Fermeture transitive : sommes booléennes et algorithme de Roy-Warshall

La fermeture transitive d'un graphe G est le graphe Ĝ qui a les mêmes sommets que G, avec un arc de x vers y chaque fois qu'il existe dans G un chemin (de longueur quelconque, au moins 1) de x vers y. Sa matrice M̂ répond d'un coup à la question « peut-on aller de x à y ? » pour tous les couples de sommets. On l'obtient par une somme de puissances booléennes de la matrice d'adjacence, ou plus vite avec l'algorithme de Roy-Warshall. Ce chapitre présente les deux méthodes, la lecture de la fermeture (circuits, arcs à ajouter) et ses usages en informatique.

Définition et exemple

On reprend le graphe G du ticket (arcs A → B, A → E, B → A, B → C, C → C, C → D, D → C, D → E). Depuis A, on peut atteindre B (directement), E (directement), C (par A → B → C), D (par A → B → C → D) et A lui-même (par A → B → A). Dans la fermeture transitive Ĝ, A a donc pour successeurs A, B, C, D, E.

En faisant de même pour chaque sommet, on obtient la matrice de Ĝ :

Interprétation pour les tickets : depuis l'état nouveau (A) ou attribué (B), un ticket peut atteindre n'importe quel état ; depuis l'état en cours (C) ou résolu (D), il ne peut plus revenir à nouveau ou attribué, mais peut atteindre C, D et E ; un ticket clos (E) n'atteint plus rien.

Méthode 1 : la somme des puissances booléennes

Un chemin de x vers y a une longueur 1, ou 2, ou 3… Or M^[p] signale les chemins de longueur p (chapitre 3). La somme booléenne de toutes ces matrices signale donc les chemins de longueur quelconque. Et il suffit de s'arrêter à la puissance n, le nombre de sommets :

Pourquoi n suffit-il ? Un chemin qui repasse par un sommet contient un circuit qu'on peut supprimer pour obtenir un chemin plus court ayant la même origine et la même extrémité. Entre deux sommets différents, on peut donc toujours trouver un chemin élémentaire, de longueur au plus n − 1 ; pour revenir à son point de départ, un circuit sans répétition a au plus n arcs.

Sur le graphe G (n = 5), les matrices M, M^[2] et M^[3] ont été calculées au chapitre 3. Leur somme booléenne :

• ligne A : (0 1 0 0 1) ⊕ (1 0 1 0 0) ⊕ (0 1 1 1 1) = (1 1 1 1 1) ;
• ligne B : (1 0 1 0 0) ⊕ (0 1 1 1 1) ⊕ (1 0 1 1 1) = (1 1 1 1 1) ;
• ligne C : (0 0 1 1 0) ⊕ (0 0 1 1 1) ⊕ (0 0 1 1 1) = (0 0 1 1 1) ;
• ligne D : (0 0 1 0 1) ⊕ (0 0 1 1 0) ⊕ (0 0 1 1 1) = (0 0 1 1 1) ;
• ligne E : que des 0.

On obtient déjà M̂. Ajouter M^[4] et M^[5] ne change plus rien.

Méthode 2 : l'algorithme de Roy-Warshall

Calculer toutes les puissances demande beaucoup de produits. L'algorithme de Roy-Warshall (publié par Bernard Roy en 1959 et Stephen Warshall en 1962) obtient la fermeture transitive en travaillant directement sur les lignes de la matrice.

Le principe. On traite les sommets un par un, dans l'ordre. Quand on traite le sommet k, on autorise k comme sommet intermédiaire : tout sommet i qui atteint k atteint aussi tout ce que k atteint.

L'algorithme.

1. Pars de la matrice M.
2. Pour chaque sommet k, dans l'ordre :
   • repère les lignes i qui ont un 1 dans la colonne k ;
   • remplace chacune de ces lignes par sa somme booléenne avec la ligne k (ligne i ⊕ ligne k).
