Graphe eulérien
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
modifierProblème du dessin de l'enveloppe
modifierLa 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
modifierLe 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
modifierOn 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.
Théorème d'Euler
modifierDegré d'un sommet
modifierLe 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
modifierLe 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 éventuellement deux d'entre eux.
- Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
Démonstration
modifierEuler 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
modifierAlgorithme de Hierholzer
modifierOn 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
modifierPierre-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
Une réorganisation et une clarification du contenu sont nécessaires.
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
modifierDans 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- (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
modifierArticles connexes
modifier- 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- (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.
