การประยุกต์ของกราฟ

บทนิยาม 

   ค่าน้ำหนัก(weight) ของเส้นเชื่อม e ในกราฟ คือ จำนวนที่ไม่เป็นลบที่กำหนดไว้บนเส้นเชื่อม e 

    กราฟถ่วงน้ำหนัก(weight graph) คือ กราฟที่เส้นเชื่อมทุกเส้นมีค่าน้ำหนัก

จะหาเส้นทางจากเมือง  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 จุด ที่มีตำแหน่งการวาง ดังรูป (ก) สามารถเขียนต้นไม้แผ่ทั่วได้ดังรูป (ข) และ (ค) 

พบว่า ต้นไม้แผ่ทั่วรูป (ค) คือ ต้นไม้แผ่ทั่วน้อยสุด