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

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา
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.

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

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

บทนิยาม[แก้]

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

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

อ้างอิง[แก้]

  1. Biggs, N. L. (1981), "T. P. Kirkman, mathematician", The Bulletin of the London Mathematical Society, 13 (2): 97–120, doi:10.1112/blms/13.2.97, MR 0608093.

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