La fermeture transitive d'un graphe 
est la relation
transitive minimale contenant la relation 
, il s'agit d'un
graphe 
tel que 
si et seulement s' il
existe un chemin 
dans 
d'origine 
et d'extrémité 
.
Figure: Un graphe et sa fermeture transitive
Le calcul de la fermeture transitive permet de répondre aux
questions concernant l'existence de chemins entre et dans
et ceci pour tout couple de sommets 
. Ce calcul complet n'est pas
vraiment utile s'il s'agit de répondre un petit nombre de fois à
des questions sur l'existence de chemins entre des couples de sommets,
on utilise alors des algorithmes qui seront décrits dans les
paragraphes suivants. Par contre lorsque l'on s'attend à avoir à
répondre de nombreuses fois à ce type de question il est
préférable de calculer au préalable 
, la réponse à
chaque question est alors immédiate par simple consultation d'un des
c
fficients de la matrice d'adjacence de 
. On dit que l'on
effectue un prétraitement, opération courante en
programmation dans maintes applications, ainsi le tri des éléments
d'un fichier peut aussi être considéré comme un prétraitement
en vue d'une série de consultations du fichier, le temps mis pour
trier le fichier est récupéré ensuite dans la rapidité de la
consultation. Le calcul de la fermeture transitive d'un graphe se
révèle très utile par exemple, dans certains
compilateurs-optimiseurs: un graphe est associé à chaque
procédure d'un programme, les sommets de ce graphe représentent
les variables de la procédure et un arc entre la variable a et
la variable b indique qu'une instruction de calcul de a
fait apparaître b dans son membre droit. On l'appelle
souvent graphe de dépendance. La fermeture transitive de ce
graphe donne ainsi toutes les variables nécessaires directement ou
indirectement au calcul de a; cette information est utile
lorsque l'on veut minimiser la quantité de calculs à effectuer en
machine pour l'exécution du programme.
Le calcul de s'effectue par itération de l'opération de
base 
qui ajoute à 
les arcs 
tels que est
un prédécesseur de et 
un de ses successeurs. Plus
formellement on pose :
Figure: L'effet de l'opération 
: les arcs ajoutés sont en pointillé
Cette opération satisfait les deux propriétés suivantes:
Preuve La première partie est très simple, on l'obtient en
remarquant que 
implique 
et que
implique 
.
Pour la seconde partie, il suffit de vérifier que si 
appartient à 
il appartient aussi à
, le résultat s'obtient ensuite par raison de
symétrie. Si 
alors ou bien 
ou bien 
et 
. Dans le premier
cas 
pour tout 
implique
. Dans le second cas il y a plusieurs
situations à considérer suivant que ou 
appartiennent ou non à ; l'examen de chacune d'entre elles permet
d'obtenir le résultat. Examinons en une à titre d'exemple,
supposons que et 
, comme on a 
, ceci implique 
et 
Preuve On se convainc facilement que 
contient
l'itérée de l'action des 
sur , la partie la plus
complexe à prouver est que 
contient . Pour cela on considère un
chemin joignant deux sommets et de alors ce chemin
s'écrit
ainsi 
les
propriétés démontrées ci-dessus permettent d'ordonner les
suivant leurs numéros croissants; le fait que 
, pour tout 
permet ensuite de conclure.
De ces deux résultats on obtient l'algorithme suivant pour le calcul
de la fermeture transitive d'un graphe, il est en général
attribué à Roy et Warshall:
procedure PHI (var m: GrapheMat; x: IntSom; n: integer);
var
u, v: IntSom;
begin
for u := 1 to n do
if (m[u, x] = 1) then
for v := 1 to n do
if (m[x, v] = 1) then
m[u, v] := 1;
end;
procedure FermetureTransitive (var m: GrapheMat; n: integer);
var
x: IntSom;
begin
for x := 1 to n do
PHI(m, x, n);
end;
Remarque L'algorithme ci-dessus effectue un nombre d'opérations que
l'on peut majorer par 
, chaque exécution de la procédure
PHI pouvant nécessiter 
opérations; cet algorithme est
donc meilleur que le calcul des puissances successives de la matrice
d'adjacence.