11.3. Fermeture transitive

Dans les graphes non-orientés il était possible de connaître tous les sommets accessibles à partir d'un sommet donné : on obtenait alors une composante connexe.

De manière identique, dans un graphe orienté il est intéressant de connaître l'ensemble des sommets accessibles à partir d'un sommet donné en suivant les arcs dans le sens indiqué.

Nous avons montré dans le chapitre précédent que la procédure Visite de l'algorithme DFS visite tous les sommets accessibles depuis le sommet de départ, pour autant qu'ils n'aient pas déjà été visités. Ainsi, si l'on modifie cette procédure de façon à imprimer le nom du sommet visité lors de chaque appel, par exemple en insérant : 

    write (Nom(IndexSommet))

juste à l'entrée de la procédure, on obtient la liste de tous les sommets accessibles à partir du sommet donné.

N.B. Du fait que l'algorithme de recherche en profondeur (DFS) vu au paragraphe 3 du chapitre 10 est prévu pour ne pas traiter un sommet deux fois, cette procédure DFS ne peut pas être utilisée telle quelle (depuis le sommet H on peut accéder à tous les sommets du graphe, pas seulement à I). Cela signifie qu'il ne faut pas ignorer les arcs en pointillé dans l'arbre de parcours. Il faut donc remettre le tableau "NuméroDOrdre" à zéro avant de traiter chaque sommet de départ, c'est-à-dire avant chaque appel non récursif à la procédure Visite.

Pour obtenir tous les sommets accessibles depuis chaque sommet, on peut donc utiliser la même procédure SommetsAccessibles que celle décrite au paragraphe 3.2 du chapitre 10 : 

procedure SommetsAccessibles(NbSommets: integer );

{ Variante de l'algorithme de parcours
  d'un graphe en profondeur avec repré-
  sentation par matrice de connectivité.
  Les déclarations globales ainsi que la
  lecture du graphe sont décrites au
  paragraphe 10.2.1 du chapitre 10 }

var j,
    CmptrVisite,
    IndexSommet : 0..MaxNbSommets;
    NumDOrdre : array[1..MaxNbSommets] of integer;

procedure Visite (IndexSommet : integer);
var AutreSommet : integer;
begin
  CmptrVisite := CmptrVisite + 1;
  NumDOrdre[IndexSommet] := CmptrVisite;
  write (Nom[IndexSommet]);
  for AutreSommet := 1 to NbSommets do
    if Relie[IndexSommet,AutreSommet] and
       { la condition qui suit permet
         d'éviter de boucler au cas où il
         y aurait un cycle dans le graphe}
       (NumDOrdre[AutreSommet] = 0) then
      Visite (AutreSommet);
end; { Visite }

begin { SommetsAccessibles }
  for IndexSommet := 1 to NbSommets do begin
    CmptrVisite := 0;
    for j := 1 to NbSommets do NumDOrdre[j] := 0;
    Visite (IndexSommet);
    writeln;
    end; { for IndexSommet }
end; { SommetsAccessibles }

L'exécution du programme précédent produira le résultat suivant : 

    A B C D E F G J K L M
    B
    C A B D E F G J K L M
    D E F
    E D F
    F D E
    G A B C D E F J K L M
    H A B C D E F G I J K L M
    I A B C D E F G H J K L M
    J A B C D E F G K L M
    K
    L A B C D E F G J K M
    M A B C D E F G J K L

Pour un graphe non-orienté, ce traitement produisait un tableau ayant la propriété que chaque ligne correspondait à une composante connexe du graphe.

Il est à remarquer que certaines lignes du tableau présentent les mêmes sommets.

Comme souvent, il est possible d'ajouter des instructions supplémentaires pour faire plus que simplement imprimer le tableau ci-dessus. Par exemple : ajouter un arc direct de x vers y, s'il existe un moyen d'aller de x vers y.

Le graphe résultant de l'opération qui consiste à ajouter tous les arcs de ce type à un graphe orienté est appelé la fermeture transitive du graphe donné. Dans la plupart des cas, la fermeture transitive est un graphe très dense. Il convient donc d'adopter une représentation matricielle.

Cette opération est analogue à celle qui consiste à déterminer les composantes connexes d'un graphe. Il est alors très facile de répondre à la question :

"Est-il possible d'aller du sommet x vers le sommet y ?"

puisqu'il suffit d'examiner le contenu de la xème ligne, yème colonne pour obtenir la réponse.

Etant donné que l'algorithme de DFS, pour un seul sommet de départ, a une complexité de l'ordre de NbSommets2, utiliser l'algorithme DFS pour déterminer la fermeture transitive exige NbSommets3 étapes dans le cas le plus défavorable, dans la mesure où il faut examiner chaque élément de la matrice pour la recherche DFS déclenchée pour chaque sommet.

Il y a une façon beaucoup plus simple, bien que nécessitant à peu près autant d'étapes, pour déterminer la fermeture transitive d'un graphe orienté représenté par matrice : 

for y := 1 to NbSommets do
  for x := 1 to NbSommets do
    if Relie[x,y] then
      for j := 1 to NbSommets do
        if Relie[y,j] then Relie[x,j] := true;
{ cette dernière instruction conditionnelle
  est équivalente à:
  Relie[x,j]:=Relie[x,j] or Relie[y,j]}

Cette méthode due à S. Warshall en 1962, repose sur la simple observation suivante :

"S'il existe un chemin allant de x vers y et un chemin allant de y vers j, alors il existe un chemin allant de x vers j".

L'idée est de rendre cette observation un peu plus forte de manière à faire le calcul en un seul passage, à savoir :

"S'il existe (dans la fermeture transitive) un chemin pour aller du sommet x vers le sommet y en traversant uniquement des sommets d'indices plus petits que x et qu'il existe un chemin allant de y vers j, alors il existe un chemin allant de x vers j n'employant que des sommets d'indices inférieurs ou égaux à x"

Dans notre exemple (graphe de la figure 11.1), la méthode de Warshall convertit la matrice de connectivité de la figure 11.3 en la matrice de la figure 11.4.

11.4. Le tri topologique

Table des matières.

Site Hosting: Bronco