กราฟออยเลอร์

กราฟออยเลอร์

        ปัญหาสะพานเคอนิกส์เบิร์ก มีอยู่ว่า ณ เมืองเคอนิกส์เบิร์กมีเกาะกลางแม่น้ำพรีเกล (Pregel)

จำนวน 2 เกาะ และมีสะพานที่เชื่อมระหว่างเกาะและเมืองดังรูปต่อไปนี้

 

        ชาว เมืองเคอนิกส์เบิร์กพยายามหาวิธีเดินข้ามสะพานให้ครบทุกสะพาน โดยที่ข้ามสะพานแต่ละสะพานเพียงครั้งเดียวและกลับมาที่จุดยอดเริ่มต้น 
         เลออนฮาร์ด ออยเลอร์ได้แปลงปัญหานี้ให้อยู่ในรูปกราฟ โดยให้อาณาบริเวณ A, B, C, D แทนด้วยจุดยอดของกราฟ และสะพานแต่ละพานแทนด้วยเส้นเชื่อมของกราฟ 

ปัญหาสะพานเคอนิกส์เบอร์ก เมื่อจำลองอยู่ในรูปกราฟจะได้

จากกราฟ สามารถแปลงได้เป็นปัญหาการลากผ่านเส้นเชื่อมของกราฟดังรูปข้างต้น จนครบทุกเส้นโดยไม่ต้องยกปากกาและผ่านเส้นแต่ละเส้นเพียงครั้งเดียว

            โดยที่จุดเริ่มต้นและจุดสิ้นสุดเป็นจุดเดียวกัน

บทนิยาม

        วงจรออยเลอร์(Euler trail) คือ รอยเดินซึ่งผ่านจุดยอดทุกจุดและเส้นเชื่อมทุกเส้นของกราฟ   

ทฤษฎีบทต่อไปนี้ ให้เงื่อนไขว่า กราฟที่กำหนดให้เป็นกราฟออยเลอร์เมื่อไร 

  ทฤษฎีบท ให้ G เป็นกราฟเชื่อมโยง จะได้ว่า

G เป็นกราฟออยเลอร์ ก็ต่อเมื่อ จุดยอดทุกจุดของ G มีดีกรีเป็นจำนวนคู่

               กราฟที่มีวงจรออยเลอร์ เรียกว่า กราฟออยเลอร์ (Eulerian graph)   

 

ตัวอย่าง กราฟต่อไปนี้เป็นกราฟออยเลอร์

 บทนิยาม รอยเดินออยเลอร์(Euler circuit) คือ วงจรที่ผ่านจุดยอดทุกจุดและเส้นเชื่อมทุกเส้นของกราฟ

ทฤษฎีบท ให้ G เป็นกราฟเชื่อมโยง จะได้ว่า G เป็นกราฟที่มีรอยเดินออยเลอร์ ก็ต่อเมื่อ G มีจุดยอดที่เป็นดีกรีเป็น         
                    จำนวนคี่ไม่เกิน 2 จุด ยิ่งไปกว่านั้นจุดยอดที่เป็นจำนวนคี่เหล่านั้นจะเป็นจุดเริ่มต้นและจุดปลายของรอยเดิน
                    ออยเลอร์

ปัญหา หนี่งที่ดูคล้ายกับปัญหาวงจรออยเลอร์ คือปัญหาการหาวิถีในกราฟที่ไม่ใช้จุดยอดซ้ำกันยกเว้นจุดเริ่มต้นและจุดสิ้น สุดต้องเป็นจุดเดียวกัน ซึ่งก็คือ วัฎจักรและวัฎจักรนี้ผ่านครบทุกจุดยอดในกราฟนี้ จะเรียกวัฎจักรนี้ว่า วัฎจักรแฮมิลตัน

         ถ้า G มีวัฎจักรแฮมิลตัน จะเรียก G ว่าเป็นกราฟแฮมิลตัน(Hamiltonian graph)  

https://sites.google.com/site/graphmath101/6-kraf-xxy-lex-r 

วันที่ 4 กันยายน 2556