Chapitre 3 • Éléments de la théorie des graphes
66
Remarques.
• 1 I 1
# M2
3k4
est la matrice codant l’exis tence des che mins d’au plus k arcs
dans le graphe.
• M comporte, dans l’exemple, une colonne entiè re ment for mée de 0 ; c’est
une entrée du graphe (ici, le som met A) ; elle comporte aussi une ligne consti -
tuée uni que ment de 0 : c’est une sor tie du graphe (ici, F).
• Dans un graphe de n som mets, il ne peut y avoir de che min élémentaire de
lon gueur supé rieure à n 2 1 (sans répé tition de som met), si bien que lors -
qu’on recherche la fer me ture tran si tive, (ou ensemble des des cen dants de tous
les som mets) on peut s’arrêter à la puis sance n 2 1 de I 1
# M. En pra tique, on
peut d’ailleurs s’arrê ter dès que :
1 I 1
# M2
3k4 5 1 I 1
# M2
3k214
.
Don nons deux sché mas pos sibles pour le cal cul de M. Posons A 5 I 1
# M. Le
pre mier schéma consiste à cal cu ler :
A
324 5 A # A, puis A
334 5 A
324 # A, puis A
344
, c , puis A
3n214 5 A
3n224 # A,
soit n 2 2 pro duits de matrices.
Or le pro duit de deux matrices n 3 n requiert n
3
mul ti pli cations boo léennes ; en
effet, soient B, C, D des matrices n 3 n telles que : D 5 B # C. Rap pe lons que :
d ij 5 b i1 # c 1j 1
# b i2 # c 2j 1
# c 1
# b in # c nj .
L’éva lua tion de d ij requiert donc n mul ti pli cations boo léennes ; or D comporte
n
2
termes : au total, il faut effec tuer n
2 3 n, soit n
3
mul ti pli cations boo léennes pour
cal cu ler D.
Fina le ment pour éva luer M, on aura 1 n 2 22 3 n
3
mul ti pli cations boo léennes. La
complexité de ce schéma est donc O(n
4
).
Ainsi pour un graphe de n 5 240 som mets, l’on cal cu le rait :
A
2 5 A # A, A
3 5 A
2 # A, c , A
239 5 A
238 # A
soit 238 pro duits de matrices.
On peut donc amé lio rer ce schéma comme suit : on a vu plus haut que :
1 I 1
# M2
3n214 5 1 I 1
# M2
3n4 5 c 5 3I 1
# M4
3n1p4
(p entier > 212 .
Pour ce graphe M 5 A
239
; comme : 2
7 5 128 , 239 , 2
8 5 256, on a aussi :
M 5 A
256
. D’où le schéma de cal cul amé lioré :
A
2 5 A # A , puis A
4 5 A
2 # A
2
, A
8 5 A
4 # A
4
, c , A
256 5 A
128 # A
128
.
ˆ
ˆ
ˆ
ˆ
66
Remarques.
• 1 I 1
# M2
3k4
est la matrice codant l’exis tence des che mins d’au plus k arcs
dans le graphe.
• M comporte, dans l’exemple, une colonne entiè re ment for mée de 0 ; c’est
une entrée du graphe (ici, le som met A) ; elle comporte aussi une ligne consti -
tuée uni que ment de 0 : c’est une sor tie du graphe (ici, F).
• Dans un graphe de n som mets, il ne peut y avoir de che min élémentaire de
lon gueur supé rieure à n 2 1 (sans répé tition de som met), si bien que lors -
qu’on recherche la fer me ture tran si tive, (ou ensemble des des cen dants de tous
les som mets) on peut s’arrêter à la puis sance n 2 1 de I 1
# M. En pra tique, on
peut d’ailleurs s’arrê ter dès que :
1 I 1
# M2
3k4 5 1 I 1
# M2
3k214
.
Don nons deux sché mas pos sibles pour le cal cul de M. Posons A 5 I 1
# M. Le
pre mier schéma consiste à cal cu ler :
A
324 5 A # A, puis A
334 5 A
324 # A, puis A
344
, c , puis A
3n214 5 A
3n224 # A,
soit n 2 2 pro duits de matrices.
Or le pro duit de deux matrices n 3 n requiert n
3
mul ti pli cations boo léennes ; en
effet, soient B, C, D des matrices n 3 n telles que : D 5 B # C. Rap pe lons que :
d ij 5 b i1 # c 1j 1
# b i2 # c 2j 1
# c 1
# b in # c nj .
L’éva lua tion de d ij requiert donc n mul ti pli cations boo léennes ; or D comporte
n
2
termes : au total, il faut effec tuer n
2 3 n, soit n
3
mul ti pli cations boo léennes pour
cal cu ler D.
Fina le ment pour éva luer M, on aura 1 n 2 22 3 n
3
mul ti pli cations boo léennes. La
complexité de ce schéma est donc O(n
4
).
Ainsi pour un graphe de n 5 240 som mets, l’on cal cu le rait :
A
2 5 A # A, A
3 5 A
2 # A, c , A
239 5 A
238 # A
soit 238 pro duits de matrices.
On peut donc amé lio rer ce schéma comme suit : on a vu plus haut que :
1 I 1
# M2
3n214 5 1 I 1
# M2
3n4 5 c 5 3I 1
# M4
3n1p4
(p entier > 212 .
Pour ce graphe M 5 A
239
; comme : 2
7 5 128 , 239 , 2
8 5 256, on a aussi :
M 5 A
256
. D’où le schéma de cal cul amé lioré :
A
2 5 A # A , puis A
4 5 A
2 # A
2
, A
8 5 A
4 # A
4
, c , A
256 5 A
128 # A
128
.
ˆ
ˆ
ˆ
ˆ