เส้นทางแฮมิลตัน

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

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

แม้ว่าจะตั้งชื่อตามแฮมิลตัน แต่รอบแฮมิลตันในทรงหลายเหลี่ยมก็ได้รับการศึกษามาก่อนแล้วหนึ่งปีโดยโทมัส เคิร์กแมนซึ่งโดยเฉพาะอย่างยิ่งได้ยกตัวอย่างทรงหลายเหลี่ยมที่ไม่มีรอบแฮมิลตัน^{[ 1 ]}ก่อนหน้านั้น รอบแฮมิลตันและเส้นทางในกราฟของอัศวินบนกระดานหมากรุก หรือ การเดินของอัศวินได้รับการศึกษาในศตวรรษที่ 9 ในคณิตศาสตร์อินเดียโดยรุดราตะและในช่วงเวลาเดียวกันในคณิตศาสตร์อิสลามโดยอัล-อัดลี อาร์-รูมีในยุโรปศตวรรษที่ 18 การเดินของอัศวินได้รับการตีพิมพ์โดยอับราฮัม เดอ มัวร์และเลออนฮาร์ด ออยเลอร์^{[ 2 ]}

คำจำกัดความ

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

วงจรแฮมิลโทเนียน (Hamiltonian cycle) , วงจรแฮมิลโทเนียน (Hamiltonian circuit) , เส้นทางผ่านจุดยอด (vertex tour ) หรือวงจรในกราฟ (graph cycle)คือวงจรที่ผ่านจุดยอดแต่ละจุดเพียงครั้งเดียว กราฟที่ประกอบด้วยวงจรแฮมิลโทเนียนเรียกว่ากราฟแฮมิลโทเนียน (Hamiltonian graph )

แนวคิดที่คล้ายกันนี้สามารถกำหนดได้สำหรับกราฟแบบมีทิศทางโดยที่แต่ละขอบ (ส่วนโค้ง) ของเส้นทางหรือวงจรสามารถลากได้เพียงทิศทางเดียวเท่านั้น (กล่าวคือ จุดยอดเชื่อมต่อกันด้วยลูกศร และขอบจะลากแบบ "หางต่อหัว")

การแยกส่วนแบบแฮมิลโทเนียนคือการแยกส่วนขอบของกราฟออกเป็นวงจรแฮมิลโทเนียน

เขาวงกตแฮมิลตันเป็นปริศนาตรรกะประเภทหนึ่งซึ่งเป้าหมายคือการค้นหาวงจรแฮมิลตันที่ไม่ซ้ำกันในกราฟที่กำหนด^{[ 3 ]}^{[ 4 ]}

ตัวอย่าง

กราฟสมบูรณ์ที่มีจุดยอดมากกว่าสองจุดเรียกว่ากราฟแฮมิลโทเนียน
กราฟวัฏจักรทุก กราฟ เป็นแบบแฮมิลโทเนียน
ทุกทัวร์นาเมนต์จะมีเส้นทางแฮมิลโทเนียนเป็นจำนวนคี่ ( Rédei 1934)
ทรงหลายเหลี่ยมเพลโตทุกอันเมื่อพิจารณาว่าเป็นกราฟ จะเป็นแฮมิลโทเนียน^{[ 5 ]}
กราฟเคย์ลีย์ของกลุ่มค็อกซีเตอร์ จำกัด เป็นกราฟแฮมิลโทเนียน (ดูข้อสันนิษฐานของโลวัสซ์สำหรับข้ออ้างที่ครอบคลุมกว่านี้)
กราฟ Cayleyบนกลุ่มนิลโพเท นต์ ที่มีกลุ่มย่อยคอมมิวเทเตอร์ แบบวัฏจักร เป็นแฮมิลโทเนียน^{[ 6 ]}
กราฟพลิกของรูปหลายเหลี่ยมนูนหรือเทียบเท่ากับกราฟการหมุนของต้นไม้ไบนารีคือแฮมิลโทเนียน^{[ 7 ]}^{[ 8 ]}

คุณสมบัติ

วงจรแฮมิลโทเนียนใดๆ สามารถแปลงเป็นเส้นทางแฮมิลโทเนียนได้โดยการลบขอบด้านใดด้านหนึ่งออก แต่เส้นทางแฮมิลโทเนียนจะสามารถขยายเป็นวงจรแฮมิลโทเนียนได้ก็ต่อเมื่อจุดปลายของวงจรทั้งสองอยู่ติดกันเท่านั้น

