114
Recherche opérationnelle
on a la matrice binaire associée suivante :
Remarque : la somme des éléments d'une ligne donne le demi-degré extérieur du
sommet correspondant à la ligne; de même la somme des éléments d'une colonne fournit
le demi-degré intérieur du sommet associé à cette colonne.
Effectuons maintenant le produit de
par elle-même, les opérations correspondantes
étant les opérations classiques dans l'anneau des matrices et le corps des réels.
Un élément
de la matrice
sera donné par :
j
k
k
i
k
j
i
a
a
a =
(2)
Le produit
est égal à 1 si
et
sont égaux à 1, et égal à 0 si l'un au moins des
deux termes
et
est nul.
Or
s'il existe un arc reliant
et
s'il existe un arc reliant
. En
conséquence, si
c'est qu'il existe un chemin de longueur 2 entre
.
Dans ces conditions,
représente le nombre de chemins de longueur 2 entre
. Par
exemple :
1
=
0
1
0
1
0
1
0
0
1
1
0
0
=
(2)
13
a
Il y a un chemin de longueur 2 entre 1 et 3 : c'est le chemin (1, 2, 3).