116
Recherche opérationnelle
Soit alors la matrice , considérée comme formée d'éléments booléens et faisons le
produit
où l'opération « produit matriciel » garde la même signification
qu'auparavant, mais où les opérations sur les
sont booléens. Soit alors :
nj
in
kj
ik
j
j
i
ij
a
a
a
a
a
a
a
a
a
.
.....
.
.....
.
.
.
=
2
12
1
1
(2)
Il est clair que si
, cela signifie qu'il existe au moins un chemin de longueur 2
entre et et
signifie qu'il n'existe pas de chemins de longueur 2 entre
De même
, calculée sur la base des opérations ci-dessus permet de savoir s'il existe
un chemin de longueur entre un sommet quelconque et un autre.
Si alors, on fait la somme
avec : matrice unité,
la matrice obtenue permet de savoir s'il existe un chemin entre un sommet quelconque
et un autre (avec la convention: il existe un chemin de longueur entre et ).
Par exemple si l'on prend une ligne de , associée a un sommet quelconque, cette
ligne fournit tous les sommets que l'on peut atteindre par un chemin partant de .Cet
ensemble de sommets s'appelle la fermeture transitive de . Si l'on se réfère à
l'application définie plus haut, la fermeture transitive de peut s'écrire:
Pratiquement, pour calculer
, il suffit d'effectuer la somme ci-dessus jusqu'à
. En
effet :
a) si le graphe est sans circuit,
b) si le graphe comporte des circuits, il existe des
non nuls pour
; mais cela
signifie qu'il existe entre et un chemin de longueur qui emprunte au moins un
circuit.
En enlevant tous les circuits de ce chemin, on obtient un chemin reliant à de longueur
inférieure à . Donc il existe
tel que
; et l'élément
avec
n'ajoute rien à