กราฟแฮมิลโทเนียนทั้งหมดเป็นกราฟเชื่อมต่อสองทางแต่กราฟเชื่อมต่อสองทางไม่จำเป็นต้องเป็นกราฟแฮมิลโทเนียน (ดูตัวอย่างเช่นกราฟปีเตอร์เซน ) ^{[ 9 ]}

กราฟออยเลอร์ $G$ ( กราฟเชื่อมต่อที่ทุกจุดยอดมีดีกรีคู่) จำเป็นต้องมีเส้นทางออยเลอร์ ซึ่งเป็นเส้นทางปิดที่ผ่านขอบแต่ละขอบของ $G$ เพียงครั้งเดียว เส้นทางนี้สอดคล้องกับวัฏจักรแฮมิลตันในกราฟเส้น $L (G)$ ดังนั้นกราฟเส้นของกราฟออยเลอร์ทุกกราฟจึงเป็นกราฟแฮมิลตัน กราฟเส้นอาจมีวัฏจักรแฮมิลตันอื่นๆ ที่ไม่สอดคล้องกับเส้นทางออยเลอร์ และโดยเฉพาะอย่างยิ่งกราฟเส้น $L (G)$ ของกราฟแฮมิลตัน $G ทุกกราฟนั้นเป็นกราฟแฮมิลตัน ไม่ว่ากราฟ$ $G$ จะเป็นกราฟออยเลอร์หรือไม่ก็ตาม^{[ 10 ]}

ทัวร์นาเมนต์ (ที่มีจุดยอดมากกว่าสองจุด) จะเป็นแฮมิลโทเนียนก็ต่อเมื่อมันเชื่อม ต่อกันอย่างแน่นหนา เท่านั้น

จำนวนวัฏจักรแฮมิลโทเนียนที่แตกต่างกันในกราฟแบบไม่มีทิศทางสมบูรณ์ที่มี จุดยอด $n$ จุด คือ $⁠ (n - 1)! / 2 และ$ ในกราฟทิศทางสมบูรณ์ที่มี $n$ จุดยอด จะมีค่าเท่ากับ $(n - 1)!$ การนับเหล่านี้ถือว่าวงจรที่เหมือนกันยกเว้นจุดเริ่มต้นจะไม่ถูกนับแยกกัน

ทฤษฎีบทบอนดี-ชวาทัล

การกำหนดลักษณะ ดีกรีจุดยอดที่ดีที่สุดของกราฟแฮมิลโทเนียนได้รับการเสนอในปี 1972 โดย ทฤษฎีบท Bondy – Chvátalซึ่งเป็นการขยายผลลัพธ์ก่อนหน้านี้โดยGA Dirac (1952) และØystein Oreทั้งทฤษฎีบทของ Dirac และ Ore สามารถอนุมานได้จากทฤษฎีบทของ Pósa (1962) ความเป็นแฮมิลโทเนียนได้รับการศึกษาอย่างกว้างขวางโดยสัมพันธ์กับพารามิเตอร์ต่างๆ เช่นความหนาแน่น ของกราฟ ความเหนียว กราฟย่อยต้องห้ามและระยะทางรวมถึงพารามิเตอร์อื่นๆ^{[ 11 ]}ทฤษฎีบทของ Dirac และ Ore โดยพื้นฐานแล้วระบุว่ากราฟเป็นแฮมิลโทเนียนหากมีขอบ เพียงพอ

ทฤษฎีบท Bondy–Chvátal ทำงานกับส่วนปิด $cl(G)$ ของกราฟ $G$ ที่มี $n$ จุดยอด ซึ่งได้มาจากการเพิ่มขอบใหม่ $uv$ เชื่อมจุดยอด $u$ และ $v$ ที่ไม่ติดกัน ซ้ำๆ โดยที่ $deg($ $v$ $) + deg($ $u$ $) \geq$ $n$ จนกว่าจะไม่พบจุดยอดคู่ใดที่มีคุณสมบัตินี้อีกต่อไป

ทฤษฎีบท Bondy–Chvátal (1976) —กราฟจะเป็นกราฟแฮมิลโทเนียนก็ต่อเมื่อส่วนปิดของกราฟนั้นเป็นกราฟแฮมิลโทเนียน

เนื่องจากกราฟสมบูรณ์เป็นกราฟแฮมิลโทเนียน ดังนั้นกราฟทั้งหมดที่มีส่วนปิดสมบูรณ์จึงเป็นกราฟแฮมิลโทเนียน ซึ่งเป็นเนื้อหาของทฤษฎีบทก่อนหน้านี้โดยดิแรกและโอเร

