Graphe eulérien — Wikipédia
En théorie des graphes, un parcours eulérien ou chemin eulérien[1], 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[2]. Si un tel chemin revient au sommet de départ, on parle de circuit eulérien[3] ou cycle eulérien, ou encore tournée eulérienne[3]. 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
[modifier | modifier le code]Problème du dessin de l'enveloppe
[modifier | modifier le code]La notion de parcours eulérien s'illustre avec le problème du dessin de l'enveloppe[4]. 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
[modifier | modifier le code]Le problème des sept ponts de Königsberg[5] 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
[modifier | modifier le code]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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/57/Areteoctaedre.gif/220px-Areteoctaedre.gif)
Théorème d'Euler
[modifier | modifier le code]Degré d'un sommet
[modifier | modifier le code]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
[modifier | modifier le code]Le théorème d'Euler, appelé aussi théorème d'Euler-Hierholzer, se décline en deux caractérisations[5] :
- 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
[modifier | modifier le code]Euler a démontré les conditions nécessaires en 1735[2]. La démonstration complète ci-dessous ayant été publiée par le mathématicien allemand Carl Hierholzer en 1873[6]. On attribue parfois l'équivalence à Euler, comme dans le livre de théorie des graphes de Diestel (voir Th. 1.8.1 dans [7]). 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 s0 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 s0 et nous avons trouvé un circuit s0 - s1 - ... - s0. 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 si duquel part une arête. Nous obtenons alors un autre circuit si - ... - si, que nous venons coller dans le circuit précédent à la place de si :
s0 - s1 - ... - si -- ... -- si - si+1 - ... s0.
On répète le processus jusqu'à avoir utilisé toutes les arêtes et l'on obtient un circuit eulérien.
Algorithmes
[modifier | modifier le code]Algorithme de Hierholzer
[modifier | modifier le code]On peut effectivement écrire un programme informatique pour calculer un chemin ou un circuit eulérien s'il en existe. Discutons l'algorithme de l'article de Hierholzer de 1873[6], 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[8]. 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 [9]). Pour cela, il suffit que les opérations suivantes s'exécutent en temps constant :
- trouver une arête non empruntée
- trouver un nouveau sommet qui admet encore des arêtes incidentes non empruntés
- coller le circuit dans le parcours en cours de construction
Pour cela, il suffit de maintenir efficacement avec des listes doublement chainées :
- la liste des sommets du parcours en construction qui ont encore des arêtes inutilisées
- pour chaque sommet, la liste des arêtes non encore utilisées
- la liste des arêtes du parcours en construction
Algorithme de Fleury
[modifier | modifier le code]Pierre-Henry Fleury[10] 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é
[modifier | modifier le code]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
[modifier | modifier le code]Dans certains livres d'algorithmique[11],[12] (mais aussi le livre de théorie des graphes de Diestel, voir Chapitre 10, p. 213 de [7]), 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.
Références
[modifier | modifier le code]- (en) Patrick Bosc, Marc Guyomard et Laurent Miclet, Conception d'algorithmes Principes et 150 exercices non corrigés, (lire en ligne)
- (la) Leonhard Euler, « "Solutio problematis ad geometriam situs pertinentis" », Comment. Academiae Sci. I. Petropolitanae 8, , p. 128–140 (lire en ligne)
- Algorithmique, (lire en ligne)
- « CHEMIN EULÉRIEN — Figures unicursales » : « LA CÉLÈBRE ENVELOPPE et variantes », sur NOMBRES - Curiosités, théorie et usages.
- « Ponts de Königsberg et cycle eulérien », sur www.bibmath.net (consulté le )
- (de) Carl Hierholzer et Chr Wiener, « Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren », Mathematische Annalen, vol. 6, no 1, , p. 30–32 (ISSN 1432-1807, DOI 10.1007/BF01442866, lire en ligne, consulté le )
- (en-GB) Reinhard Diestel, « Graph Theory », Graduate Texts in Mathematics, (ISSN 0072-5285 et 2197-5612, DOI 10.1007/978-3-662-53622-3, lire en ligne, consulté le )
- Fleischner, Herbert (1991), "X.1 Algorithms for Eulerian Trails", Eulerian Graphs and Related Topics: Part 1, Volume 2, Annals of Discrete Mathematics, 50, Elsevier, pp. X.1–13, (ISBN 978-0-444-89110-5).
- (en) Dieter Jungnickel, Graphs, Networks and Algorithms, Springer-Verlag, coll. « Algorithms and Computation in Mathematics », (ISBN 978-3-642-09186-5, lire en ligne)
- Fleury, Pierre-Henry (1883), "Deux problèmes de Géométrie de situation", Journal de mathématiques élémentaires, 2nd ser. (in French), 2: 257–261.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, , 2e éd., 1176 p. (ISBN 2 10 003922 9)
- (en) Sanjoy Dasgupta, Christos Papadimitriou et Umesh Vazirani, Algorithms, McGraw-Hill,
Voir aussi
[modifier | modifier le code]Articles connexes
[modifier | modifier le code]- 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
[modifier | modifier le code]- (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, (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.