Le problème du cycle hamiltonien (HC) consiste à trouver un cycle passant par tous les sommets d'un graphe non orienté donné. Le problème des vendeurs ambulants (TSP) consiste à trouver un cycle qui passe par tous les sommets d'un graphique pondéré sur les bords et minimise la distance totale mesurée par la somme des poids des bords du cycle. HC est un cas particulier de TSP, et les deux sont connus pour être NP-complets [Garey & Johnson]. (Voir les liens ci-dessus pour plus de détails et des variantes de ces problèmes.)
Existe-t-il des classes de graphes étudiées sur lesquelles le problème du cycle hamiltonien peut être résolu en temps polynomial via un algorithme non trivial , mais le problème du voyageur de commerce est NP-difficile?
Il n'est pas trivial d'exclure des classes telles que la classe de graphiques complets, où un cycle hamiltonien est garanti d'exister et peut être trouvé facilement, ou généralement des classes de graphiques où un HC est toujours garanti d'exister.
Que diriez - vous des graphiques complets ? Étant donné que TSP peut toujours être réduit à une instance sur des graphiques complets (en ajoutant des distances appropriées entre les non-arêtes), il est toujours difficile de résoudre le TSP sur des graphiques complets. Mais tout graphique complet est hamiltonien.
la source
Il existe de nombreuses classes infinies de graphes connus pour avoir des circuits hamiltoniens. Deux classes particulièrement intéressantes sont les n-cubes et les graphes Halin. Une façon de penser les graphes de Halin est d'incorporer un arbre avec au moins 3 sommets et qui n'a pas de sommets de valence deux dans le plan, puis de passer un circuit simple à travers les sommets 1-valent de l'arbre.
http://en.wikipedia.org/wiki/Halin_graph
Ces graphiques sont connus pour avoir un HC et en fait ils sont soit pancycliques (circuits de toutes longueurs) ou manquent exactement d'une longueur de circuit qui doit être de longueur paire.
la source