3. Après le dernier sommet, la matrice obtenue est M̂.

En pseudo-code :

pour k allant de 1 à n
    pour i allant de 1 à n
        si M[i][k] = 1 alors
            pour j allant de 1 à n
                M[i][j] ← M[i][j] OU M[k][j]

Sur le graphe G, en partant de M :

La matrice finale est bien M̂. Remarque que chaque étape utilise la matrice telle qu'elle est à ce moment-là : à l'étape k = B, la ligne B a déjà été enrichie à l'étape k = A, et c'est cette ligne enrichie qu'on ajoute à la ligne A.

En Python, l'algorithme tient en quelques lignes :

def roy_warshall(M):
    """Matrice de la fermeture transitive (M n'est pas modifiée)."""
    n = len(M)
    F = [ligne[:] for ligne in M]          # copie de M
    for k in range(n):
        for i in range(n):
            if F[i][k] == 1:
                F[i] = [F[i][j] | F[k][j] for j in range(n)]
    return F

M = [[0, 1, 0, 0, 1],
     [1, 0, 1, 0, 0],
     [0, 0, 1, 1, 0],
     [0, 0, 1, 0, 1],
     [0, 0, 0, 0, 0]]
for ligne in roy_warshall(M):
    print(ligne)
# [1, 1, 1, 1, 1]
# [1, 1, 1, 1, 1]
# [0, 0, 1, 1, 1]
# [0, 0, 1, 1, 1]
# [0, 0, 0, 0, 0]

L'opérateur | est le « ou » bit à bit de Python : sur des 0 et des 1, c'est exactement la somme booléenne.

Lire une fermeture transitive

Les arcs à ajouter. Les arcs de Ĝ qui ne sont pas dans G sont les cases à 1 dans M̂ et à 0 dans M. Pour G : M̂ contient 5 + 5 + 3 + 3 + 0 = 16 coefficients égaux à 1, M en contient 8, donc on ajoute 8 arcs : (A, A), (A, C), (A, D), (B, B), (B, D), (B, E), (C, E) et (D, D). Au sujet de l'E3 2026, la question « combien d'arcs faut-il ajouter pour obtenir la fermeture transitive ? » se traitait exactement ainsi.

Les circuits. Un 1 sur la diagonale de M̂, en (x, x), signifie qu'il existe un chemin de x vers x : x appartient à un circuit. Dans G, A, B, C et D sont sur des circuits, pas E.

Les sommets qui s'atteignent mutuellement. Si M̂ a un 1 en (x, y) et en (y, x), alors x et y sont sur un même circuit : on peut aller de l'un à l'autre et revenir. Dans G, A et B s'atteignent mutuellement, C et D aussi, mais pas A et C (on va de A à C, pas de C à A).

Les sommets accessibles depuis tout le monde. Une colonne de M̂ remplie de 1 (sauf éventuellement pour des puits) désigne un sommet que tous les autres peuvent atteindre. Dans G, la colonne E a des 1 pour A, B, C, D : un ticket finit toujours par pouvoir être clos.

Ce que cela donne en informatique

• Accessibilité réseau : dans le graphe des communications autorisées par des règles de pare-feu, la fermeture transitive dit quelles machines peuvent joindre quelles autres, directement ou par rebond. C'est la question que se pose un attaquant qui a pris pied sur un poste.
• Groupes imbriqués : dans un annuaire Active Directory, un utilisateur membre d'un groupe lui-même membre d'un autre groupe hérite des droits des deux. Les droits effectifs se lisent dans la fermeture transitive du graphe « est membre de ».
• Dépendances logicielles : installer un paquet installe toute la fermeture transitive de ses dépendances, ce que fait un gestionnaire comme apt ou npm.
• Bases de données : une requête SQL récursive (WITH RECURSIVE) parcourt une hiérarchie stockée dans une table, par exemple tous les subordonnés directs et indirects d'un manager : elle calcule une ligne de la fermeture transitive (CTE récursives).

Exercices