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 :
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 :
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.
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).
neato | dot |
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.
Un graphe orienté sans cycle (en anglais Directed Acyclic Graph) est noté dans la suite par les lettres DAG.
On démontre ce théorème en deux parties, chacune étant réciproque de l'autre.
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.
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.
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.
Une composante fortement connexe d'un graphe orienté est un sous-graphe de ce graphe, qui est fortement connexe.
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 :
Par exemple, il n'y a pas moyen d'aller de 7 à 1.
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 :
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.
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é.
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 :
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 :
Les composantes fortement connexes d'un graphe orienté peuvent servir à résoudre des problèmes 2-SAT.