(เส้นเชื่อมระหว่าง vertex) ใช้แสดงถึงความสัมพันธ์ระหว่าง vertex หากมี vertex ตั้งแต่ 2 vertex ขึ้นไปมีความสัมพันธ์ ใช้สัญลักษณ์เส้นตรงซึ่งอาจมีหัวลูกศร หรือไม่มีก็ได้
กราฟสามารถเขียนแทนด้วยสัญลักษ์ ดังนี้
G=(V,E)
G คือ กราฟ
V คือ กลุ่มของ vertex
E คือ กลุ่มของ edge
ตัวอย่างของกราฟในชีวิตประจำวัน เช่น กราฟของการเดินทางระหว่างเมือง ซึ่ง vertex คือกลุ่มของเมืองต่างๆ และ edge คือเส้นทางเดินระหว่างเมือง หรือ ในเครือข่ายคอมพิวเตอร์ (Computer Network) vertex ก็คือ กลุ่มของเครื่องคอมพิวเตอร์ หรือ โหนดต่างๆ และ edge ก็คือเส้นทางการติดต่อสื่อสารระหว่างโหนดต่างๆ เป็นต้น
ประเภทของกราฟ
แบ่งเป็น 3 ประเภทโดยแบ่งตามประเภทของ egdg คือ
1.Direct Graph กราฟแสดงทิศทาง เป็นกราฟที่แสดงเส้นเชื่อมระหว่าง vertex โดยแสดงทิศทางของการเชื่อมต่อด้วยกัน
2.Undirected Graph กราฟที่แสดงเส้นเชื่อมต่อระหว่าง vertex แต่ไม่แสดงทิศทางของการเชื่อมต่อ
3.Cyclic Graph กราฟที่มีเส้นเชื่อมต่อระหว่าง vertex ที่ทำให้ vertex มีลักษณะเป็นวงจรปิด(Cycle)
เส้นเชื่อมต่อระหว่าง vertex อาจจะแสงทิศทางหรือไม่แสดงทิศทางการเชื่อมต่อก็ได้
เส้นทาง (Path)
เส้นทางคือการเดินทางจาก vertex หนึ่งไปยังอีก vertex หนึ่งที่ต้องการ โดยผ่าน edge ที่เชื่อระหว่าง vertex ความของเส้นทาง คือจำนวนของ edge ในเส้นทางเดินนั้นว่ามีจำนวนเท่าไร ในการเดินทางจาก
vertex หนึ่งไปยังอีก vertex หนึ่งถ้าหากเส้นทางประกอบด้วย vertex จำนวน N ความยาวของเส้นทางจะเท่ากับ N-1
การแทนที่ด้วยกราฟเมตริกซ์
โครงสร้างข้อมูลประเภทกราฟสามารถใช้เมตริกซ์มาแสดงแทนได้โดยกราฟที่ประกอบด้วย vertex จำนวน
N vertex สามารถแทนที่ด้วยเมตริกซ์ขนาด N*N โดยค่าในเมตริกซ์จะประกอบด้วย ค่า 0 และ 1
ค่า 0 จะใช้แทนไม่มี edge ความยาว 1 เชื่อต่อจากต้นทางไปปลายทาง และ ค่า 1 จะใช้แทนมี edge ความยาว 1 เชื่อต่อจากต้นทางไปปลายทาง
ไม่มีความคิดเห็น:
แสดงความคิดเห็น