problème du dodécaèdre de Hamilton
Le problème du dodécaèdre de Hamilton consiste à trouver un chemin fermé qui suit uniquement les arêtes d'un dodécaèdre régulier, passe exactement une fois par chacun de ses 20 sommets, puis revient au sommet de départ. Autrement dit, on cherche un cycle hamiltonien dans le graphe de ses sommets et de ses arêtes ; le dessiner à plat sans changer les voisinages facilite la recherche et la vérification du parcours.
Sommaire
Ce que vous allez apprendre
- Définir un cycle hamiltonien et un graphe hamiltonien.
- Suivre un cycle complet sur les 20 sommets du graphe du dodécaèdre.
- Vérifier la fermeture, l'adjacence et l'absence de sommet répété.
- Distinguer la visite des sommets du parcours de toutes les arêtes.
En clair
Imaginez les 20 sommets d'un dodécaèdre comme 20 étapes reliées par ses arêtes. Le défi est de partir d'une étape, de suivre les arêtes sans visiter deux fois le même sommet, puis de revenir au point de départ après avoir vu les 20 sommets.
Pour chercher ce trajet, il est plus commode de dessiner les sommets et leurs liaisons à plat. La forme du solide change, mais pas les voisinages : chaque trait du dessin représente toujours une arête autorisée.
Définition
Dans un graphe, un cycle hamiltonien est un parcours fermé qui emprunte des arêtes du graphe et visite chacun de ses sommets exactement une fois. Le sommet choisi pour commencer est aussi celui où le parcours se ferme ; sa répétition finale sert seulement à signaler cette fermeture. Un graphe est dit hamiltonien lorsqu'il contient au moins un tel cycle.
Pour le problème du dodécaèdre, les 20 sommets du solide deviennent les sommets du graphe, et les arêtes du solide deviennent ses liaisons autorisées. Une représentation plane conserve ces relations de voisinage tout en rendant le trajet plus lisible. La question est donc une question d'existence : peut-on choisir un cycle qui couvre les 20 sommets sans sortie du graphe ni seconde visite ?
Ce jeu, inventé par Hamilton vers 1850, compte parmi les premières formulations d'un problème hamiltonien. Pour un graphe général, décider si un cycle hamiltonien existe est un problème NP-complet. On ne connaît pas de critère général et efficace en temps polynomial qui caractériserait tous les graphes hamiltoniens.
Un exemple, pas à pas
On utilise une représentation plane du dodécaèdre. Ses quatre couronnes de sommets sont notées A, B, C et D ; les indices vont de 0 à 4.
Données. Le graphe possède 20 sommets et 30 arêtes. Deux sommets consécutifs de la liste proposée doivent être reliés par une arête, y compris le dernier et le premier.
1. Suivre A0, A1, A2, A3, A4, B4.
2. Continuer par C3, B3, C2, B2, C1, B1, C0.
3. Rejoindre D0, D1, D2, D3, D4, puis C4 et B0.
4. Fermer le parcours par l'arête B0–A0. Le tracé rouge rend ce contrôle visible.
2. Continuer par C3, B3, C2, B2, C1, B1, C0.
3. Rejoindre D0, D1, D2, D3, D4, puis C4 et B0.
4. Fermer le parcours par l'arête B0–A0. Le tracé rouge rend ce contrôle visible.
Le contrôle est refaisable : les 20 noms avant le retour sont distincts, chaque paire successive correspond à une arête noire du graphe, et la dernière arête revient à A0. Le parcours rouge est donc un cycle hamiltonien.
En pratique
Pour résoudre le jeu, on dessine d'abord le graphe à plat, puis on marque les sommets déjà visités. À chaque étape, on ne conserve qu'une arête menant à un sommet encore libre, tout en gardant possible un retour final au départ.
Pour vérifier une proposition, on compte les sommets distincts avant de regarder l'allure du dessin. S'il y en a 20, on contrôle ensuite chaque liaison successive et l'arête de fermeture. Cette procédure évite de prendre une courbe visuellement fermée pour une solution valide.
Si la consigne demande au contraire de parcourir toutes les arêtes, le critère hamiltonien n'est pas le bon : ici, ce sont les sommets qui doivent être couverts une fois. Le mot décisif de l'énoncé est donc « sommets ».
À ne pas confondre
Cycle hamiltonien et parcours de toutes les arêtes. Le premier impose de visiter chaque sommet exactement une fois ; il n'impose pas d'utiliser toutes les arêtes. Dans l'exemple, le cycle retient 20 des 30 arêtes du graphe : les 10 autres restent disponibles, mais inutilisées.
Cycle hamiltonien et graphe hamiltonien. Le cycle est un parcours particulier. Le graphe est qualifié d'hamiltonien dès qu'il contient au moins un tel parcours. La liste de l'exemple est un cycle ; le graphe du dodécaèdre qui le contient est hamiltonien.
Limites et pièges
Le retour au départ n'est pas une seconde visite. Dans l'écriture d'un cycle, le premier sommet réapparaît à la fin pour matérialiser la fermeture. Il faut compter les sommets avant ce retour : l'exemple en compte bien 20 distincts.
Un croisement dessiné ne crée pas un sommet. Seuls les sommets explicitement marqués et les arêtes qui les relient appartiennent au graphe. Pour éviter cette erreur de lecture, on préfère une représentation plane du dodécaèdre.
Le dessin plan ne garantit pas une solution pour tout graphe. Il facilite la recherche sur le dodécaèdre, mais il ne fournit pas un critère universel d'existence. Pour un graphe général, cette décision est NP-complète.
Une visite incomplète reste invalide. Une boucle fermée qui oublie ne serait-ce qu'un des 20 sommets n'est pas hamiltonienne. Il faut comparer la liste du parcours à la liste entière des sommets, pas seulement constater que la ligne revient à son point de départ.
Pour aller plus loin
Le problème illustre le passage d'un solide à son graphe : la longueur et l'orientation des traits peuvent changer, tandis que les sommets reliés doivent rester les mêmes. Cette invariance permet de chercher le cycle sur une représentation plane.
La fiche dodécaèdre permet de revenir au solide régulier qui porte les 20 sommets du jeu et à sa structure géométrique.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres