อะไรคือความแตกต่างระหว่าง Hamiltonian Path และ Hamiltonian Cycle?

Aug 18 2020

ชื่อเรื่องบอกทุกอย่าง ฉันเคยเห็นคำจำกัดความที่สับสนเกี่ยวกับเรื่องนี้และจะขอบคุณถ้ามีใครซักคนสรุปคำจำกัดความและตัวอย่างได้อย่างกระชับ

คำตอบ

7 Tereza Aug 18 2020 at 20:52

วงจรเริ่มต้นและสิ้นสุดในจุดยอดเดียวกัน แต่เส้นทางไม่ได้

1 SanjibanSengupta Aug 19 2020 at 05:18

เส้นทางแฮมิลตันเป็นเส้นทางในกราฟที่ไม่มีทิศทางหรือกำหนดทิศทางซึ่งไปที่จุดยอดแต่ละจุดทุกครั้งที่วัฏจักรแฮมิลตันคือเส้นทางแฮมิลตันที่เป็นวัฏจักรและวัฏจักรคือเส้นทางปิดซึ่ง "จุดยอดแรก = จุดยอดสุดท้าย" เป็นจุดยอดเดียวที่เป็น ซ้ำ
สำหรับข้อมูลเพิ่มเติมhttps://www.whitman.edu/mathematics/cgt_online/book/section05.03.html
https://en.wikipedia.org/wiki/Hamiltonian_path

1 ȘtefanDumitrescu Aug 18 2020 at 21:26

วัฏจักรแฮมิลตัน = วัฏจักร (เส้นทางที่ลงท้ายด้วยจุดยอดเดียวกันเริ่มต้น) ที่เข้าชมทุกจุดยอด ($ 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เป็นวงจรแฮมิลตัน