problème du dodécaèdre de Hamilton

COMBINATOIRE

Le problème est de trouver un chemin passant une fois et une seule par chacun des 20 sommets d’un dodécaèdre et revenant au point de départ, en restant sur les arêtes du dodécaèdre.

Inventé par Hamilton vers 1850, ce jeu a des développements en théorie des graphes. On le résout en remplaçant le dodécaèdre par un graphe planaire équivalent. On appelle problèmes hamiltoniens les problèmes de chemins passant une fois et une seule par tous les sommets d’un graphe.

Un cycle hamiltonien est un cycle passant une fois et une seule par tous les sommets. Un graphe hamiltonien est un graphe qui contient au moins un tel cycle.