Question 1 Si G est un graphe orienté, on dit qu'un sommet
s de G est une racine de G si et seulement si s ne
possède pas de prédécesseur dans G.
Montrez qu'un graphe orientésans cycle possède nécessairement
une racine au moins.
Donnez un algorithme Rset calculant l'ensemble des racines d'un
graphe orientésans cycle.
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)
Question 3 On suppose que G est orientéet sans cycle mais
possède éventuellement plusieurs racines.
En utilisant Rset et Ltop, donnez un algorithme calculant
un tri topologique de l'ensemble des sommets de G.