บทนิยาม
ค่าน้ำหนัก(weight) ของเส้นเชื่อม e ในกราฟ คือ จำนวนที่ไม่เป็นลบที่กำหนดไว้บนเส้นเชื่อม e
กราฟถ่วงน้ำหนัก(weight graph) คือ กราฟที่เส้นเชื่อมทุกเส้นมีค่าน้ำหนัก
.png)
จะหาเส้นทางจากเมือง
A ไปยังเมือง E ทั้งหมดที่ไม่ผ่านเมืองซ้ำกัน
เส้นทางที่ 1 A, B, D, E ระยะทางยาว 2 + 1 + 3 = 4 กิโลเมตร
เส้นทางที่ 2 A, B, D, F,
E ระยะทางยาว 2 + 1 + 2 + 2 = 7 กิโลเมตร
เส้นทางที่ 3 A, B, D, C, F, E ระยะทางยาว 2 + 1 + 3 + 6 + 2 =
14 กิโลเมตร
เส้นทางที่ 4 A, C, F, E ระยะทางยาว 5 + 6 + 2 = 13 กิโลเมตร
เส้นทางที่ 5 A, C, F, D, E ระยะทางยาว 5 + 6 + 2 + 3 = 16 กิโลเมตร
เส้นทางที่ 6 A, C, D, E ระยะทางยาว 5 + 3 + 3 = 11 กิโลเมตร
เส้นทางที่ 7 A, C, D, F,
E ระยะทางยาว 5 + 3 + 2 + 2 = 12 กิโลเมตร
จะเห็นว่าเส้นทางที่ 1 A, B, D, E ระยะทางยาว 4 กิโลเมตรเป็นระยะทางที่สั้นที่สุด
จะเห็นว่า วิถี A, B, D, E เป็นวิถีที่สั้นที่สุด
บทนิยาม วิถี(Path) คือ
แนวเดินในกราฟที่จุดยอดทั้งหมดแตกต่างกัน
วิถีที่สั้นที่สุด(shortest path) จากจุดยอด A ถึง Z ในกราฟถ่วงน้ำหนัก
คือวิถี A-Z ที่ผลรวมของน้ำหนักของเส้นเชื่อมทุกเส้นในวิถี A-Z น้อยที่สุด
ต้นไม้แผ่ทั่วที่น้อยที่สุด
วัฏจักร(Cycle) คือวงจรที่ไม่มีจุดยอดซ้ำกัน ยกเว้นจุดเริ่มต้นและจุดสุดท้าย
ต้นไม้ (tree) คือ
กราฟเชื่อมโยงที่ไม่มีวัฏจักร
บทนิยาม กราฟย่อย (subgraph) ของกราฟ
G คือ กราฟที่ประกอบด้วยจุดยอดและเส้นเชื่อมใน G
กล่าวคือ กราฟ H เป็นกราฟย่อยของกราฟ G ก็ต่อเมื่อ
V(H) เป็นสับเซตของ V(G) และ
E(H) เป็นสับเซตของ E(G)
บทนิยาม ต้นไม้แผ่ทั่ว (spanning tree) คือ
ต้นไม้ซึ่งเป็นกราฟย่อยของกราฟย่อยของกราฟเชื่อมโยง G ที่บรรจุจุดยอดทุกจุดของ G
ต้นไม้แผ่ทั่วที่น้อยที่สุด
(minimal spanning tree) คือต้นไม้แผ่ทั่วที่มีผลรวมของค่าน้ำหนักของแต่ละเส้นเชื่อมที่น้อยที่สุด
•
ในกรณีที่เราหาการเชื่อมต่อที่สั้นที่สุดโดยมีลักษณะเป็นต้นไม้แผ่ทั่ว
เราจะเรียกต้นไม้ที่ได้ว่า ต้นไม้แผ่ทั่วน้อยสุด
•
จากตัวอย่าง
จากการต่อจุด 4 จุด ที่มีตำแหน่งการวาง ดังรูป (ก)
สามารถเขียนต้นไม้แผ่ทั่วได้ดังรูป (ข) และ (ค)
พบว่า ต้นไม้แผ่ทั่วรูป (ค) คือ
ต้นไม้แผ่ทั่วน้อยสุด
ไม่มีความคิดเห็น:
แสดงความคิดเห็น