วัฎจักรฮามิลตัน

A Hamiltonian cycle in a dodecahedron. Like all platonic solids, the dodecahedron is Hamiltonian.

The Herschel graph is the smallest possible polyhedral graph that does not have a Hamiltonian cycle.

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

วิถีฮามิลตันและวัฏจักรฮามิลตันได้รับการตั้งชื่อตามวิเลียม โรแวน ฮามิลตันผู้คิดค้นเกมไอโคเซียนซึ่งมีชื่อเรียกอีกชื่อหนึ่งว่าปริศนาของฮามิลตัน ทั้งนี้เป็นปริศนาที่เกี่ยวข้องกับการหาวัฏจักรฮามิลตันในทุกๆด้านของรูปทรงสิบสองหน้า ฮามิลตันแก้ไขปัญหานี้โดยใช้แคลคูลัสไอโคเซียนซึ่งเป็นโครงสร้างทางพีชคิตที่มีพื้นฐานมาจากรากของหนึ่ง ผลเฉลยของปัญหานี้ไม่สามารถนำมาใช้กับกรณีทั่วไปอื่นๆได้ ทั้งนี้ ถึงแม้ว่าชื่อกล่าวนี้มีชื่อของฮามิลตันเขามาเกี่ยวข้องแต่วัฏจักรฮามิลตันนี้ได้รับการศึกษามาก่อนหน้านี้จากโทมัส เคิร์กแมน

บทนิยาม

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

วัฏจักรฮามิลตันเป็นวัฏจักรที่ผ่านจุดยอดแต่ละจุดเพียงหนึ่งครั้ง (ยกเว้นจุดเริ่มต้และจุดสิ้นสุดซึ่งเป็นจุดเดียวกันและมีวัฏจักรผ่านสองคร้ง) กราฟที่มีวัฏจักรฮามิลตันเรียกว่ากราฟฮามิลตัน

แหล่งข้อมูลอื่น

• เอริก ดับเบิลยู. ไวส์สไตน์, "Hamiltonian Cycle" จากแมทเวิลด์.
• Euler tour and Hamilton cycles เก็บถาวร 2012-03-09 ที่ เวย์แบ็กแมชชีน