Le problème porte le nom du mathématicien irlandais William Rowan Hamilton, bien qu'il ait été étudié un an plus tôt (en 1856) par Thomas Kirkman. En 1857, Hamilton invente et commercialise un casse-tête appelé le Jeu Icosien.
Il est très fréquent de confondre les cycles eulériens et hamiltoniens. Pourtant, mathématiquement, un monde les sépare :
- Cycle d'Euler (visiter toutes les arêtes) : Problème "facile" Classe P. Il suffit de vérifier que tous les sommets sont de degré pair. Cela se fait en une fraction de seconde.
- Cycle de Hamilton (visiter tous les sommets) : Problème "difficile" NP-complet. Il n'existe aucun critère local simple (comme le degré des sommets) permettant de savoir si un tel cycle existe.
Note : Bien qu'il n'y ait pas de condition nécessaire et suffisante simple, il existe des conditions suffisantes (ex: Théorème de Dirac : si chaque sommet a un degré $d \ge n/2$, alors le graphe est hamiltonien).
Incarnez la machine non-déterministe ! Choisissez un point de départ, et cliquez sur les sommets adjacents pour construire votre chemin.
Astuce : Cliquez sur le sommet où vous vous trouvez (en jaune) pour annuler votre dernier déplacement.
Vous pouvez déplacer les sommets pour mieux observer certaines parties du graphe.
L'algorithme parcourt l'arbre des possibles $\mathcal{O}(n!)$. S'il échoue, il prouve mathématiquement l'absence de cycle.