Utilisation de l'arborescence de Trémaux

On étudie tout d'abord la numérotation des sommets d'un graphe que l'on obtient par l'algorithme de Trémaux. On la rappelle ici en y ajoutant une instruction de numérotation.

var
    numero: SomVect;
    nu: integer;
procedure TremauxRec (u: Sommet; var pere: Arbo);
    var
        k: integer;
        v: Sommet;
    begin
    nu := nu + 1;
    numero[u] := nu;
    k := 1;
    v := succ[u, k];
    while (v <> Omega) do
        begin
        if (pere[v] = Omega) then
            begin
            pere[v] := u;
            TremauxRec(v, pere);
            end;
         k := k + 1;
         v := succ[u, k];
         end;
    end;

for i:=1 to n do 
    pere[i] := Omega;
pere[x] := x;
nu := 0;
TremauxRec (x,pere);

On supposera dans la suite que les sommets sont numérotés de cette façon, ainsi lorsqu'on parlera du sommet , cela voudra dire le ème sommet rencontré lors du parcours de Trémaux et cela évitera certaines lourdeurs d'écriture. La proposition ci-dessus se traduit alors par le fait suivant:

Si est un descendant de dans et si un sommet satisfait :

est aussi un descendant de dans cette arborescence.

Les liens entre arborescence de Trémaux de racine et les composantes fortement connexes sont dus à la proposition suivante, que l'on énoncera après avoir donné une définition.

  
Figure: Un exemple de sous-arborescence

Ainsi tout élément de est extrémité d'un chemin d'origine et ne contenant que des arcs de .

Preuve Cette proposition contient en fait deux conclusions; d'une part elle assure l'existence d'un sommet de tel que tous les éléments de sont des descendants de dans , d'autre part elle affirme que pour tout de tous les sommets du chemin de joignant à sont dans .

La deuxième affirmation est simple à obtenir car dans un graphe tout sommet situé sur un chemin joignant deux sommets appartenant à la même composante fortement connexe est aussi dans cette composante. Pour prouver la première assertion choisissons pour le sommet de plus petit numéro de et montrons que tout de est un descendant de dans . Supposons le contraire, étant dans la même composante que , il existe un chemin d'origine et d'extrémité . Soit le premier sommet de qui n'est pas un descendant de dans et soit le sommet qui précède dans . L'arc n'est pas un arc de , ni un arc de descente, c'est donc un arc de retour ou un arc transverse et on a :

L'arborescence étant préfixe on en déduit que est descendant de d'où la contradiction cherchée.