การประยุกต์ของกราฟ-คณิตศาสตร์ ม.ปลาย

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

บางครั้งอาจมีการกำหนดจำนวนไว้บนเส้นเชื่อมแต่ละเส้น ซึ่งจำนวนเหล่านี้อาจแทนระยะทางระหว่างจังหวัด หรืออาจ

แทนเวลาในการเดินทางจากจังหวัดหนึ่งไปยังอีกจังหวัดหนึ่งหรืออาจแทนค่าใช้จ่ายในการสร้างถนนระหว่างจังหวัดสอง

จังหวัด เป็นต้น ดังตัวอย่างกราฟในรูป

จำนวนที่กำหนดไว้บนเส้นเชื่อมดังกล่าว เรียกว่า ค่าน้ำหนัก ของเส้นเชื่อมนั้น และกราฟที่มีลักษณะดังเช่นรูป

เรียกว่า “กราฟถ่วงน้ำหนัก” ซึ่งมีบทนิยาม ดังนี้

บทนิยาม

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

กราฟถ่วงน้ำหนัก (weighted 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 น้อยที่สุด

สำหรับกราฟถ่วงนำหนักที่มีจุดยอดและเส้นเชื่อมเป็นจำนวนมาก การหาวิถี A – Z ที่สั้นที่สุด
โดยการค้นหาวิถี A – Z ทั้งหมด แล้วเลือกวิถีที่ผลรวมของค่าน้ำหนักน้อยที่สุด ทำได้ไม่สะดวกและเสียเวลา ในการหาวิถี A – Z ที่สั้นที่สุด ดังตัวอย่างข้างต้น ทำได้ไม่สะดวกและเสียเวลา ในกรณีนี้มีขั้นตอนวิธีที่ใช้หาวิถีที่สั้นที่สุดหลายวิธี เช่น ขั้นตอนวิธีของไดจ์สตรา (Dijkstra’algorithm) ซึ่งไม่ขอกล่าวในระดับชั้นนี้

ต้นไม้แผ่ทั่วน้อยที่สุด

บทนิยาม วัฎจักร คือ วงจรที่ไม่มีจุดยอดซ้ำกัน ยกเว้นจุดเริ่มต้นและจุดสุดท้าย

ต้นไม้ คือ กราฟเชื่อมโยงที่ไม่มีวัฎจักร

ตัวอย่างที่ 1 กำหนดกราฟดังรูป

อยากทราบว่า กราฟทั้งสองเป็นต้นไม้หรือไม่

วิธีทำ กราฟ A และกราฟ B เป็นกราฟเชื่อมโยงและไม่มีวัฏจักร

ดังนั้น กราฟ A และกราฟ Bเป็นต้นไม้

ตัวอย่างที่ 2 กำหนดกราฟดังรูป

วิธีทำ C ไม่เป็นต้นไม้เพราะมีวัฎจักร

D ไม่เป็นต้นไม้เพราะไม่ใช่กราฟเชื่อมโยง

ข้อสังเกต 1.ต้นไม้ไม่มีเส้นเชื่อมขนาน และไม่มีวงวน

2.ตันไม้ที่มี n จุดยอด จะมีเส้นเชื่อม n – 1 เส้นเสมอ

บทนิยาม กราฟย่อย(subgraph) ของกราฟ G คือกราฟที่ประกอบด้วยจุดยอดและเส้นเชื่อมใน G กล่าวคือ

กราฟ H เป็นกราฟย่อยของกราฟ G ถ้า V(H) V(G) และ E(H) E(G)

ตัวอย่างที่ 3 กำหนดกราฟ G และกราฟ H ดังรูป

อยากทราบว่ากราฟ H เป็นส่วนย่อยของกราฟ G หรือไม่

วิธีทำ   จากรูป V(G) = { A, B, C, D }
                   V(H) = { A, B, C, D }
                     E(G) = {AB, BC, CD, DA, BD}
                   E(H) = {AB, BC, DA, BD}

จะได้ว่า กราฟ H เป็นกราฟย่อยของกราฟ G

บทนิยาม ต้นไม้แผ่ทั่ว (spanning tree) คือ ต้นไม้ซึ่งเป็นกราฟย่อยของ

กราฟเชื่อมโยง G ที่บรรจุจุดยอดทุกจุดยอดของ G

ตัวอย่าง กำหนดกราฟ ดังรูป