chaîne eulérienne

Imaginez un réseau de ponts reliant plusieurs îles. Le défi consiste à choisir un point de départ, puis à franchir chaque pont une seule fois, sans obligation de revenir au départ. Une chaîne eulérienne est précisément un tel parcours : elle s'intéresse aux liaisons empruntées, et non au nombre de passages par chaque lieu.

Les lieux reliés à un nombre impair de ponts décident des extrémités. S'il y en a deux, le parcours part de l'un et finit à l'autre.

Dans un graphe non orienté, une chaîne eulérienne est une suite d'arêtes adjacentes qui utilise chaque arête du graphe exactement une fois. Un sommet peut être rencontré plusieurs fois. Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes.

Pour un graphe fini et connexe, notons o le nombre de sommets de degré impair. Le critère d'existence est $o\in \{0,2\}o\backslash in\backslash \{0,2\backslash \}$. Si o vaut 2, les deux sommets impairs sont nécessairement les extrémités de la chaîne. Si o vaut 0, le parcours peut revenir à son sommet initial : c'est un cycle eulérien, aussi appelé circuit eulérien. Avec plus de deux sommets impairs, aucune chaîne eulérienne n'existe.

Dans un graphe orienté, les liaisons sont des arcs munis d'un sens. La notion analogue est le chemin eulérien, qui utilise chaque arc exactement une fois. Son existence dépend alors de l'équilibre entre le nombre d'arcs entrants et le nombre d'arcs sortants à chaque sommet, et non de la seule parité du degré.

Considérons quatre sommets A, B, C et D. Les cinq arêtes sont AB, BC, CD, DA et AC. La figure associe à chaque sommet son degré ; A et C, en jaune, sont les deux sommets impairs.

1. On compte les arêtes incidentes à chaque sommet. En notant d le degré, on obtient :

2. A et C sont les seuls sommets de degré impair. Une chaîne eulérienne doit donc commencer à l'un et se terminer à l'autre.

3. Partons de A et suivons A–B–C–D–A–C. Les arêtes parcourues sont, dans l'ordre, AB, BC, CD, DA et AC.

Le parcours part de A, finit en C et utilise les cinq arêtes une fois chacune. Pour le contrôler, on coche la liste AB, BC, CD, DA, AC : chaque élément apparaît exactement une fois.

Devant un réseau non orienté fini, on vérifie d'abord qu'il est connexe, puis on compte les sommets de degré impair. Ce contrôle suffit pour décider si une chaîne eulérienne peut exister.

S'il existe exactement deux sommets impairs, on choisit l'un comme départ et l'autre comme arrivée. Dans l'exemple A–B–C–D–A–C, partir de B serait donc un mauvais choix pour une chaîne couvrant les cinq arêtes.

Si tous les degrés sont pairs, on cherche plutôt un circuit eulérien et l'on peut revenir au point de départ. Si plus de deux degrés sont impairs, il faut modifier le réseau ou renoncer à utiliser chaque arête exactement une fois.

Chaîne eulérienne et cycle eulérien. Une chaîne peut avoir deux extrémités distinctes ; un cycle revient à son point de départ. Dans le graphe de l'exemple, A et C ont un degré impair : A–B–C–D–A–C est une chaîne, pas un cycle.

Arêtes et sommets. Le critère eulérien impose d'utiliser chaque arête exactement une fois, mais il n'interdit pas de revoir un sommet. Dans A–B–C–D–A–C, le sommet A apparaît deux fois alors que chacune des cinq arêtes n'apparaît qu'une fois.

Graphe non orienté et graphe orienté. Dans le premier, une arête se parcourt dans les deux sens. Dans le second, le sens des arcs compte, et le test repose sur les nombres d'arcs entrants et sortants. Le simple comptage des degrés impairs ne tranche donc pas le cas orienté.

Oublier la connexité. Dans un graphe fini, avoir zéro ou deux sommets impairs ne suffit pas si des arêtes se trouvent dans des composantes séparées. Un parcours continu ne peut pas passer d'une composante à l'autre ; il faut d'abord vérifier que toutes les arêtes appartiennent au même réseau connexe.

Choisir une mauvaise extrémité. Avec exactement deux sommets impairs, le départ et l'arrivée sont imposés à l'ordre près. Dans l'exemple, commencer en B empêche d'obtenir une chaîne eulérienne complète ; il faut commencer en A ou en C.

Dépasser le seuil. Dès qu'un graphe fini et connexe possède quatre sommets impairs ou davantage, aucune chaîne eulérienne n'est possible. Ajouter ou retirer des arêtes peut changer les parités ; le test doit alors être refait sur le graphe modifié.

Transposer le test au cas orienté. La parité des degrés convient aux graphes non orientés. Pour des arcs, il faut comparer séparément les demi-degrés entrant et sortant de chaque sommet.

Le graphe connexe précise pourquoi toutes les arêtes à parcourir doivent rester accessibles au sein d'une même composante.

Le degré d'un sommet d'un graphe approfondit le comptage dont la parité fournit le critère eulérien.

La fiche Graphe orienté et non-orienté aide à choisir le bon critère selon que les liaisons possèdent ou non un sens.