Quelle est la différence entre un chemin hamiltonien et un cycle hamiltonien ?
Le titre dit tout. J'ai vu des définitions confuses à ce sujet et j'apprécierais que quelqu'un puisse clarifier cela succinctement avec des définitions et des exemples.
Réponses
Le cycle commence et se termine au même sommet, mais pas le chemin.
Le chemin hamiltonien est un chemin dans un graphe non orienté ou orienté qui visite chaque sommet exactement une fois. Le cycle hamiltonien est un chemin hamiltonien qui est un cycle, et un cycle est une piste fermée dans laquelle le "premier sommet = dernier sommet" est le seul sommet répété.
Pour plus d'informationshttps://www.whitman.edu/mathematics/cgt_online/book/section05.03.html
https://en.wikipedia.org/wiki/Hamiltonian_path
Cycle hamiltonien = un cycle (chemin se terminant au même sommet qu'il commence) qui visite chaque sommet ($ n $bords);
Chemin hamiltonien = un chemin qui visite chaque sommet ($ n - 1 $bords).
Dans le graphe représenté par la matrice d'adiacence :
01001
10100
01010
00101
10010
Nous avons 1 - 2 - 3 - 4 - 5
ou des 1 - 5 - 4 - 3 - 2
chemins hamiltoniens. Aussi, 1 - 2 - 3 - 4 - 5 - 1
est un cycle hamiltonien.