Graphe Eulérien

Graphe eulérien

En théorie des graphes, on dit d'un graphe non-orienté qu'il est « eulérien » en référence à Euler (la plupart des mathématiciens écrivent « Eulérien » à cause de l'usage anglo-saxon) s'il a la propriété suivante :

On peut distinguer une extrémité initiale et une extrémité finale de chaque arête, et ordonner l'ensemble des arêtes du graphe de telle façon que l'extrémité finale d'une arête corresponde à l'extrémité initiale de l'arête qui lui succède dans l'ordre (où la première arête de l'ordre succède à la dernière).

Cette propriété est équivalente au fait que l'on peut « parcourir » le graphe en partant d'un sommet quelconque et en empruntant exactement une fois chaque arête pour revenir au sommet de départ. Un tel graphe a alors la propriété qu'il correspond à un dessin qu'on peut tracer sans lever le crayon.

Théorème d'Euler

La preuve du théorème d'Euler ci-dessous fut en fait publiée par Hierholzer en 1873, on l'appelle donc aussi le théorème d'Euler-Hierholzer :

Théorème d'Euler (1736) – Un graphe connexe est eulérien si et seulement si chacun de ses sommets est incident à un nombre pair d'arêtes.

Remarquons que si seuls deux sommets s et t sont incidents à un nombre impair d'arêtes, l'ajout de l'arête st rend le graphe eulérien, en d'autres termes, on peut parcourir le graphe depuis s jusqu'à t en empruntant chaque arête exactement une fois (comme e.g. pour l'enveloppe).

Preuve

La nécessité est pratiquement immédiate (l'argument est le même que pour la résolution du problème des sept ponts de Königsberg). La suffisance n'est pas non plus beaucoup plus dure.

Rappelons d'abord quelques définitions :

Le degré d'un sommet est le nombre d'arêtes incidentes au sommet ;
Un parcours est une suite d'arêtes telle que (i) pour chaque arête de la suite on peut distinguer une extrémité initiale et une terminale, (ii) l'extrémité terminale d'une arête est aussi l'extrémité initiale de l'arête qui lui succède dans la suite (et la première arête succède à la dernière) ;
Un circuit est un parcours non-vide tel qu'aucun sommet n'est l'extrémité initiale (terminale) de plus d'une arête.

La condition suffisante du théorème d'Euler-Hierholzer s'appuie principalement sur les trois faits suivants :

(1) Si tous les degrés sont pairs et non tous nuls, alors il existe un circuit ;

(2) Un parcours est une union de circuits disjoints – au niveau des arêtes, et non des sommets ;

(3) Si l'on retire les arêtes d'un parcours, alors les degrés pairs restent pairs.

Supposons maintenant que chaque sommet a un degré pair et qu'il n'existe pas de parcours contenant toutes les arêtes. Si l'on considère un parcours avec un nombre maximum d'arêtes et que l'on retire ensuite les arêtes du parcours du graphe, par (3), les degrés restent pairs. D'où, par (1), l'existence d'un circuit disjoint de notre parcours maximum. Mais, par (2), l'union de notre parcours et du circuit forme un autre parcours avec plus d'arêtes, ce qui contredit l'hypothèse de maximalité du parcours initial. Cette contradiction implique donc le théorème.

Le cas orienté

Les résultats ci-dessus s'exportent facilement aux graphes orientés. Un tel graphe est Eulérien s'il a la propriété suivante :

On peut ordonner les arcs du graphe de telle façon que deux arêtes consécutives par rapport à l'ordre – où la dernière et la première arêtes de l'ordre sont considérées comme consécutives – sont consécutives dans le graphe.

Là encore cette propriété signifie que l'on peut « parcourir » le graphe en suivant les arcs depuis leur extrémité initiale vers l'extrémité terminale et en utilisant bien sûr exactement une fois chaque arc et en revenant au point de départ. On montre comme pour la version non-orientée le théorème suivant :

Théorème d'Euler (version orientée) – Un graphe orienté fortement connexe est Eulérien si et seulement si chacun de ses sommets est l'extrémité initiale et terminale du même nombre d'arêtes.