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





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





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.




This document was translated from LATEX by HEVEA.