Histoire et cultureNotion · Glossaire
cycle eulérien
Dans la théorie des graphes, un cycle eulérien est un parcours fermé d'un graphe non orienté qui emprunte chaque arête exactement une fois. C'est donc une chaîne eulérienne (parcours passant par toutes les arêtes exactement une fois) dont le sommet de départ et le sommet d'arrivée sont confondus. Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair. Ce résultat est dû à Euler, qui l'a établi dans le cadre du célèbre problème des sept ponts de Königsberg (1736). La recherche d'un cycle eulérien dans un graphe peut se faire efficacement par des algorithmes tels que celui de Hierholzer.
Sommaire
Ce que vous allez apprendre
- Identifier ce qui doit être parcouru exactement une fois dans un cycle eulérien.
- Tester l'existence d'un cycle par la connexité et la parité des degrés.
- Contrôler pas à pas un cycle eulérien sur un graphe à trois sommets.
- Distinguer un cycle eulérien d'une chaîne eulérienne.
En clair
Imaginez un réseau de chemins dessinés entre plusieurs carrefours. Le défi consiste à parcourir chaque chemin une seule fois, puis à revenir exactement au carrefour de départ. Les carrefours peuvent être revisités ; ce sont les chemins qui ne doivent jamais l'être.
Un tel trajet forme un cycle eulérien. Pour qu'il existe dans un réseau d'un seul tenant, le nombre de chemins reliés à chaque carrefour doit être pair. Chaque arrivée peut alors être associée à un départ.
Définition
Dans un graphe non orienté, les sommets représentent les points du réseau et les arêtes les liaisons entre ces points. Un cycle eulérien est une marche fermée, c'est-à-dire une suite alternée de sommets et d'arêtes où chaque arête relie le sommet qui la précède à celui qui la suit, qui utilise chaque arête du graphe exactement une fois et revient au sommet initial. Un sommet peut apparaître plusieurs fois dans cette suite : seule la répétition d'une arête est interdite.
Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes. Pour un graphe connexe, le critère est nécessaire et suffisant : il existe un cycle eulérien si et seulement si chaque sommet a un degré pair. En notant V l'ensemble des sommets et deg(v) le degré du sommet v, ce critère s'écrit . La connexité assure qu'un parcours peut atteindre toutes les arêtes ; la parité permet de quitter chaque sommet autant de fois qu'on y entre.
Une chaîne eulérienne utilise elle aussi toutes les arêtes une seule fois, mais ses extrémités ne sont pas nécessairement confondues. Le cas fermé est le cycle eulérien. Euler a établi le critère dans le contexte du problème des sept ponts de Königsberg, en 1736. Pour construire effectivement un cycle, l'algorithme de Hierholzer suit des arêtes encore inutilisées et assemble les parcours fermés obtenus.
Un exemple, pas à pas
Considérons un graphe formé de trois sommets A, B et C. Le schéma associé montre un triangle : il permet de suivre visuellement le parcours tout en contrôlant chaque arête.
Les données sont les trois arêtes AB, BC et CA. Chaque sommet touche exactement deux arêtes : A, B et C ont donc tous le degré 2. Le graphe est connexe.
1. Partez de A et empruntez l'arête AB.
2. Depuis B, prenez l'arête BC, encore inutilisée.
3. Depuis C, prenez l'arête CA et revenez au point de départ. Le parcours obtenu est A–B–C–A.
Le contrôle est direct : AB, BC et CA figurent chacune une fois dans le parcours, aucune autre arête n'existe, et le départ coïncide avec l'arrivée. A–B–C–A est donc un cycle eulérien. Le critère des degrés pairs donne le même verdict.
En pratique
Pour décider rapidement si un réseau connexe admet un cycle eulérien, comptez les arêtes incidentes à chaque sommet. Si tous les degrés sont pairs, le cycle existe ; dès qu'un degré est impair, il faut renoncer à un parcours fermé utilisant chaque arête une seule fois.
Quand la tâche porte sur les liaisons elles-mêmes, par exemple parcourir tous les segments d'un réseau sans répétition, le modèle eulérien est adapté. Si l'objectif porte plutôt sur une visite unique de chaque sommet, le critère sur les arêtes ne répond pas à la question.
Lorsque le test de parité est positif, l'algorithme de Hierholzer fournit une construction efficace : il suit des arêtes inutilisées jusqu'au retour au départ, puis raccorde de nouveaux parcours fermés tant qu'il reste des arêtes.
À ne pas confondre
Chaîne eulérienne et cycle eulérien. Une chaîne eulérienne parcourt chaque arête exactement une fois et peut être ouverte ou fermée selon la convention. Un cycle eulérien est le cas fermé : si le parcours A–B–C se termine ailleurs qu'en A, il peut être une chaîne, mais pas un cycle eulérien.
Parcourir les arêtes et visiter les sommets. Un cycle eulérien impose une visite unique des arêtes, pas des sommets. Dans A–B–C–A, le sommet A apparaît deux fois, ce qui est normal, tandis qu'une seconde utilisation de AB invaliderait le parcours.
Limites et pièges
Des degrés pairs ne suffisent pas sans connexité. Si les arêtes sont réparties dans plusieurs composantes séparées, aucun parcours continu ne peut toutes les atteindre. Il faut d'abord traiter les composantes séparément ou relier le graphe.
La présence d'un degré impair suffit à bloquer le cycle. Le symptôme est un sommet où les passages ne peuvent pas être associés par couples entrée-sortie. Il faut vérifier tous les degrés avant de chercher un parcours fermé.
Le tracé ne constitue pas une preuve. Un dessin symétrique peut suggérer à tort qu'un cycle existe. Le bon contrôle porte sur deux propriétés vérifiables : la connexité du graphe et la parité du degré de chaque sommet.
Pour aller plus loin
degré d'un sommet d'un graphe — Pour approfondir le comptage local sur lequel repose le critère des degrés pairs.
ponts de Königsberg — Pour replacer le critère eulérien dans le problème historique cité dans la définition.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres