Problèmes de chemins
115
La matrice
complète est :
Un raisonnement analogue nous montre que
fournit nombre de chemins de longueur
3 existant entre chaque paire de sommets.
Enfin
, qui fournit les chemins de longueur égale à 4 est :
On vérifiera sans peine que
, ce qui est évident sur le graphe en question.
D'une façon générale, si
à partir d'un certain exposant, cela veut dire que le
graphe est sans circuit. En effet, si le graphe avait un circuit, il est évident que pour tout
entier on pourrait choisir deux sommets du circuit tels qu'il existe un chemin de
longueur entre ces deux sommets, donc que
, ce qui est incompatible avec
= 0 à partir d'un certain .
Réciproquement, si le graphe est sans circuit, et puisqu'il est fini, un chemin est au plus
de longueur
, si
; on est alors sûr que pour
L'examen successif des matrices,
,…
répond au problème 1. Pour un couple
de sommets si un
est non nul, c'est qu'il existe un chemin menant du sommet
au sommet .
Cependant, toujours dans le cadre du problème 1, on préfère utiliser la matrice
d'une
autre manière.
Les éléments de
seront à présent considérés comme les éléments du calcul booléen ;
ces éléments (0 et 1) peuvent, on le sait, se combiner suivant les deux opérations :
addition (+) et multiplication (.) booléennes suivant les tables :