Retour à la table des matières

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

 

Chapitre 1 - Graphes eulériens

 

D - Extension aux graphes orientés

Un graphe orienté est un graphe dans lequel chaque arête a maintenant un sens de parcours obligatoire. Un chemin le long d'un tel graphe (ou un lacet) doit donc être parcouru en suivant le sens des flèches. Pour certaines questions, comme celle des graphes hamiltoniens que nous étudierons au chapitre suivant, l'introduction de l'orientation rend létude beaucoup plus compliquée, voire quasi-impossible. Ce n'est pas le cas, cependant, pour les graphes eulériens.

Définition - Un graphe G orienté est dit symétrique si, en tout sommet x, le nombre d'arêtes sortantes est égal au nombre d'arêtes entrantes.

Théorème - Un graphe orienté est eulérien si et seulement si il est symétrique.

Ce théorème se démontre exactement comme les théorèmes de caractérisation prouvés dans la partie B.

Exemple (algorithme de Sari)

On considère le graphe orienté G dont les sommets sont les suites (a1, , am) de 0 et de 1 (ai = 0 ou 1). Chaque sommet (a1, , a m) a deux ``descendants'' : (a2, , am, 1) et (a2, , am, 0). L'arête qui relie (a1, , am) à (a2, , am, 1) est elle-même notée (a1, , am, 1) (et de même, on désigne par (a1, , am, 0) l'arête qui relie (a1, , am) à son autre descendant (a2, , am, 0)).

Attention : dans cette manière de coder les arêtes, alors que les sommets sont des m-uplets de 0 et de 1, les arêtes, elles, sont représentées par des (m+1)-uplets.

Chaque sommet a donc deux descendants, mais aussi deux ascendants : les deux m-uplets (0, a1, , am-1) et (1, a1, , am-1) ont (a1, , am) pour descendant, et ce sont ses seuls ascendants.

Par conséquent, le graphe est équilibré, donc eulérien : il est possible de parcourir toutes ses arêtes sans passer deux fois sur la même et sans lever le crayon. Remarquant par ailleurs que deux arêtes adjacentes s'écrivent toujours

(a0 et am+1 valent 0 ou 1), on constate que, partant d'une première arête, puis en ajoutant une adjacente, et continuant ainsi jusqu'à épuisement des ingrédients, on obtient

(où N est le nombre total d'arêtes) qui peut s'écrire en raccourci :

a0 a1 ... am am+1 ... aN -1 ... am+N -1

Le codage des arêtes représente toutes les manières possibles d'écrire une suite (a0, , am+1) de m+1 nombres valant 0 ou 1.

Imaginons alors qu'un pinceau de largeur N +1 balaie la suite a0, am+N -1 : il lira alors toutes ces suites, les unes après les autres. De telles suites sont au nombre de 2m+1 (d'où N = 2m+1). Il faut noter que, par rapport à la simple écriture les unes en dessous des autres de toutes ces suites (écriture qui nécessiterait m . 2m+1 caractères), le ``codage'' ci-dessus permet de n'utiliser que m + 2m+1 caractères. Si m=10, on passe donc de 20560 à 2067 caractères.

Remarque - Ce codage est effectivement utilisé pour certaines applications de nature technique.

Il reste maintenant à savoir comment trouver un algorithme efficace pour écrire la suite a0, am+N-1 (ou, en d'autres termes, pour parcourir le graphe). On pourrait bien sûr utiliser l'algorithme de Fleury, mais il y a une autre possibilité.

Algorithme de Sari - On part de (0, , 0), on va vers (0, , 0, 1) et on efface l'arête. Puis, chaque fois que l'on est à un sommet (a1, , am), on choisit d'aller de préférence vers (a2, , am, 1). L'expression ``de préférence'' signifie que le seul cas où l'on va vers l'autre sommet est celui où l'arête qui nous permettrait d'atteindre le sommet ``préféré'' a déjà été effacée lors d'un précédent passage. Puis on efface l'arête que l'on vient d'utiliser.

Cet algorithme, pour des raisons de parité, se termine forcément en (0, , 0) aprés parcours de la boucle (0, , 0) (0, , 0). Montrons qu'il permet de parcourir toutes les arêtes.

Supposons que l'arête (a0, , am) ne soit pas parcourue et montrons que l'arête (a1, , am, 0) ne l'est pas non plus.

Si le sommet (a1, , am) n'est pas traversé, c'est clair.

S'il était traversé deux fois, il faudrait, l'une des fois, arriver par (a0, , am).

Il n'est donc traversé qu'une fois, et cette fois-là on choisit d'aller vers (a2, , am, 1) et on parcourt donc l'arête (a1, , am, 1) et non (a1, , am, 0).

De même, (a3, , am, 0, 0), (a4, , am, 0, 0, 0), (am, 0, , 0) ne sont pas parcourues. Mais cette dernière arête vaut (0, 0, , 0) ou (1, 0, , 0) : ce sont les deux arêtes qui terminent l'algorithme, par construction, d'où la contradiction.