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

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

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

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

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

 อ้างอิง 

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

 Euler tour and Hamilton cycles 

หมวดหมู่:Computational problems in graph theory
หมวดหมู่:NP-complete problems
หมวดหมู่:Graph theory objects