chemin hamiltonien

chemin hamiltonien

Chemin qui passe une et une seule fois par chacun des sommets d’un graphe orienté.

Exemple

Dans ce graphe orienté, le chemin reliant dans l’ordre les sommets A, B, C, D et E est un chemin hamiltonien de longueur 5.  Il est formé des arcs abcd et e.

Noter qu’il n’est pas nécessaire que le chemin passe par toutes les arêtes du graphe.  C’est comme la tournée du facteur qui doit passer par toutes les adresses de son parcours de travail.