Vérificateur de Chemin Hamiltonien

Vérificateur de Chemin Hamiltonien

Le Vérificateur de Chemin Hamiltonien détermine si un graphe contient un chemin hamiltonien — une séquence qui visite chaque sommet exactement une fois — ou un cycle hamiltonien, qui revient en plus au sommet de départ. Il combine des pré-vérifications structurelles rapides (connectivité, conditions préalables de degré, théorème de Dirac, théorème d'Ore) avec une recherche par retour sur trace (backtracking) optimisée par l'heuristique de Warnsdorff, et visualise le chemin témoin avec une animation étape par étape.

Qu'est-ce qu'un chemin hamiltonien ?

Étant donné un graphe G = (V, E) à n sommets, un chemin hamiltonien est une séquence ordonnée v₁, v₂, …, v_n de tous les sommets telle que chaque paire consécutive (v_i, v_i+1) est une arête de G, et chaque sommet apparaît exactement une fois. Si, de plus, (v_n, v₁) est une arête, la séquence est un cycle hamiltonien.

Le problème tire son nom de William Rowan Hamilton, qui inventa en 1857 le jeu icôsien — un casse-tête demandant au joueur de trouver un cycle visitant chaque sommet d'un dodécaèdre régulier exactement une fois.

Pourquoi c'est difficile : la NP-complétude

Le problème de décision du chemin hamiltonien et celui du cycle hamiltonien sont tous deux NP-complets (Karp, 1972). À moins que P = NP, il n'existe aucun algorithme en temps polynomial capable de résoudre chaque instance. Dans le pire des cas, le retour sur trace explore un arbre de recherche d'une taille allant jusqu'à (n−1)! pour un cycle. C'est pourquoi le calculateur limite l'entrée à 20 sommets — une faible augmentation polynomiale de n produit une augmentation explosive du temps d'exécution.

En pratique, l'heuristique de Warnsdorff (conçue à l'origine par Heinrich Warnsdorff en 1823 pour le problème du cavalier) rend la recherche considérablement plus rapide sur les graphes structurés : à chaque étape, l'algorithme prolonge le chemin actuel vers le voisin non visité ayant le plus petit nombre de voisins non visités restants. Cette règle gloutonne empêche la recherche de s'enfermer dans une impasse et trouve souvent un parcours hamiltonien sans aucun retour sur trace sur les graphes bien structurés.

Conditions nécessaires — Rejet rapide

Avant de lancer une recherche coûteuse, le calculateur rejette les graphes qui ne peuvent pas contenir de chemin hamiltonien :

• Connectivité. Un chemin hamiltonien doit visiter chaque sommet, le graphe doit donc posséder exactement une composante connexe. Pour les graphes orientés, une connectivité faible (ignorant le sens des flèches) est requise.
• Degré (non orienté). Au plus deux sommets peuvent avoir un degré 1 — ce sont les seuls candidats pour les extrémités du chemin. Pour un cycle hamiltonien, chaque sommet doit avoir un degré d'au moins 2.
• Degré (orienté). Pour un chemin hamiltonien, au plus un sommet peut avoir un degré entrant de 0 (le départ) et au plus un peut avoir un degré sortant de 0 (la fin). Pour un cycle hamiltonien, chaque sommet doit avoir un degré entrant ≥ 1 et un degré sortant ≥ 1.

Ces règles permettent de rejeter de nombreuses entrées sans issue en temps linéaire, évitant ainsi des efforts inutiles de backtracking.

Conditions suffisantes — Théorèmes classiques

Plusieurs théorèmes classiques donnent des conditions suffisantes (mais pas nécessaires) garantissant un cycle hamiltonien dans les graphes simples non orientés. Si l'une de ces conditions s'applique, le calculateur marque le résultat comme "GARANTIT" sans même lancer la recherche — bien qu'il affiche tout de même un cycle témoin.

Théorème de Dirac (1952)

Si G est un graphe simple non orienté à n ≥ 3 sommets et que chaque sommet a un degré au moins égal à n / 2, alors G possède un cycle hamiltonien.

Théorème d'Ore (1960)

Si pour chaque paire de sommets non adjacents u et v, nous avons deg(u) + deg(v) ≥ n, alors G possède un cycle hamiltonien. La condition d'Ore est strictement plus faible que celle de Dirac, donc Ore implique Dirac.

L'échec des conditions de Dirac ou d'Ore ne signifie pas que le graphe ne possède pas de cycle hamiltonien — de nombreux graphes ne satisfont ni l'un ni l'autre tout en en contenant un (par exemple, un cycle simple à n sommets a un degré minimum de 2, bien en dessous de n/2 pour de grandes valeurs de n).

L'algorithme de recherche interne

Lorsque les pré-vérifications ne permettent pas de trancher, le calculateur lance une recherche par retour sur trace sur la représentation d'adjacence du graphe. Tactiques clés :