ทฤษฎีบทของดิแรก (1952) —กราฟอย่างง่ายที่มี จุดยอด $n$ จุด ( ) เรียกว่ากราฟแฮมิลโทเนียน ถ้าทุกจุดยอดมีดีกรี n หรือมากกว่า $n\geq 3$ ${\tfrac {n}{2}}$

ทฤษฎีบทของโอเร (1960) —กราฟแบบง่ายที่มี $จุดยอด n$ จุด () เรียกว่ากราฟแฮมิลโทเนียน ถ้าสำหรับทุกคู่ของจุดยอดที่ไม่ติดกัน ผลรวมของดีกรีของจุดยอดทั้งสองนั้นมี $ค่าเท่ากับ n$ หรือมากกว่า $n\geq 3$

ทฤษฎีบทต่อไปนี้สามารถถือได้ว่าเป็นเวอร์ชันที่มีทิศทาง:

Ghouila–Houiri (1960) —กราฟทิศทาง แบบง่าย ที่เชื่อมต่อกันอย่างแน่นหนา ซึ่งมี $n$ จุดยอด เรียก ว่า กราฟแฮมิลโทเนียน ถ้าทุกจุดยอดมีดีกรีเต็มมากกว่าหรือเท่ากับ $n$

เมย์เนียล (1973) —กราฟทิศทาง แบบง่าย ที่เชื่อมต่อกันอย่างแน่นหนา ซึ่งมี $n$ จุดยอด เรียกว่ากราฟแฮมิลโทเนียน ถ้าผลรวมของดีกรีเต็มของทุกคู่ของจุดยอดที่แตกต่างกันและไม่ติดกันมีค่ามากกว่าหรือเท่ากับ $2n-1$

จำนวนจุดยอดต้องเพิ่มเป็นสองเท่า เนื่องจากขอบที่ไม่มีทิศทางแต่ละเส้นจะสอดคล้องกับส่วนโค้งที่มีทิศทางสองส่วน ดังนั้นระดับของจุดยอดในกราฟที่มีทิศทางจึงเป็นสองเท่าของระดับในกราฟที่ไม่มีทิศทาง

Rahman– Kaykobad (2005) —กราฟแบบง่ายที่มี จุดยอด $n$ จุดจะมีเส้นทางแฮมิลโทเนียนก็ต่อเมื่อสำหรับทุกคู่จุดยอดที่ไม่ติดกัน ผลรวมของดีกรีและความยาวเส้นทางที่สั้นที่สุดของคู่จุด ยอดเหล่านั้นมีค่ามากกว่า $n$ ^{[ 12 ]}

ทฤษฎีบทข้างต้นสามารถระบุได้เพียงการมีอยู่ของเส้นทางแฮมิลโทเนียนในกราฟเท่านั้น ไม่ใช่วัฏจักรแฮมิลโทเนียน

ผลลัพธ์เหล่านี้จำนวนมากมีลักษณะคล้ายคลึงกับกราฟสองส่วน ที่สมดุล ซึ่งดีกรีของจุดยอดจะถูกเปรียบเทียบกับจำนวนจุดยอดบนด้านใดด้านหนึ่งของการแบ่งสองส่วน แทนที่จะเป็นจำนวนจุดยอดในกราฟทั้งหมด^{[ 13 ]}

การมีอยู่ของวัฏจักรแฮมิลโทเนียนในกราฟระนาบ

ทฤษฎีบท—การแบ่งสามเหลี่ยมระนาบที่เชื่อมต่อ 4 จุดจะมีวัฏจักรแฮมิลโทเนียน^{[ 14 ]}

ทฤษฎีบท—กราฟระนาบที่เชื่อมต่อ 4 จุดจะมีวัฏจักรแฮมิลโทเนียน^{[ 15 ]}

พหุนามวัฏจักรแฮมิลโทเนียน

