Apa perbedaan antara Jalur Hamiltonian dan Siklus Hamiltonian?
Judulnya menjelaskan semuanya. Saya telah melihat definisi yang membingungkan tentang ini, dan akan menghargai jika seseorang dapat secara ringkas menjelaskan ini dengan definisi dan contoh.
Jawaban
Siklus dimulai dan diakhiri di simpul yang sama, tetapi jalurnya tidak.
Lintasan Hamiltonian adalah lintasan dalam graf tak berarah atau berarah yang mengunjungi setiap simpul tepat sekali siklus Hamiltonian adalah lintasan Hamiltonian yang merupakan sebuah siklus, dan sebuah siklus adalah jalur tertutup di mana “simpul pertama = simpul terakhir” adalah satu-satunya simpul yang ada ulang.
Untuk info lebih lanjuthttps://www.whitman.edu/mathematics/cgt_online/book/section05.03.html
https://en.wikipedia.org/wiki/Hamiltonian_path
Siklus Hamiltonian = sebuah siklus (jalur yang diakhiri dengan simpul yang sama yang dimulainya) yang mengunjungi setiap simpul ($ n $tepi);
Jalur Hamiltonian = jalur yang mengunjungi setiap titik sudut ($ n - 1 $ tepi).
Dalam grafik yang diwakili oleh matriks adiacence:
01001
10100
01010
00101
10010
Kami memiliki 1 - 2 - 3 - 4 - 5
atau 1 - 5 - 4 - 3 - 2
jalur Hamiltonian. Juga, 1 - 2 - 3 - 4 - 5 - 1
adalah siklus Hamiltonian.