"'O
0
c
:J
0
:<:;
li)
.,,
..--t
c::
:l
0
~
N
"
@
~
.......
0
J::
:;
O'l
"'
·;::::
c::
0
>c::
o.
c::
0
.9
u
ü
:l
.,,
2
o.
~
"
:;
0
11
.,,
0
c:
:l
0
QJ
6.2 • Chemins d'un graphe
Exemple
0 l 0
1 1 0
Soit M = 1 1 0 et M'= 1 0 0
1 0 0
0 0 1
L'addition booléenne des deux matrices se note
M ffi M' et vaut
1 1 0
MffiM'= l 1 0
1 0 1
0 2 0
En pratique, on peut calculer M + M ' = 2 1 0 et rendre cette matrice
1 0 l
booléenne en gardant les 0 et les 1, et en remplaçant par 1 tous les coefficients
supérieurs à 1.
On peut aussi faire la multiplication booléenne des matrices, qui se note M ® M'.
1 0 0
En pratique, il est plus simple de calculer MM'= 2 1 0 et de rendre la matrice
1
0
booléenne.
1 0 0
Ainsi, M®M'= 1 1 0
1 0
On peut également définir des puissances booléennes, notées M [Pl .
1 1 0
M
2 = 1 2 0
0 1 0
1 1 0
donc M[
2 l = 1 1 0
0 1 0
Soit M et M' deux matrices booléennes :
• La somme booléenne de M et M ' est notée M EB M ' : elle est obtenue en faisant
les sommes booléennes des coefficients des deux matrices.
• On peut définir de même le produit booléen noté M ® M' .
• La puissance booléenne d'exposant p de la matrice M se note M[pJ et vaut
M @ M @ ... @ M, produit de p matrices égales à M.
Propriété 6.2
Soit M la matrice d ' adjacence d'un graphe ayant n sommets a 1 , a 2 , ... ,an et soit
M[p] =(mi) la matrice booléenne d'exposant p.
Si mi,J :;z=O alors il existe au moins un chemin de longueur p reliant le sommet ai
au sommet ai"
153