Table des Matières
1. Qu'est-ce qu'un Parcours Eulérien ?
Un parcours eulérien (aussi appelé chemin d'Euler) est un trajet dans un graphe qui emprunte chaque arête exactement une fois. On peut repasser par un même sommet plusieurs fois, mais jamais parcourir deux fois la même arête.
Il répond à une question étonnamment pratique : étant donné un réseau de routes, de canalisations ou de câbles, puis-je toutes les parcourir sans jamais répéter une connexion ?
2. Chemin vs Circuit Eulérien
Les deux termes sont proches mais distincts :
- Un chemin eulérien emprunte chaque arête une fois et peut commencer et finir sur des sommets différents.
- Un circuit eulérien est un chemin eulérien fermé : il emprunte chaque arête une fois et revient à son sommet de départ.
Tout circuit eulérien est aussi un chemin eulérien, mais l'inverse est faux. Ce qu'un graphe admet dépend entièrement des degrés de ses sommets.
3. Les Sept Ponts de Königsberg
La ville prussienne de Königsberg était divisée par une rivière en quatre terres, reliées par sept ponts. Les habitants se demandaient s'ils pouvaient faire une promenade traversant chaque pont exactement une fois et revenant au point de départ.
En 1736, Leonhard Euler démontra qu'une telle promenade n'existe pas. Il modélisa chaque terre par un sommet et chaque pont par une arête, puis fit une observation décisive : chaque fois que l'on entre sur une terre par un pont, il faut en ressortir par un autre, donc tout sommet « de passage » doit avoir un nombre pair de ponts. Les quatre sommets de Königsberg avaient un nombre impair de ponts, rendant la promenade impossible. Cette preuve est considérée comme l'acte de naissance de la théorie des graphes. (Voir notre histoire de la théorie des graphes.)
4. La Règle des Degrés : Quand Existe-t-il ?
Le degré d'un sommet est le nombre d'arêtes qui le touchent. L'idée d'Euler donne des règles simples et exactes pour un graphe connexe :
- Un circuit eulérien existe si et seulement si tous les sommets ont un degré pair.
- Un chemin eulérien ouvert existe si et seulement si exactement deux sommets ont un degré impair, et il doit commencer à l'un et finir à l'autre.
- Si plus de deux sommets ont un degré impair, aucun chemin eulérien n'existe.
Le graphe doit aussi être connexe. Sinon, il suffit de compter les sommets de degré impair.
Parcourez le Graphe Vous-même
Construisez un réseau, puis regardez un algorithme tracer un chemin eulérien arête par arête, et voyez exactement pourquoi les sommets de degré impair le brisent.
Ouvrir le Visualiseur5. Le Trouver : Algorithmes de Fleury et Hierholzer
Une fois que l'on sait qu'un chemin existe, deux algorithmes classiques le construisent :
Algorithme de Fleury
Parcourez le graphe une arête à la fois, et ne franchissez jamais un isthme (une arête dont la suppression déconnecterait le graphe) sauf si vous n'avez pas d'autre choix. Facile à comprendre, mais vérifier les isthmes en permanence le rend relativement lent.
Algorithme de Hierholzer
Le choix efficace, en temps O(E). Suivez des arêtes pour former une boucle fermée, puis trouvez de façon répétée un sommet de votre parcours actuel qui possède encore des arêtes inutilisées et insérez-y une autre boucle. Quand il ne reste plus d'arêtes inutilisées, les boucles fusionnent en un seul circuit eulérien.
6. Euler vs Hamilton
On les confond sans cesse, mais ce sont des problèmes totalement différents :
- Un chemin eulérien visite chaque arête une fois.
- Un chemin hamiltonien visite chaque sommet une fois.
La surprise est algorithmique : décider si un chemin eulérien existe est facile (compter les degrés impairs), alors que décider si un chemin hamiltonien existe est NP-complet, parmi les problèmes les plus durs en informatique. Le Problème du Voyageur de Commerce en est un exemple hamiltonien célèbre.
7. Applications Concrètes
- Inspection de tournées (problème du postier chinois) : trouver le trajet le plus court couvrant chaque rue, courrier, collecte des déchets, déneigement, balayage.
- Séquençage de l'ADN : l'assemblage moderne de génomes construit un graphe de De Bruijn à partir de lectures courtes et trouve un chemin eulérien pour reconstruire la séquence.
- Maintenance de réseaux : inspecter ou tester chaque liaison d'un réseau télécom ou de distribution exactement une fois.
- Dessins « en un seul trait » : la célèbre énigme consistant à dessiner une figure sans lever le crayon est exactement une question de chemin eulérien.
Foire Aux Questions
Quelle est la différence entre un chemin et un circuit eulérien ?
Un chemin eulérien emprunte chaque arête exactement une fois et peut commencer et finir sur des sommets différents. Un circuit eulérien emprunte aussi chaque arête une fois, mais doit commencer et finir sur le même sommet.
Comment savoir si un graphe possède un chemin eulérien ?
Dans un graphe connexe, un circuit eulérien existe si tous les sommets ont un degré pair, et un chemin eulérien ouvert existe si exactement deux sommets ont un degré impair. Si plus de deux sommets ont un degré impair, aucun chemin eulérien n'existe.
Quelle est la différence entre un chemin eulérien et hamiltonien ?
Un chemin eulérien visite chaque arête une fois, tandis qu'un chemin hamiltonien visite chaque sommet une fois. Vérifier un chemin eulérien est facile, mais vérifier un chemin hamiltonien est NP-complet.
Pourquoi le problème des Sept Ponts de Königsberg est-il impossible ?
Les quatre terres étaient reliées par un nombre impair de ponts. Un chemin eulérien admet au plus deux sommets de degré impair, donc traverser chaque pont exactement une fois est impossible.