Digraphes sans circuits

Théorème 9
Le digraphe G = (V, E) est sans circuits si et seulement si on peut attribuer un nombre r(v), appelé le rang de v, à chaque sommet v de manière que pour tout arc (u, v) de G on ait r(u) < r(v).

Preuve

Si G comporte un circuit C, il n'est pas possible de trouver de tels nombres r(i) car, autrement, considérant r(j) = max {r(i) | i

C} et l'arc (j, k)

C on aurait r(j)

r(k) en contradiction avec la définition de r( ).
Réciproquement, si G n'a pas de circuits, il existe au moins un sommet sans prédécesseurs dans G (sans cela, en remontant successivement d'un sommet à un prédécesseur, on finirait par fermer un circuit). Ainsi, on peut attribuer séquentiellement des valeurs r( ) aux sommets du graphe à l'aide de l'algorithme qui suit, ce qui conclura la démonstration.

Algorithme de calcul du rang

Donnée : digraphe G = (V, E) sans circuit.
Résultat : rang r(v) de chaque sommet v

V du digraphe G.
Début
   r := 0, X := V
   R: l'ensemble des sommets de X sans prédécesseurs dans X
   Tant que X n'est pas vide faire
      Début
         r(v) := r pour tout sommet v

R
         X := X - R
         R: l'ensemble des sommets de X sans prédécesseurs dans X
         r := r + 1
      Fin
Fin.

Exercice

Attribuez un rang aux sommets du digraphe ci-dessous en utilisant l'algorithme de calcul du rang:

Le corrigé est disponible, mais seulement pour les visiteurs autorisés!

Didier Müller, 18.4.03