Dans l’article précédent, nous avons vu comment Euler avait transformé le problème des ponts de Königsberg en une question de structure : peut-on parcourir toutes les arêtes d’un réseau une seule fois ? Avec Hamilton, le regard se déplace. Il ne s’agit plus de franchir tous les chemins, mais de visiter tous les sommets. Ce déplacement du regard trouve une forme particulièrement élégante dans le jeu icosien, imaginé par William Rowan Hamilton autour du dodécaèdre.
Ce glissement peut sembler minime. Il est pourtant décisif. Entre Euler et Hamilton, la théorie des graphes change de visage : d’un critère presque local fondé sur les degrés, on passe à une recherche globale, souvent difficile, parfois vertigineuse.
Hamilton n’arrive donc pas à la théorie des graphes par les ponts, mais par les symétries, les polyèdres et les jeux de parcours. Là où Euler partait d’un problème urbain, Hamilton part d’un objet géométrique presque parfait : le dodécaèdre.
Ce Dodécaèdre de Platon possède :
Le jeu icosien propose de trouver un cycle sur le graphe du dodécaèdre. Le parcours doit passer par chaque sommet exactement une fois et revenir au point de départ. Le jeu a été commercialisé au XIXe siècle, notamment sous forme de plateau ou de dodécaèdre, mais il n’a pas été un grand succès commercial. MathWorld indique que Hamilton l’a vendu à un fabricant londonien en 1859 pour 25 livres.
Le principe du jeu est simple à énoncer : parcourir les vingt sommets du dodécaèdre, chacun une seule fois, puis revenir au sommet de départ. En langage moderne, il s’agit de trouver un cycle hamiltonien dans le graphe du dodécaèdre.
Le contraste est intéressant : le jeu peut tenir dans un salon, mais l’idée mathématique qu’il contient traversera toute l’histoire de la théorie des graphes.
Un cycle hamiltonien est un cycle qui passe par tous les sommets d’un graphe exactement une fois avant de revenir au point de départ. Un graphe qui possède un tel cycle est appelé graphe hamiltonien.
La définition est courte, presque innocente. Pourtant, elle cache une difficulté profonde : il ne suffit pas de regarder chaque sommet séparément. Il faut comprendre l’organisation globale du graphe.
Prenons le dessin classique de la maison à tracer sans lever le crayon. Dans ce problème, ce qui compte, ce sont les segments. On cherche à passer une seule fois sur chaque trait de la figure.
Dans ce cadre, on peut très bien repasser plusieurs fois par le même sommet. Ce n’est pas un problème. Un sommet peut servir de carrefour, de point d’arrivée, puis de nouveau point de départ. Pour Euler, la contrainte porte sur les arêtes : chaque chemin doit être utilisé une seule fois.
Imaginons maintenant que l’on pose le problème autrement. On marque seulement les cinq sommets principaux de la maison, puis on demande s’il est possible de les visiter tous une seule fois avant de revenir au point de départ.
Cette fois, les segments ne sont plus tous obligatoires. On peut laisser certains chemins de côté. Ce qui compte, ce sont les sommets. Pour Hamilton, la contrainte porte sur les étapes à visiter : chaque sommet doit apparaître une seule fois dans le parcours.
On obtient donc deux lectures du même dessin :
C’est ce déplacement de contrainte qui est essentiel. Le passage d’Euler à Hamilton n’est pas seulement un changement de décor : c’est un changement de question. Dans un cas, on demande si tous les traits peuvent être parcourus exactement une fois. Dans l’autre, on demande si tous les points peuvent être visités exactement une fois, quitte à ne pas utiliser tous les traits disponibles.
Pour éviter de croire que le problème hamiltonien est toujours plus intuitif que le problème eulérien, prenons un autre dessin très simple : deux triangles qui partagent un seul sommet.
Dans ce graphe, tous les sommets semblent correctement reliés. Mieux encore : du point de vue d’Euler, la situation est favorable. Chaque sommet possède un nombre pair d’arêtes. On peut donc parcourir toutes les arêtes une seule fois.
Mais du point de vue de Hamilton, un obstacle apparaît immédiatement. Le sommet commun aux deux triangles est le seul passage entre la partie gauche et la partie droite du dessin. Pour visiter tous les sommets, il faut l’utiliser pour passer d’un triangle à l’autre. Mais pour fermer le cycle, il faudrait nécessairement revenir par ce même sommet.
Or un cycle hamiltonien ne permet pas de visiter deux fois le même sommet.
Ce petit graphe est donc un bon avertissement : un dessin peut être facile pour Euler et impossible pour Hamilton. La difficulté ne porte pas sur le même objet. Euler surveille les arêtes ; Hamilton surveille les sommets.
Prenons maintenant un carré avec ses deux diagonales. Le cycle hamiltonien est évident : on peut faire le tour du carré en passant par A, B, C, D, puis revenir à A. Les diagonales ne gênent pas Hamilton : elles existent, mais rien ne l’oblige à les emprunter.
En revanche, du point de vue d’Euler, la situation est bloquée : les quatre sommets ont un degré impair. Il est donc impossible de parcourir toutes les arêtes une seule fois sans lever le crayon.
Ce petit exemple montre l’inverse du nœud papillon : un graphe peut être hamiltonien sans être eulérien.
Ces petits exemples montrent pourquoi il faut se méfier des dessins trop simples. Un graphe peut être facile pour Euler et impossible pour Hamilton. Un autre peut être évident pour Hamilton et bloqué pour Euler. Les deux notions ne se contredisent pas : elles ne posent tout simplement pas la même question.
Pour Euler, il existe un critère très simple fondé sur la parité des sommets. Si tous les sommets sont reliés à un nombre pair d’arêtes, on peut espérer partir d’un point, parcourir toutes les arêtes une seule fois, puis revenir au point de départ : c’est le cas du cycle eulérien.
Si exactement deux sommets seulement sont reliés à un nombre impair d’arêtes, un parcours eulérien reste possible, mais il commence à l’un de ces deux sommets et se termine à l’autre : c’est le cas du chemin eulérien. Cette information locale suffit donc à décider rapidement si le problème d’Euler peut être résolu.
Pour Hamilton, rien d’aussi direct n’existe. Un sommet peut avoir beaucoup de voisins sans que le graphe possède un cycle hamiltonien.
À l’inverse, un graphe relativement sobre peut contenir un tel cycle. La difficulté vient du fait qu’il ne suffit pas de contrôler les sommets un par un : il faut réussir à organiser tous les sommets dans un seul parcours global, sans en oublier aucun et sans en visiter un deux fois.
Le jeu icosien peut sembler anecdotique : un plateau, vingt points à visiter, et une règle de parcours. Pourtant, il contient déjà une question qui deviendra centrale en mathématiques et en informatique : comment trouver un itinéraire passant par toutes les étapes imposées, sans répétition inutile ?
Dans le cas du dodécaèdre, le problème reste visuel et presque ludique. On peut chercher le parcours à la main, essayer, revenir en arrière, recommencer. Mais dès que le nombre de sommets augmente, la situation change complètement. Le nombre de parcours possibles explose, et une recherche naïve devient vite impraticable.
C’est là que l’idée de Hamilton dépasse largement le jeu inventé au XIXe siècle. Elle annonce toute une famille de problèmes de parcours : organiser une tournée, relier des points, visiter des lieux, optimiser un trajet, planifier un ordre de passage. À chaque fois, la question n’est plus seulement de savoir si deux points sont reliés, mais de savoir s’il existe un ordre global satisfaisant toutes les contraintes.
Le jeu icosien marque donc un passage important : derrière un objet géométrique élégant et une règle facile à comprendre, on voit apparaître une difficulté moderne. Le problème est simple à énoncer, mais il peut devenir très difficile à résoudre. C’est précisément ce contraste qui fera des graphes hamiltoniens un thème durable de la théorie des graphes.
Euler avait montré qu’un problème de promenade pouvait devenir une question mathématique. Avec les ponts de Königsberg, il ne s’intéressait plus à la forme exacte de la ville, ni aux distances, ni aux angles, mais seulement aux connexions entre les lieux. Cette abstraction était décisive : elle faisait apparaître un réseau derrière une situation concrète.
Hamilton conserve cette idée de réseau, mais il déplace la contrainte. Chez Euler, l’enjeu est de parcourir tous les chemins disponibles. Chez Hamilton, l’enjeu est de visiter toutes les étapes imposées. Ce n’est plus la même manière de regarder le dessin : les arêtes ne sont plus l’objectif principal, elles deviennent les possibilités de passage entre les sommets.
Ce changement est profond. Euler fournit un critère simple fondé sur la parité des sommets. Hamilton, lui, ouvre un domaine où la solution dépend de l’organisation globale du graphe. Il ne suffit plus de vérifier les sommets un par un : il faut trouver un ordre de visite cohérent pour l’ensemble du réseau.
Hamilton ajoute donc à l’héritage d’Euler une nouvelle famille de questions. Après le problème des chemins à parcourir, vient celui des étapes à organiser. Cette distinction suffira à faire naître des problèmes beaucoup plus difficiles qu’ils n’en ont l’air.
Le jeu icosien n’a peut-être pas connu le succès commercial espéré par Hamilton, mais il a laissé une idée beaucoup plus durable : certains problèmes de parcours ne se résument...
lien vers l'article sur wouf blog