1. Masque de bits pour l'ensemble visité. Les sommets visités sont stockés sous forme de masque de bits (test d'appartenance rapide en O(1) jusqu'à 20 sommets).
2. Heuristique de Warnsdorff. À chaque extension, les voisins sont essayés dans l'ordre de leur degré non visité restant (le plus petit en premier), imitant un ordre à "faible branchement".
3. Sélection de la racine. Pour un cycle hamiltonien, un seul sommet de départ est nécessaire (les cycles sont invariants par rotation). Pour un chemin hamiltonien, les départs sont essayés par ordre croissant de degré sortant — les positions les plus rares en premier.
4. Budget d'étapes. Une limite stricte empêche les instances pathologiques de s'exécuter indéfiniment ; l'interface signale le verdict comme "expiré" si le budget est épuisé.

Hamiltonien vs Eulérien

Il est facile de confondre les problèmes hamiltoniens et eulériens — ils semblent similaires mais sont fondamentalement différents :

Formats d'entrée pris en charge

Liste d'arêtes

Une arête par ligne, ou séparée par des virgules. Séparateurs pris en charge : A-B, A B, A,B, A--B, A->B, A<-B. Utilisez -> pour forcer une interprétation orientée.

Matrice d'adjacence

Matrice carrée de valeurs 0/1, une ligne par ligne, séparée par des espaces ou des virgules. Fournissez des étiquettes facultatives dans le champ Étiquettes de matrice ; sinon, A, B, C... sont utilisés automatiquement.

Comment utiliser ce vérificateur

1. Choisissez un format d'entrée — Liste d'arêtes pour les petits graphes écrits à la main, Matrice d'adjacence pour les copier-coller de code ou de manuels.
2. Collez votre graphe dans la zone de texte. Pour l'entrée matricielle, fournissez éventuellement des étiquettes de sommets.
3. Choisissez quoi vérifier : Chemin uniquement, Cycle uniquement, ou Les deux en une seule fois.
4. Sélectionnez le type de graphe — La détection automatique déduit l'orientation à partir du style de flèche (->) ou de la symétrie de la matrice.
5. Cliquez sur Vérifier l'Hamiltonien. La page de résultats affiche un verdict, la pré-vérification des conditions nécessaires, les tests de conditions suffisantes de Dirac / Ore, le chemin témoin (s'il existe) et une visualisation interactive.
6. Rejouez le témoin à l'aide des commandes Lecture / Étape. Observez le chemin s'allumer arête par arête sur le graphe.

Exemple pratique — Le graphe de Petersen

Le célèbre graphe de Petersen (10 sommets, 15 arêtes, 3-régulier) est un exemple classique de graphe possédant un chemin hamiltonien mais aucun cycle hamiltonien. Collez ceci dans le champ de liste d'arêtes et cliquez sur Vérifier :

Le vérificateur confirme : chemin hamiltonien trouvé (ex : 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3), mais la recherche exhaustive ne trouve aucun moyen de fermer la boucle — un résultat prouvé pour la première fois dans les années 1890.

Applications courantes

• Routage et problème du voyageur de commerce (TSP) — chaque tour TSP est un cycle hamiltonien dans le graphe complet pondéré.
• Assemblage de génome — la reconstruction d'une séquence d'ADN à partir de lectures chevauchantes peut être modélisée comme un chemin hamiltonien dans un graphe de chevauchement.
• Conception de circuits — ordonner les broches sur un PCB pour un câblage de longueur minimale.
• IA de jeu et résolution de casse-tête — parcours du cavalier sur un échiquier, jeu icôsien.
• Ordonnancement — séquençage de tâches de sorte que chacune puisse passer de manière réalisable à la suivante.
• Enseignement de la combinatoire — illustration de la NP-complétude avec de petits exemples résolvables à la main.

Foire aux questions

Qu'est-ce qu'un chemin hamiltonien ?

Un chemin hamiltonien est un parcours dans un graphe qui visite chaque sommet exactement une fois. Il porte le nom de William Rowan Hamilton, qui a étudié le problème sur le graphe du dodécaèdre en 1857. Décider si un tel chemin existe est un problème NP-complet, donc aucun algorithme connu ne le résout en temps polynomial pour tous les graphes.

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

