อะไรคือความแตกต่างระหว่าง Hamiltonian Path และ Hamiltonian Cycle?
ชื่อเรื่องบอกทุกอย่าง ฉันเคยเห็นคำจำกัดความที่สับสนเกี่ยวกับเรื่องนี้และจะขอบคุณถ้ามีใครซักคนสรุปคำจำกัดความและตัวอย่างได้อย่างกระชับ
คำตอบ
วงจรเริ่มต้นและสิ้นสุดในจุดยอดเดียวกัน แต่เส้นทางไม่ได้
เส้นทางแฮมิลตันเป็นเส้นทางในกราฟที่ไม่มีทิศทางหรือกำหนดทิศทางซึ่งไปที่จุดยอดแต่ละจุดทุกครั้งที่วัฏจักรแฮมิลตันคือเส้นทางแฮมิลตันที่เป็นวัฏจักรและวัฏจักรคือเส้นทางปิดซึ่ง "จุดยอดแรก = จุดยอดสุดท้าย" เป็นจุดยอดเดียวที่เป็น ซ้ำ
สำหรับข้อมูลเพิ่มเติมhttps://www.whitman.edu/mathematics/cgt_online/book/section05.03.html
https://en.wikipedia.org/wiki/Hamiltonian_path
วัฏจักรแฮมิลตัน = วัฏจักร (เส้นทางที่ลงท้ายด้วยจุดยอดเดียวกันเริ่มต้น) ที่เข้าชมทุกจุดยอด ($ n $ขอบ);
เส้นทางแฮมิลตัน = เส้นทางที่เยี่ยมชมทุกจุดยอด ($ n - 1 $ ขอบ)
ในกราฟแสดงโดยเมทริกซ์ของ adiacence:
01001
10100
01010
00101
10010
เรามี1 - 2 - 3 - 4 - 5
หรือ1 - 5 - 4 - 3 - 2
เส้นทางแฮมิลตัน นอกจากนี้ยัง1 - 2 - 3 - 4 - 5 - 1
เป็นวงจรแฮมิลตัน