Question 2
On rappelle qu'une liste L= est un tri
topologique des éléments de S si et seulement si pour tout arc
(x,y)Î A, x est placéavant y dans L.
Si L est une liste, on rappelle que x.L désigne la liste obtenue
en rajoutant x devant L. Soit l'algorithme récursif Ltop :
Proc Ltop(s)
Tant que s poss`ede un successeur x non visit'e faire
Ltop(x)
Fin-tant-que
L¬ s.L
Fin-proc
Montrez que si G=(S,A) est un graphe orientésans cycle qui ne
possède qu'une seule racine r et si L est vide au départ alors
L contient un tri topologique de S aprés la terminaison de Ltop(r)
Corrigé
On montre, dans un premier temps que lorsqu'un sommet x est placédans L, x n'a pas de prédécesseur dans L.
Soient x1, .., xk les prédécesseurs de x, soit xi l'un
d'eux. On raisonne pas cas suivant que Ltop(xi) est appeléavant Ltop(x) ou non.
Si Ltop(xi) est appeléavant Ltop(x) alors
Ltop(x) est appelédans la boucle ``Tant que'' de l'appel
àLtop(xi) et xi n'étant placéqu'en sortie de
boucle dans L, il s'y retrouve avant x.
Si Ltop(xi) est appeléaprés Ltop(x) c'est
qu'il existe jÎ[1..i[ tel que Ltop(xj) est appeléavant Ltop(xi). Au retour de Ltop(xj), x est dans
la liste L, il y est donc au moment de l'appel àLtop(xi) et xi sera donc placédans L avant x.
Puisque tous les prédécesseurs de x sont placés dans L avant
x, et que L est vide au départ, L ne contient donc aucun
prédécesseur de x lorsque celui-ci y est placé.
Puisque l'on suppose que L est vide au départ elle ne contient, au
retour de Ltop(r) que des sommets placés par la suite des
appels récursifs. On remarque que la suite des appels récursifs àLtop
détermine un parcours en profondeur de G. D'où, puisque r est
racine, tous les éléments de S sont dans L au retour de Ltop(r). On obtient donc, en vertu de notre premier résultat, une
énumération s1, .., sn de S telle que pour tout
i,jÎ[1..n], si i > j alors (xi, xj)ÏA; c'est àdire, par contraposée, que si (xi, xj)Î A alors i < j.