Graphe eulérien

En théorie des graphes, un parcours eulérien ou chemin eulérien, ou encore chaine eulérienne d'un graphe non orienté est un chemin qui passe par toutes les arêtes, une fois par arête. Le nom a été donné en référence à Leonhard Euler. Si un tel chemin revient au sommet de départ, on parle de circuit eulérien ou cycle eulérien, ou encore tournée eulérienne. Un graphe qui admet un circuit eulérien est dit eulérien. S'il admet un parcours eulérien, il est dit semi-eulérien.

Exemples

Problème du dessin de l'enveloppe

La notion de parcours eulérien s'illustre avec le problème du dessin de l'enveloppe. Il s'agit de tracer une enveloppe sans lever le crayon et sans dessiner plusieurs fois un même trait. On peut modéliser le dessin avec le graphe ci-dessous. Un parcours eulérien correspond à un tracé d'un graphe sur une feuille sans lever le crayon.

• 
  Exemple d'un graphe admettant un parcours eulérien.
• 
  Dessin à la main sans lever le crayon

Problème des sept ponts de Königsberg

Le problème des sept ponts de Königsberg est le problème de savoir si on peut traverser chaque pont de la ville de Königsberg en une promenade, une fois sur chaque pont. Comme le montre la figure ci-dessous, le problème se modélise à l'aide d'un graphe comme suit : les ponts constituent les arêtes et les îles et les berges les sommets. Comme ce graphe n'admet pas de parcours eulérien, le problème n'a pas de solutions.

→ →

Graphe d'un octaèdre

On peut aussi considérer le graphe d'un polyèdre, par exemple un octaèdre. Les sommets et arêtes du polyèdre sont respectivement les sommets et arêtes du graphe.

Animation d'un des 372 circuits eulériens (de première arête donnée) du graphe des arêtes de l'octaèdre régulier. Ce graphe est eulérien car tous ses sommets sont de degré 4.

Théorème d'Euler

Degré d'un sommet

Le degré d'un sommet est le nombre d'arêtes arrivant à ce sommet (arêtes incidentes). Dans les graphes suivants, on indique les degrés pour chaque sommet.

• 
  Graphe des 7 ponts de Königsberg, et un autre graphe, dit des 5 chambres. Ces graphes n'admettent pas de parcours eulériens. Les nombres indiqués sont les degrés.
• 
  1. et 4. Graphes ayant un parcours eulérien mais pas de circuit eulérien. 2. Graphe sans solution. 3. Graphe ayant un circuit eulérien.

Énoncé du théorème

Le théorème d'Euler, appelé aussi théorème d'Euler-Hierholzer, se décline en deux caractérisations :

• Un graphe connexe admet un parcours eulérien si et seulement si ses sommets sont tous de degré pair sauf au plus deux.
• Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair.

Démonstration

Euler a démontré les conditions nécessaires en 1735. La démonstration complète ci-dessous ayant été publiée par le mathématicien allemand Carl Hierholzer en 1873. On attribue parfois l'équivalence à Euler, comme dans le livre de théorie des graphes de Diestel (voir Th. 1.8.1 dans ). Le sens direct se démontre comme suit.

Supposons qu'il y a un parcours eulérien et empruntons le en supprimant les arêtes utilisées. À chaque passage sur un sommet (sauf au début et à la fin), on supprime l'arête qui arrive sur ce sommet et l'arête qui en part. Ainsi, sauf pour le sommet de départ ou d'arrivée, la parité du degré reste inchangée. À la fin du parcours, toutes les arêtes sont supprimées, ce qui permet de conclure sur la parité des sommets.

Le sens indirect, i.e. réciproque, se démontre comme suit.

Montrons le quand tous les sommets sont de degré pair. Commençons à un sommet quelconque s₀ du graphe. Empruntons des arêtes, en les supprimant du graphe, tant que cela est possible. Comme les degrés sont pairs, nous sommes forcément revenus au sommet s₀ et nous avons trouvé un circuit s₀ - s₁ - ... - s₀. S'il ne reste plus d'arêtes, alors nous avons un circuit eulérien. Sinon, nous recommençons le processus afin d'exhiber un autre circuit, depuis un sommet s_i duquel part une arête. Nous obtenons alors un autre circuit s_i - ... - s_i, que nous venons coller dans le circuit précédent à la place de s_i :

s₀ - s₁ - ... - s_i -- ... -- s_i - s_i+1 - ... s₀.

On répète le processus jusqu'à avoir utilisé toutes les arêtes et l'on obtient un circuit eulérien.

Algorithmes

Algorithme de Hierholzer

On peut effectivement écrire un programme informatique pour calculer un chemin ou un circuit eulérien s'il en existe. Discutons l'algorithme du papier de Hierholzer de 1873, qui suit l'idée de sa démonstration (voir le sens indirect ci-dessus). Il répète l'extraction de circuits que l'on colle pour construire un circuit eulérien. Cet algorithme peut s'implémenter afin d'avoir un algorithme en temps linéaire en le nombre d'arêtes (voir Example 2.5.2, et Algorithm 2.3.1 dans ). Pour cela, il suffit que les opérations suivantes s'exécutent en temps constant :

1. trouver une arête non empruntée
2. trouver un nouveau sommet qui admet encore des arêtes incidentes non empruntés
3. coller le circuit dans le parcours en cours de construction

Pour cela, il suffit de maintenir efficacement avec des listes doublement chainées :

1. la liste des sommets du parcours en construction qui ont encore des arêtes inutilisées
2. pour chaque sommet, la liste des arêtes non encore utilisées
3. la liste des arêtes du parcours en construction

Algorithme de Fleury

Pierre-Henry Fleury a donné un autre algorithme en 1883 mais dont une implémentation sur ordinateur serait moins efficace que l'algorithme de Hierholzer. Son idée est de construire le circuit en empruntant à chaque fois en priorité une arête dont la suppression ne déconnecte pas le graphe.

Cas d'un graphe orienté

Les résultats ci-dessus s'exportent aux graphes orientés. Un tel graphe est dit 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 connexe et chacun de ses sommets est l'extrémité initiale et terminale du même nombre d'arêtes.

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

Complexité algorithmique

Dans certains livres d'algorithmique (mais aussi le livre de théorie des graphes de Diestel, voir Chapitre 10, p. 213 de ), dans le cadre de la théorie de la complexité, le problème EULÉRIEN, de savoir si un graphe est eulérien, est souvent comparé au problème HAMILTONIEN, de trouver un parcours hamiltonien, c'est-à-dire un parcours passant exactement une fois par chaque sommet. Déterminer qu'un graphe admet un circuit eulérien se fait en temps polynomial (il suffit de vérifier la parité des degrés des sommets du graphe). Ainsi, le problème EULÉRIEN de savoir si un graphe est eulérien est dans la classe P. Le problème HAMILTONIEN est a priori plus compliqué à résoudre algorithmiquement : c'est un problème NP-complet, avec des applications importantes.

Voir aussi

Articles connexes

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

• Théorème de BEST, qui donne une formule pour compter le nombre de circuits eulériens d'un graphe
• Liste de sujets portant le nom d'Euler

Bibliographie

• (en) Reinhard Diestel, Graph Theory [détail des éditions]
• Édouard Lucas, Récréations mathématiques, 9 rue de Médicis, Paris, Librairie Albert Banchard, 1892 (lire en ligne) lire en ligne sur Gallica, voir p. « page 33 » où le problème est décrit sous le titre Les ponts de Paris en 1880.