Retour à la table des matières

Département de mathématiques de l'Université de La Rochelle

 

Chapitre 1 - Graphes eulériens

 

C - Algorithme de Fleury - Tracé des chemins eulériens

La démonstration par récurrence du paragraphe précédent fournit un moyen théorique de tracer, dans un graphe eulérien ou semi-eulérien, un lacet ou un chemin eulérien. Il existe néanmoins, pour ce faire, un moyen plus simple, l'algorithme de Fleury.

Définition - Soit G un graphe connexe et A1A2 une arête de G. On dit que cette arête est un pont si, lorsqu'on la retire et si l'on efface les éventuels points isolés qui résultent de cette suppression, le nouveau graphe obtenu n'est plus connexe.

Ainsi, dans la figure ci-dessous, l'arête A1A2 est un pont pour le graphe de gauche, alors qu'elle n'en est pas un pour celui de droite.

Algorithme de Fleury : pour tracer un graphe eulérien, suivre la procédure suivante :

partir d'un sommet quelconque A ; chaque fois que l'on suit une arête, on l'efface ; chaque fois qu'un point devient isolé on l'efface aussi.

ne jamais utiliser une arête AB qui, au moment considéré, soit un pont, sauf s'il n'existe aucune autre possibilité.

Nous allons démontrer en deux temps que cet algorithme permet bien de tracer un lacet eulérien.

1. On peut toujours suivre cette procédure.

Sinon, cela signifierait qu'à un certain moment, on serait en un sommet x d'où ne partent que des ponts (et au moins 2 compte tenu de la définition d'un pont : si d'un point part une unique arête, la suppression de celle-ci rend le point isolé et entraîne la suppression de celui-ci, de telle sorte que l'arête considérée n'est pas un pont). Ces deux ponts conduisent à des composantes disjointes du graphe (si elles ne l'étaient pas, la suppression d'un seul des deux ponts ne suffirait pas à disconnecter G.

Observons la composante G1. Le nombre d'arêtes incidentes à A dans cette composante est impair. En effet, dans le graphe entier, il est pair lorsqu'on rajoute xA. Donc il existe, quelque part ailleurs dans G1, un autre point de degré impair à cause du (b) du lemme des poignées de mains. Appelons b ce sommet. On trouve de même un autre sommet a dans la composante G2 de degré impair. Or, à ce stade du tracé, les deux seuls points éventuellement de degré impair dans le graphe sont x et A (à condition qu'ils soient distincts) : il ne peut donc y avoir qu'un point autre que x et de degré impair.

2. Lorsque la procédure s'arrête, le graphe entier est dessiné.

D'après ce qui vient d'être dit au dessus, dès lors qu'il y a, devant x, au moins deux arêtes, l'une d'entre elles n'est pas un pont et on peut continuer. S'il y a devant x une seule arête, celle-ci n'est pas un pont et on peut continuer. Donc, si la procédure s'arrête, c'est qu'il n'y a plus devant x aucune arête, et donc que x est isolé. Or, l'algorithme est ainsi fait qu'à tout instant le graphe restant est connexe. Si un graphe connexe contient un point isolé, c'est qu'il est égal à ce point isolé. Cela signifie que la dernière arête que l'on vient d'effacer était aussi la dernière du graphe.