Quelle est la différence entre un chemin hamiltonien et un cycle hamiltonien ?

Aug 18 2020

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

7 Tereza Aug 18 2020 at 20:52

Le cycle commence et se termine au même sommet, mais pas le chemin.

1 SanjibanSengupta Aug 19 2020 at 05:18

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

1 ȘtefanDumitrescu Aug 18 2020 at 21:26

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 - 5ou des 1 - 5 - 4 - 3 - 2chemins hamiltoniens. Aussi, 1 - 2 - 3 - 4 - 5 - 1est un cycle hamiltonien.