ประเภทของกราฟ

ประเภทที่ 1 แบบไม่ระบุทิศทาง หรือ Undirected Graph

ในการสื่อสารระหว่างเมือง 2 เมือง ซึ่งประกอบด้วยอุปกรณ์คอมพิวเตอร์และสายโทรศัพท์ที่เชื่อมระหว่างเครื่องคอมพิวเตอร์เมื่อนำมาเขียนเป็นกราฟ สามารถแทนตำแหน่งของคอมพิวเตอร์ด้วยจุด และสามารถโทรศัพท์ด้วยเส้นเชื่อมดังรูปที่ 1

รูปที่ 1 การสื่อสารระหว่างเมืองแบบไม่ระบุทิศทาง

จากรูปที่ 1 เห็นได้ว่าระหว่างเครื่องคอมพิวเตอร์ 2 เครื่อง ประกอบด้วยสายโทรศัพท์ 1 สาย และสายโทรศัพท์แต่ละสายมีการทำงานสำหรับส่งข่าวสารได้ 2 ทาง ระบบการเชื่อมโยงแบบนี้เรียกว่า กราฟแบบไม่ระบุทิศทาง (Undirected Graph) ซึ่งประกอบด้วยโหนด (node) แทนเครื่องคอมพิวเตอร์และเส้นเชื่อมไม่ระบุทิศทาง แทนสายโทรศัพท์ซึ่งเส้นเชื่อมแต่ละเส้นต่อระหว่างโหนด 2 โหนด

ประเภทที่ 2 แบบระบุทิศทาง หรือ Direct Graph

กรณีของระบบการสื่อสารที่เชื่อมโยงในการสื่อสารที่ไม่สามารถทำงานได้ 2 ทิศทาง เช่น เครื่องคอมพิวเตอร์ที่เชียงใหม่ สามารถรับข้อมูลจากคอมพิวเตอร์อื่นเขียนแทนด้วยเส้นเชื่อมระบุทิศทางที่ประกอบด้วยหัวลูกศรชี้เข้าสู่โหนดเชียงใหม่ แต่โหนดนี้ไม่สามารถส่งข้อมูลออก นอกจากนี้สายโทรศัพท์เส้นอื่นสามารถดำเนินงานได้ทั้ง 2 ทิศทาง และแทนด้วยเส้นเชื่อมหลายเส้น เขียนในทิศทางตรงกันข้าม

รูปที่ 2 การสื่อสารผ่านสายโทรศัพท์ระหว่างเมืองแบบระบุทิศทาง

ประเภทที่ 3 กราฟแบบมีโหนดต้นทางและโหนดปลายทางเป็นโหนดเดียวกัน หรือ Cyclic Graph

เป็นกราฟที่มีเส้นทาง (Path) เกิดจากเส้นเชื่อมระหว่างโหนดที่มีลักษณะเป็นวงจรปิด (Cycle) หมายถึงมีโหนดต้นทางและโหนดปลายทางเป็นโหนดเดียวกัน โดย Cyclic Graph สามารถเป็นได้ทั้ง Direct Graph (Digraph) และ Undirected Graph

รูปที่ 3 รูปตัวอย่างของ Cyclic Graph

เส้นทาง (Path) ของโหนดหนึ่งซึ่งเป็นโหนดต้นทางไปยังโหนดปลายทางใด ๆ ที่ต้องการ หมายถึงเส้นทางจากโหนดต้นทางไปยังโหนดปลายทางซึ่งจะต้องผ่านโหนดอื่น ๆ ที่อยู่ระหว่าง 2 โหนดนี้ ตัวอย่างเช่น จากรูป ซึ่งเป็น Cyclic Direct Graph (หรือ Cyclic Digraph) จะได้ว่าเส้นทางของโหนด 1 ไปโหนด 2 มีทั้งหมด 3 เส้นทางดังนี้

เส้นทางที่ 1 คือ 1 – 3 – 4 – 2

เส้นทางที่ 2 คือ 1 – 3 – 2

เส้นทางที่ 3 คือ 1 – 4 – 2

Cycle Path เป็นเส้นทางของโหนดต้นทางไปยังโหนดปลายทาง โดยทั้งโหนดต้นทางและโหนดปลายทางนี้เป็นโหนดเดียวกัน ตัวอย่างเช่น จากรูป (a) ซึ่งเป็น Cyclic Direct Graph (หรือ Cyclic Digraph) เส้นทางของโหนด 1 ไปยังโหนดทุกโหนดบนกราฟและมีโหนดปลายทางเป็นโหนด 1 คือ 1 – 3 – 4 – 2 – 1 หรือเส้นทางของโหนด 1 ไปยังโหนดบางโหนดบนกราฟและมีโหนดปลายทางเป็นโหนด 1 คือ 1 – 3 – 2 – 1 เป็นต้น