Parcours en profondeur d'un graphe orienté

I/ Recherche de cycles

Il y a deux manières d'ordonner les sommets d'un graphe orienté par un parcours en profondeur, selon qu'on enregistre un sommet à la première visite (préordre) ou après l'avoir traité en entier (postordre). Par exemple pour ce graphe, en commençant le parcours par A :

%3 A A B B A->B E E A->E C C C->B D D D->C E->B E->C E->D F F F->A F->D F->E

Un parcours préfixe donne ABECDF et un parcours suffixe donne BCDEAF.

On obtient le même arbre couvrant avec les deux ordres de parcours :

%3 A A B B A->B E E A->E C C D D E->C E->D F F F->A

Le postordre permet de détecter la présence éventuelle d'un cycle : dans un cycle il y a un arc S→T tel que T vient après S dans le postordre. Par exemple avec le postordre BCDEAF :

Donc le graphe orienté ci-dessus n'a pas de cycle.

II/ Ordre topologique

Un ordre topologique d'un graphe orienté est un ordre ≺ de ses sommets tel que s'il y a un arc S→T alors S≺T. La commande dot de Linux essaye de dessiner les graphes en suivant un ordre topologique (s'il en existe un).

neatodot
%3 A A B B A->B E E A->E C C C->B D D D->C E->B E->C E->D F F F->A F->D F->E %3 A A B B A->B E E A->E C C C->B D D D->C E->B E->C E->D F F F->A F->D F->E

L'ordre topologique trouvé par dot est (de haut en bas) F≺A≺E≺D≺C≺B. On constate que c'est l'ordre inverse de l'ordre postfixe. Ceci fournit un algorithme pour calculer un ordre topologique : il suffit de calculer l'inverse d'un postordre.

1) DAG

Un graphe orienté sans cycle (en anglais Directed Acyclic Graph) est noté dans la suite par les lettres DAG.

2) Théorème

Un graphe orienté est un DAG si et seulement s'il possède un ordre topologique.

On démontre ce théorème en deux parties, chacune étant réciproque de l'autre.

Condition nécessaire

En supposant qu'un graphe est un DAG, on peut construire un ordre topologique par cet algorithme : parcourir le graphe en profondeur en enregistrant un postordre, puis inverser ce postordre. Comme il n'y a pas de cycles (par hypothèse) alors l'inverse du postordre est bien une relation d'ordre.

Condition suffisante

S'il existe un cycle alors le graphe comprend trois sommets S, T et U tels que S≺T, T≺U et U≺S. L'ordre ≺ ne peut donc pas être un ordre topologique.

III/ Forte connexité

1) Définition

Un graphe orienté est dit fortement connexe si, depuis chaque sommet, il est possible d'aller à n'importe quel autre sommet en « suivant les flèches ».

Par exemple le graphe ci-dessous n'est pas fortement connexe car, depuis le sommet E, il n'y a aucun chemin vers le sommet A.

%3 A A B B A->B E E A->E C C C->B D D D->C E->B E->C E->D F F F->A F->D F->E

2) Composantes fortement connexes

Une composante fortement connexe d'un graphe orienté est un sous-graphe de ce graphe, qui est fortement connexe.

IV/ Algorithme de Kosaraju

En 1978, Rao Kosaraju a trouvé un algorithme donnant les composantes fortement connexes d'un graphe orienté. On va le décrire sur un exemple : le graphe de Frances Allen. Ce graphe n'est pas fortement connexe :

%3 1 1 2 2 1->2 3 3 2->3 7 7 2->7 4 4 3->4 5 5 3->5 4->3 6 6 4->6 5->6 6->7 7->2 8 8 7->8

Par exemple, il n'y a pas moyen d'aller de 7 à 1.

1) Graphe inversé

En remplaçant chaque arc a→b par l'arc inverse b→a, on obtient un nouveau graphe orienté, appelé inverse du précédent. L'inverse du graphe de Frances Allen est :

%3 1 1 2 2 2->1 7 7 2->7 3 3 3->2 4 4 3->4 4->3 5 5 5->3 6 6 6->4 6->5 7->2 7->6 8 8 8->7

2) Parcours en profondeur

L'algorithme de Kosaraju commence par un parcours en profondeur du graphe inversé. Ce parcours se fait en postordre et donne (en commençant par 1) 1,3,4,5,6,7,2,8. C'est ce postordre que l'on enregistre.

3) Ordre de parcours du graphe

On inverse le postordre 1,3,4,5,6,7,2,8. On se servira donc de l'ordre 8,2,7,6,5,4,3,1 pour parcourir le graphe orienté.

4) Parcours du graphe

On parcourt le graphe (par exemple en profondeur) en commençant par 8, puis comme 8 n'a pas de successeur, on passe à 2 etc. On obtient alors les composantes fortement connexes et la manière dont elles sont reliées :

%3 1 1 2 2 1->2 3 3 2->3 7 7 2->7 4 4 3->4 5 5 3->5 4->3 6 6 4->6 5->6 6->7 7->2 8 8 7->8

4) Ordre topologique

Le graphe des composantes fortement connexes ne possède pas de cycle (sinon ce cycle serait fortement connexe) donc on peut le munir d'un ordre topologique :

%3 1 1 2 234567 1->2 3 8 2->3

Les composantes fortement connexes d'un graphe orienté peuvent servir à résoudre des problèmes 2-SAT.