การแสดงเชิงพีชคณิตของวัฏจักรแฮมิลโทเนียนของไดกราฟที่มีน้ำหนักที่กำหนด (ซึ่งส่วนโค้งได้รับน้ำหนักจากฟิลด์พื้นฐานบางอย่าง) คือพหุนามวัฏจักรแฮมิลโทเนียนของเมทริกซ์ประชิดที่มีน้ำหนัก ซึ่งกำหนดเป็นผลรวมของผลคูณของน้ำหนักส่วนโค้งของวัฏจักรแฮมิลโทเนียนของไดกราฟ พหุนามนี้จะไม่เป็นศูนย์โดยสมบูรณ์ในฐานะฟังก์ชันของน้ำหนักส่วนโค้งก็ต่อเมื่อไดกราฟเป็นแฮมิลโทเนียน ความสัมพันธ์ระหว่างความซับซ้อนในการคำนวณของการคำนวณและการคำนวณค่าถาวรได้รับการแสดงโดย Grigoriy Kogan ^{[ 16 ]}

ดูเพิ่มเติม

ข้อสันนิษฐานของบาร์เน็ตต์ปัญหาที่ยังไม่ได้รับการแก้ไขเกี่ยวกับความเป็นแฮมิลตันของกราฟทรงหลาย เหลี่ยมสอง ส่วน ลูกบาศก์
เส้นทางออยเลอร์ (Eulerian path)คือเส้นทางที่ลากผ่านขอบทั้งหมดในกราฟ
ทฤษฎีบทของเฟลชเนอร์เกี่ยวกับกำลังสองแฮมิลตันของกราฟ
รหัสสีเทา
ทฤษฎีบทของกรินเบิร์กซึ่งให้เงื่อนไขที่จำเป็นสำหรับกราฟระนาบที่จะมีวัฏจักรแฮมิลโทเนียน
ปัญหาเส้นทางแฮมิลโทเนียนคือ ปัญหาการคำนวณเพื่อหาเส้นทางแฮมิลโทเนียน
กราฟไฮโปแฮมิลโทเนียนคือกราฟที่ไม่ใช่แฮมิลโทเนียน แต่กราฟย่อยที่ลบจุดยอดทุกจุดนั้นจะเป็นกราฟแฮมิลโทเนียน
การเดินของอัศวินวงจรแฮมิลตันในกราฟของอัศวิน
สัญลักษณ์ LCFสำหรับกราฟลูกบาศก์ แฮมิลโท เนียน
ข้อสันนิษฐานของ Lovászที่ว่ากราฟแบบ vertex-transitiveเป็นกราฟแบบ Hamiltonian
กราฟแพนไซคลิกคือกราฟที่มีวงจรทุกความยาว รวมถึงวงจรแฮมิลโทเนียน
Panconnectivityคือการเสริมสร้างทั้ง pancyclicity และ Hamiltonian-connectedness ให้แข็งแกร่งยิ่งขึ้น
สะพานเจ็ดแห่งแห่งเคอนิกส์แบร์ก
เลขชี้กำลังความสั้นคือค่าตัวเลขที่บ่งบอกว่ากราฟในตระกูลหนึ่งๆ นั้นอยู่ห่างจากกราฟแฮมิลโทเนียนได้มากแค่ไหน
เส้นทาง งูในกล่อง (Snake-in-the-box) ซึ่ง เป็นเส้นทางเหนี่ยวนำที่ยาวที่สุดในไฮเปอร์คิวบ์
อัลกอริทึม Steinhaus–Johnson–Trotterสำหรับการค้นหาเส้นทางแฮมิลโทเนียนในเพอร์มูโทเฮดรอน
กราฟซับแฮมิลโทเนียนคือกราฟย่อยของกราฟแฮมิลโทเนียนแบบระนาบ
ข้อสันนิษฐานของเทต (ซึ่งปัจจุบันทราบแล้วว่าไม่ถูกต้อง) ที่ว่า กราฟทรงหลายเหลี่ยมปกติ 3 มิติเป็นกราฟแฮมิลโทเนียน
ปัญหาพนักงานขายเดินทาง
กราฟแฮร์ริสคือตระกูลของกราฟที่มีความทนทาน เป็นแบบออยเลอร์และไม่ใช่แบบแฮมิลโทเนียน

หมายเหตุ

