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, 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.

Sommaire

Théorème d'Euler

La preuve du théorème d'Euler ci-dessous fut en fait publiée par Carl Hierholzer (en) 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.

Graphe eulérien et graphe hamiltonien

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

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

Référence

(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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe eulérien de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • 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… …   Wikipédia en Français

  • Graphe eulerien — 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é… …   Wikipédia en Français

  • Graphe Hamiltonien — En théorie des graphes, un graphe hamiltonien est un graphe possédant au moins un cycle passant par tous les sommets une et une seule fois. Un tel cycle élémentaire est alors appelé cycle hamiltonien. Un graphe hamiltonien ne doit pas être… …   Wikipédia en Français

  • Graphe partiel — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Graphe (mathématiques) — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Graphe (théorie des graphes) — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Graphe hamiltonien — En théorie des graphes, un graphe hamiltonien est un graphe possédant au moins un cycle passant par tous les sommets une et une seule fois. Un tel cycle élémentaire est alors appelé cycle hamiltonien. Un graphe hamiltonien ne doit pas être… …   Wikipédia en Français

  • Graphe de Hamming — H(4,2) Notation H(d,q) Nombre de sommets qd Nombre d arêtes …   Wikipédia en Français

  • Graphe de Chvátal — Le graphe de Chvátal Nombre de sommets 12 Nombre d arêtes 24 Distribution des degrés 4 régulier Rayon 2 …   Wikipédia en Français

  • Graphe cuboctaédrique — Représentation du graphe cuboctaédrique. Nombre de sommets 12 Nombre d arêtes 24 Distribution des degrés 4 régulier Rayon …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”