กราฟออยเลอร์
ปัญหาสะพานเคอนิกส์เบิร์ก มีอยู่ว่า ณ
เมืองเคอนิกส์เบิร์กมีเกาะกลางแม่น้ำพรีเกล (Pregel)
จำนวน
2 เกาะ และมีสะพานที่เชื่อมระหว่างเกาะและเมืองดังรูปต่อไปนี้
ชาว เมืองเคอนิกส์เบิร์กพยายามหาวิธีเดินข้ามสะพานให้ครบทุกสะพาน
โดยที่ข้ามสะพานแต่ละสะพานเพียงครั้งเดียวและกลับมาที่จุดยอดเริ่มต้น
เลออนฮาร์ด ออยเลอร์ได้แปลงปัญหานี้ให้อยู่ในรูปกราฟ โดยให้อาณาบริเวณ A, B, C, D แทนด้วยจุดยอดของกราฟ และสะพานแต่ละพานแทนด้วยเส้นเชื่อมของกราฟ
เลออนฮาร์ด ออยเลอร์ได้แปลงปัญหานี้ให้อยู่ในรูปกราฟ โดยให้อาณาบริเวณ A, B, C, D แทนด้วยจุดยอดของกราฟ และสะพานแต่ละพานแทนด้วยเส้นเชื่อมของกราฟ
ปัญหาสะพานเคอนิกส์เบอร์ก
เมื่อจำลองอยู่ในรูปกราฟจะได้
จากกราฟ
สามารถแปลงได้เป็นปัญหาการลากผ่านเส้นเชื่อมของกราฟดังรูปข้างต้น
จนครบทุกเส้นโดยไม่ต้องยกปากกาและผ่านเส้นแต่ละเส้นเพียงครั้งเดียว
โดยที่จุดเริ่มต้นและจุดสิ้นสุดเป็นจุดเดียวกัน
บทนิยาม
วงจรออยเลอร์(Euler trail) คือ
รอยเดินซึ่งผ่านจุดยอดทุกจุดและเส้นเชื่อมทุกเส้นของกราฟ
ทฤษฎีบทต่อไปนี้ ให้เงื่อนไขว่า
กราฟที่กำหนดให้เป็นกราฟออยเลอร์เมื่อไร
ทฤษฎีบท ให้ G เป็นกราฟเชื่อมโยง จะได้ว่า
G เป็นกราฟออยเลอร์
ก็ต่อเมื่อ จุดยอดทุกจุดของ G มีดีกรีเป็นจำนวนคู่
กราฟที่มีวงจรออยเลอร์ เรียกว่า กราฟออยเลอร์
(Eulerian graph)
ตัวอย่าง กราฟต่อไปนี้เป็นกราฟออยเลอร์
บทนิยาม
รอยเดินออยเลอร์(Euler
circuit) คือ
วงจรที่ผ่านจุดยอดทุกจุดและเส้นเชื่อมทุกเส้นของกราฟ
ทฤษฎีบท
ให้ G เป็นกราฟเชื่อมโยง จะได้ว่า
G เป็นกราฟที่มีรอยเดินออยเลอร์ ก็ต่อเมื่อ G มีจุดยอดที่เป็นดีกรีเป็น
จำนวนคี่ไม่เกิน 2 จุด ยิ่งไปกว่านั้นจุดยอดที่เป็นจำนวนคี่เหล่านั้นจะเป็นจุดเริ่มต้นและจุดปลายของรอยเดิน
ออยเลอร์
จำนวนคี่ไม่เกิน 2 จุด ยิ่งไปกว่านั้นจุดยอดที่เป็นจำนวนคี่เหล่านั้นจะเป็นจุดเริ่มต้นและจุดปลายของรอยเดิน
ออยเลอร์
ปัญหา
หนี่งที่ดูคล้ายกับปัญหาวงจรออยเลอร์ คือปัญหาการหาวิถีในกราฟที่ไม่ใช้จุดยอดซ้ำกันยกเว้นจุดเริ่มต้นและจุดสิ้น
สุดต้องเป็นจุดเดียวกัน ซึ่งก็คือ วัฎจักรและวัฎจักรนี้ผ่านครบทุกจุดยอดในกราฟนี้
จะเรียกวัฎจักรนี้ว่า วัฎจักรแฮมิลตัน
ถ้า G มีวัฎจักรแฮมิลตัน จะเรียก G ว่าเป็นกราฟแฮมิลตัน(Hamiltonian graph)
https://sites.google.com/site/graphmath101/6-kraf-xxy-lex-r
วันที่ 4 กันยายน 2556
ไม่มีความคิดเห็น:
แสดงความคิดเห็น