^ Biggs, NL (1981), "TP Kirkman นักคณิตศาสตร์", The Bulletin of the London Mathematical Society , 13 (2): 97– 120, doi : 10.1112/blms/13.2.97 , MR 0608093.
^วัตกินส์, จอห์น เจ. (2004), "บทที่ 2: การเดินของอัศวิน", ทั่วทั้งกระดาน: คณิตศาสตร์ของปัญหาบนกระดานหมากรุก , สำนักพิมพ์มหาวิทยาลัยพรินซ์ตัน, หน้า 25–38 , ISBN 978-0-691-15498-5.
↑เดอ รุยเตอร์, โยฮาน (2017) Hamilton Mazes – คู่มือสำหรับผู้เริ่มต้น
^ฟรีดแมน, เอริช. "เขาวงกตแบบแฮมิลตัน" . วังปริศนาของเอริช.เก็บถาวรจากต้นฉบับเมื่อวันที่ 16 เมษายน 2016. สืบค้นเมื่อ23 ตุลาคม 2025 .
^การ์ดเนอร์, เอ็ม. "เกมคณิตศาสตร์: เกี่ยวกับความคล้ายคลึงที่น่าทึ่งระหว่างเกมไอโคเซียนและหอคอยฮานอย" Sci. Amer. 196, 150–156, พฤษภาคม 1957
^ Ghaderpour, E.; Morris, DW (2014). "กราฟ Cayley บนกลุ่มนิลโพเทนต์ที่มีกลุ่มย่อยคอมมิวเทเตอร์แบบวัฏจักรเป็นแฮมิลโทเนียน" Ars Mathematica Contemporanea . 7 (1): 55– 72. arXiv : 1111.6216 . doi : 10.26493/1855-3974.280.8d3 . S2CID 57575227 .
^ Lucas, Joan M. (1987), "กราฟการหมุนของต้นไม้ไบนารีเป็นแบบแฮมิลโทเนียน", Journal of Algorithms , 8 (4): 503– 535, doi : 10.1016/0196-6774(87)90048-4
^ Hurtado, Ferran ; Noy, Marc (1999), "กราฟของการแบ่งรูปสามเหลี่ยมของรูปหลายเหลี่ยมนูนและต้นไม้ของการแบ่งรูปสามเหลี่ยม", เรขาคณิตเชิงคำนวณ , 13 (3): 179– 188, doi : 10.1016/S0925-7721(99)00016-4
^ Eric W. Weisstein . "กราฟเชื่อมต่อสองทาง" . Wolfram MathWorld.
^ Balakrishnan, R.; Ranganathan, K. (2012), "Corollary 6.5.5", A Textbook of Graph Theory , Springer, หน้า 134, ISBN 9781461445296.
^ Gould, Ronald J. (8 กรกฎาคม 2545). "ความก้าวหน้าเกี่ยวกับปัญหาแฮมิลโทเนียน – บทสำรวจ" (PDF) . มหาวิทยาลัยเอมอรี. เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 13 กรกฎาคม 2561. สืบค้นเมื่อ10 ธันวาคม 2555 .
^ Rahman, MS; Kaykobad, M. (เมษายน 2548). "เกี่ยวกับวัฏจักรแฮมิลโทเนียนและเส้นทางแฮมิลโทเนียน". Information Processing Letters . 94 : 37–41 . doi : 10.1016/j.ipl.2004.12.002 .
^ Moon, J.; Moser, L. (1963), "เกี่ยวกับกราฟสองส่วนแฮมิลโทเนียน", Israel Journal of Mathematics , 1 (3): 163– 165, doi : 10.1007/BF02759704 , MR 0161332 , S2CID 119358798
^ Whitney, Hassler (1931), "ทฤษฎีบทเกี่ยวกับกราฟ", Annals of Mathematics , Second Series, 32 (2): 378– 390, doi : 10.2307/1968197 , JSTOR 1968197 , MR 1503003
^ Tutte, WT (1956), "ทฤษฎีบทเกี่ยวกับกราฟระนาบ", Trans. Amer. Math. Soc. , 82 : 99– 116, doi : 10.1090/s0002-9947-1956-0081471-8
^ Kogan, Grigoriy (1996). "การคำนวณค่าคงที่บนฟิลด์ที่มีลักษณะเฉพาะ 3: ที่ไหนและทำไมจึงยาก". รายงานการประชุมวิชาการครั้งที่ 37 ว่าด้วยพื้นฐานของวิทยาการคอมพิวเตอร์หน้า 108–114 . doi : 10.1109/SFCS.1996.548469 . ISBN 0-8186-7594-2. S2CID 39024286 .

ลิงก์ภายนอก

ไวส์สไตน์, เอริค ดับเบิลยู. "วัฏจักรแฮมิลโทเนียน" . แมธเวิลด์ .
ทัวร์ออยเลอร์และวัฏจักรแฮมิลตัน

[1] Biggs, NL (1981), "TP Kirkman นักคณิตศาสตร์", The Bulletin of the London Mathematical Society , 13 (2): 97– 120, doi : 10.1112/blms/13.2.97 , MR 0608093.