Un cycle hamiltonien est un chemin hamiltonien qui revient à son sommet de départ, formant une boucle fermée qui visite chaque sommet exactement une fois. Chaque cycle hamiltonien contient un chemin hamiltonien (il suffit de supprimer l'arête de fermeture), mais l'inverse n'est pas vrai : de nombreux graphes ont un chemin hamiltonien mais pas de cycle hamiltonien.

Que dit le théorème de Dirac ?

Le théorème de Dirac (1952) stipule que tout graphe simple non orienté à n ≥ 3 sommets dans lequel chaque sommet a un degré d'au moins n/2 contient un cycle hamiltonien. C'est une condition suffisante mais pas nécessaire : de nombreux graphes qui n'atteignent pas le seuil de Dirac ont tout de même des cycles hamiltoniens.

Que dit le théorème d'Ore ?

Le théorème d'Ore (1960) stipule que si, pour chaque paire de sommets non adjacents u et v dans un graphe simple à n ≥ 3 sommets, la somme de leurs degrés est au moins égale à n, alors le graphe possède un cycle hamiltonien. La condition d'Ore est plus faible que celle de Dirac, donc le théorème d'Ore s'applique chaque fois que le théorème de Dirac s'applique.

Pourquoi la recherche est-elle limitée à 20 sommets ?

Les problèmes de décision de chemin et de cycle hamiltoniens sont NP-complets. Le temps d'exécution dans le pire des cas augmente de manière exponentielle avec le nombre de sommets. Avec l'élagage et l'heuristique de Warnsdorff, le calculateur traite rapidement de nombreux petits graphes jusqu'à 20 sommets, mais les instances complexes peuvent expirer. Au-delà de 20 sommets, vous devriez utiliser des solveurs spécialisés tels que Concorde ou des formulations de programmation en nombres entiers.

Qu'est-ce que l'heuristique de Warnsdorff ?

La règle de Warnsdorff, proposée en 1823 pour le problème du cavalier, stipule qu'à chaque étape, vous devez visiter le sommet suivant qui possède le moins de voisins non visités restants. Cette règle d'apparence gloutonne élague considérablement l'arbre de recherche en pratique et trouve souvent des chemins hamiltoniens sans aucun retour sur trace sur les graphes réguliers.

Cet outil trouve-t-il tous les chemins hamiltoniens ?

Non — il trouve un seul chemin ou cycle témoin lorsqu'il en existe un. Compter le nombre total de chemins hamiltoniens est en soi un problème #P-complet et bien plus complexe que le problème de décision. Pour l'énumération, des outils spécialisés ou des solveurs de programmation en nombres entiers sont plus appropriés.

Lectures complémentaires

• Graphe hamiltonien — Wikipédia
• Problème du chemin hamiltonien — Wikipédia
• Théorème de Dirac sur les cycles hamiltoniens — Wikipédia (EN)
• Théorème d'Ore — Wikipédia
• Règle de Warnsdorff — Wikipédia

Opérations mathématiques avancées:

• Calculateur de Matrice d'Adjacence Nouveau
• Calculatrice d'Antilogarithme
• Calculatrice de la fonction bêta
• Calculateur de Coefficient Binomial
• Calculatrice de distribution binomiale
• Calculatrice de Bit Populaire
• Simplificateur d'Algèbre de Boole Nouveau
• Calculateur du Théorème Central Limite
• Calculatrice du Théorème des Restes Chinois
• Calculatrice de Combinaison Populaire
• Calculatrice de Fonction d'Erreur Complémentaire
• Calculatrice de Nombres Complexes
• Calculatrice de fractions continues
• Calculateur de Dérangement (Sous-factorielle)
• Calculateur de plus court chemin de Dijkstra
• Calculatrice d'Entropie
• Calculatrice de fonction d'erreur
• Calculatrice de la fonction indicatrice d'Euler
• Calculatrice de désintégration exponentielle
• Calculatrice de croissance exponentielle
• Calculatrice d'intégrale exponentielle
• Calculatrice des Exposants (Haute Précision) Populaire
• Calculatrice de l'Algorithme Euclidien Étendu
• Calculatrice Factorielle
• Calculatrice de Fonction Gamma
• Calculateur de Nombre d'Or
• Calculateur de Coloration de Graphes Nouveau
• Validateur de séquence de degrés de graphe
• Calculateur d'Ordre en Théorie des Groupes Nouveau
• Calculatrice de demi-vie
• Vérificateur de Chemin Hamiltonien Nouveau
• Calculateur d'Inclusion-Exclusion Nouveau
• Solveur de Tableau de Karnaugh (K-Map) Nouveau
• Solveur de Programmation Linéaire Nouveau
• Calculateur d'état stationnaire de chaîne de Markov
• Calculateur d'arbre couvrant minimum
• Calculateur d'Exponentiation Modulaire Nouveau
• Calculatrice de l'Inverse Multiplicatif Modulaire
• Calculateur de Distribution Binomiale Négative Nouveau
• Calculateur de Flot Maximal dans un Réseau Nouveau
• Calculatrice du Taux de Croissance en Pourcentage Populaire
• Calculatrice de permutation
• Calculateur de Permutations avec Répétition Nouveau
• Calculateur du principe des tiroirs
• Vérificateur de Graphe Planaire Nouveau
• Calculatrice de Distribution de Poisson
• Calculatrice des racines de polynômes avec étapes détaillées
• Calculateur de Racine Primitive
• Calculatrice de probabilité
• Calculatrice de Distribution de Probabilité
• Calculatrice de Proportion
• Calculatrice de Formule Quadratique Populaire
• Calculateur d’Anneaux et de Corps Nouveau
• Calculateur d'Arrondi Nouveau
• Calculatrice Scientifique
• Calculatrice de notation scientifique
• Calculateur de Théorie des Ensembles
• Calculateur de Chiffres Significatifs Nouveau
• Solveur du Problème des Mariages Stables Nouveau
• Calculateur de Nombres de Stirling
• Calculatrice de Somme de Cubes
• Calculatrice de la somme des entiers positifs
• Calculatrice de la somme des carrés
• Calculateur de Tri Topologique Nouveau
• Solveur du Voyageur de Commerce (TSP) Nouveau
• Générateur de table de vérité
• Générateur de Diagramme de Venn (3 Ensembles)