Graphe eulérien

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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, il admet donc un cycle eulérien. 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[modifier | modifier le code]

La preuve du théorème d'Euler ci-dessous fut en fait publiée par Carl 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[modifier | modifier le code]

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é[modifier | modifier le code]

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) – Soit G un graphe orienté. Les trois propositions suivantes sont équivalentes:
  • G est eulérien
  • G est fortement connexe et chacun de ses sommets est l'extrémité initiale et terminale du même nombre d'arêtes.
  • G est faiblement connexe et chacun de ses sommets est l'extrémité initiale et terminale du même nombre d'arêtes.

La faible connexité suffit pour étendre le cas non orienté au cas orienté et un graphe eulérien est nécessairement fortement connexe.

Graphe eulérien et graphe hamiltonien[modifier | modifier le code]

Finalement, remarquons que le problème de décider si un graphe admet un parcours passant exactement une fois par chaque sommet – c'est-à-dire s'il est un graphe hamiltonien – est largement plus complexe. C'est un problème NP-complet, avec des applications importantes, qui occupe de nos jours encore de nombreux mathématiciens…

Voir aussi[modifier | modifier le code]

Problème du postier chinois (qui consiste à chercher un chemin passant au moins une fois par chaque arête)

Référence[modifier | modifier le code]

(en) Reinhard Diestel (de), Graph Theory, Springer-Verlag, Heidelberg, New York, 1997, 2000, 2005. Version électronique de la 3e édition document PDF disponible en ligne gratuitement