Apa perbedaan antara Jalur Hamiltonian dan Siklus Hamiltonian?

Aug 18 2020

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

7 Tereza Aug 18 2020 at 20:52

Siklus dimulai dan diakhiri di simpul yang sama, tetapi jalurnya tidak.

1 SanjibanSengupta Aug 19 2020 at 05:18

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

1 ȘtefanDumitrescu Aug 18 2020 at 21:26

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 - 5atau 1 - 5 - 4 - 3 - 2jalur Hamiltonian. Juga, 1 - 2 - 3 - 4 - 5 - 1adalah siklus Hamiltonian.