UNIVERSITÉPIERRE & MARIE CURIE
Licence informatique
algorithmique I
1998-99





Interrogation écrite
Décembre 1998
Corrigé
--°--





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.
  1. 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.
  2. 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.

cqfd




This document was translated from LATEX by HEVEA.