Qu'est-ce qu'un chemin hamiltonien ?

C'est un chemin à travers un graphe qui visite chaque sommet exactement une fois, en n'utilisant que des arêtes existant dans le graphe — il n'a pas besoin de revenir à son point de départ (cela en ferait plutôt un cycle hamiltonien).

Pourquoi est-il difficile de trouver un chemin hamiltonien ?

Le problème du chemin hamiltonien est NP-complet, ce qui signifie qu'aucun algorithme connu ne le résout de façon nettement plus rapide qu'en essayant des combinaisons d'ordonnancements, et le nombre d'ordonnancements possibles croît de façon factorielle avec le nombre de nœuds.

Pourquoi cette calculatrice est-elle limitée à 10 nœuds ?

La recherche par retour sur trace explore un espace de recherche qui peut croître de façon factorielle dans le pire des cas. Dix nœuds gardent cette recherche confortablement rapide pour un outil basé sur navigateur, tout en couvrant encore la plupart des exemples de graphes saisis à la main que les gens veulent vérifier.

Comment fonctionne la recherche par retour sur trace ?

Elle construit un chemin nœud par nœud, s'étendant toujours vers un voisin non visité ; si elle atteint une impasse où aucun voisin non visité n'est disponible, elle revient en arrière (annule la dernière étape) et essaie un voisin différent, répétant depuis chaque nœud de départ possible.

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

Un chemin hamiltonien doit seulement visiter chaque sommet une fois ; un cycle hamiltonien exige en plus que le chemin revienne à son sommet de départ, formant une boucle fermée — les deux sont NP-complets à détecter.

Tout graphe a-t-il un chemin hamiltonien ?

Non — de nombreux graphes, surtout épars ou déconnectés, n'en ont aucun. Un graphe déconnecté ne peut jamais avoir de chemin hamiltonien, car le chemin devrait sauter entre des composantes sans arête à utiliser.

En quoi cela diffère-t-il de la Calculatrice d'Arbre Couvrant Minimal ?

Un arbre couvrant minimal connecte chaque nœud à l'aide d'une structure arborescente (qui peut se ramifier), tandis qu'un chemin hamiltonien est une seule ligne non ramifiée qui visite chaque nœud exactement une fois — une exigence beaucoup plus restrictive.

Où le problème du chemin hamiltonien est-il utilisé dans la vie réelle ?

Il est étroitement lié au problème du voyageur de commerce et apparaît dans la planification d'itinéraires, le séquençage de l'ADN (assemblage de fragments), et des problèmes de puzzle comme le parcours du cavalier sur un échiquier.

Vérificateur de Chemin Hamiltonien — Trouvez un Chemin qui Visite Chaque Nœud Exactement Une Fois

Notre Vérificateur de Chemin Hamiltonien recherche un chemin à travers un graphe qui visite chaque nœud exactement une fois, en essayant chaque nœud de départ possible et en revenant sur trace à travers les routes possibles, votre graphe étant saisi sous forme de simple liste d'arêtes textuelle (par ex. A-B, B-C, C-D).

Réponse rapide

Saisissez votre graphe sous forme de liste d'arêtes (jusqu'à 10 nœuds) pour rechercher instantanément un chemin hamiltonien — un itinéraire visitant chaque nœud exactement une fois — via retour sur trace.

Arêtes (séparées par des virgules)

Saisissez des arêtes sous la forme NœudA-NœudB, par ex. A-B, B-C, C-D. Maximum 10 nœuds.

Comment utiliser Vérificateur de Chemin Hamiltonien — Visitez Chaque Nœud Une Fois en Ligne

1
Saisissez votre graphe sous forme de liste d'arêtes séparées par des virgules, par ex. A-B, B-C, C-D.
2
Cliquez sur 'Calculer' pour rechercher un chemin hamiltonien.
3
Consultez le chemin trouvé, ou la confirmation qu'aucun n'existe.

Pourquoi utiliser Vérificateur de Chemin Hamiltonien — Visitez Chaque Nœud Une Fois en Ligne ?

Un chemin hamiltonien visite chaque sommet d'un graphe exactement une fois — contrairement à un chemin eulérien, qui consiste à visiter chaque arête, il s'agit ici de visiter chaque nœud. Déterminer si un tel chemin existe est NP-complet en général, ce qui signifie qu'aucun algorithme connu n'est nettement plus rapide que d'essayer systématiquement des possibilités, donc cette calculatrice utilise une recherche par retour sur trace : construire un chemin nœud par nœud, et revenir en arrière chaque fois qu'une impasse est atteinte, en essayant chaque nœud de départ possible. Comme l'espace de recherche croît de façon factorielle avec la taille du graphe, cette calculatrice est délibérément limitée à 10 nœuds maximum, où la recherche exhaustive par retour sur trace se termine encore instantanément.

Questions fréquentes

Outils similaires

Solveur du Voyageur de Commerce — DP Exacte de Held-Karp en Ligne

Trouvez l'itinéraire aller-retour le plus court exact visitant chaque ville exactement une fois, à l'aide de l'algorithme de programmation dynamique de Held-Karp. Calculateur gratuit, jusqu'à 12 villes.

Calculatrice de Tri Topologique — Algorithme de Kahn en Ligne

Trouvez un ordre topologique valide pour un graphe orienté à l'aide de l'algorithme de Kahn, ou détectez qu'aucun ordre n'existe à cause d'un cycle. Calculatrice gratuite avec une simple saisie de liste d'arêtes.

Calculatrice d'Arbre Couvrant Minimal — Algorithme de Kruskal en Ligne

Trouvez l'arbre couvrant minimal d'un graphe pondéré à l'aide de l'algorithme de Kruskal. Calculatrice gratuite avec une simple saisie de liste d'arêtes et détection de cycles par union-find.