[2] วัตกินส์, จอห์น เจ. (2004), "บทที่ 2: การเดินของอัศวิน", ทั่วทั้งกระดาน: คณิตศาสตร์ของปัญหาบนกระดานหมากรุก , สำนักพิมพ์มหาวิทยาลัยพรินซ์ตัน, หน้า 25–38 , ISBN 978-0-691-15498-5.

[3] เดอ รุยเตอร์, โยฮาน (2017) Hamilton Mazes – คู่มือสำหรับผู้เริ่มต้น

[4] ฟรีดแมน, เอริช. "เขาวงกตแบบแฮมิลตัน" . วังปริศนาของเอริช.เก็บถาวรจากต้นฉบับเมื่อวันที่ 16 เมษายน 2016. สืบค้นเมื่อ23 ตุลาคม 2025 .

[5] การ์ดเนอร์, เอ็ม. "เกมคณิตศาสตร์: เกี่ยวกับความคล้ายคลึงที่น่าทึ่งระหว่างเกมไอโคเซียนและหอคอยฮานอย" Sci. Amer. 196, 150–156, พฤษภาคม 1957

[6] Ghaderpour, E.; Morris, DW (2014). "กราฟ Cayley บนกลุ่มนิลโพเทนต์ที่มีกลุ่มย่อยคอมมิวเทเตอร์แบบวัฏจักรเป็นแฮมิลโทเนียน" Ars Mathematica Contemporanea . 7 (1): 55– 72. arXiv : 1111.6216 . doi : 10.26493/1855-3974.280.8d3 . S2CID 57575227 .

[7] Lucas, Joan M. (1987), "กราฟการหมุนของต้นไม้ไบนารีเป็นแบบแฮมิลโทเนียน", Journal of Algorithms , 8 (4): 503– 535, doi : 10.1016/0196-6774(87)90048-4

[8] Hurtado, Ferran ; Noy, Marc (1999), "กราฟของการแบ่งรูปสามเหลี่ยมของรูปหลายเหลี่ยมนูนและต้นไม้ของการแบ่งรูปสามเหลี่ยม", เรขาคณิตเชิงคำนวณ , 13 (3): 179– 188, doi : 10.1016/S0925-7721(99)00016-4

[9] Eric W. Weisstein . "กราฟเชื่อมต่อสองทาง" . Wolfram MathWorld.

[10] Balakrishnan, R.; Ranganathan, K. (2012), "Corollary 6.5.5", A Textbook of Graph Theory , Springer, หน้า 134, ISBN 9781461445296.

[11] Gould, Ronald J. (8 กรกฎาคม 2545). "ความก้าวหน้าเกี่ยวกับปัญหาแฮมิลโทเนียน – บทสำรวจ" (PDF) . มหาวิทยาลัยเอมอรี. เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 13 กรกฎาคม 2561. สืบค้นเมื่อ10 ธันวาคม 2555 .

[12] Rahman, MS; Kaykobad, M. (เมษายน 2548). "เกี่ยวกับวัฏจักรแฮมิลโทเนียนและเส้นทางแฮมิลโทเนียน". Information Processing Letters . 94 : 37–41 . doi : 10.1016/j.ipl.2004.12.002 .

[13] Moon, J.; Moser, L. (1963), "เกี่ยวกับกราฟสองส่วนแฮมิลโทเนียน", Israel Journal of Mathematics , 1 (3): 163– 165, doi : 10.1007/BF02759704 , MR 0161332 , S2CID 119358798

[14] Whitney, Hassler (1931), "ทฤษฎีบทเกี่ยวกับกราฟ", Annals of Mathematics , Second Series, 32 (2): 378– 390, doi : 10.2307/1968197 , JSTOR 1968197 , MR 1503003

[15] Tutte, WT (1956), "ทฤษฎีบทเกี่ยวกับกราฟระนาบ", Trans. Amer. Math. Soc. , 82 : 99– 116, doi : 10.1090/s0002-9947-1956-0081471-8

[16] Kogan, Grigoriy (1996). "การคำนวณค่าคงที่บนฟิลด์ที่มีลักษณะเฉพาะ 3: ที่ไหนและทำไมจึงยาก". รายงานการประชุมวิชาการครั้งที่ 37 ว่าด้วยพื้นฐานของวิทยาการคอมพิวเตอร์หน้า 108–114 . doi : 10.1109/SFCS.1996.548469 . ISBN 0-8186-7594-2. S2CID 39024286 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]