3.1 Élé ments de la théo rie des graphes
67
© Dunod – Toute reproduction non autorisée est un délit.
où à chaque ité ra tion, on cal cule le carré de la matrice de l’ité ra tion pré cé dente.
Ce schéma ne néces site que 8 pro duits de matrices (au lieu de 238...) et dans le cas
géné ral : E* [log 2 (n – 1)] pro duits de matrices, où E*[x] désigne la par tie entière de
x par excès : ici n 2 1 5 239 ; puisque 2
7 , 239 , 2
8
, on a : 7 , log 2 239 , 8 et
E* 3log 2 2394 5 8. La complexité de la méthode matricielle avec ce schéma amé -
lioré n’est plus que de O(n
3
log 2 n), qui est effectivement moindre que O(n
4
).
Nous allons main te nant don ner l’algo rithme de Roy- Warshall, de complexité
moindre : O(n
3
) qui, lui aussi, déter mine la fer me ture tran si tive d’un graphe (cet
algo rithme a été aussi trouvé indé pen dam ment par le Pr Louis Nolin).
1. A d M
2. pour i 5 1 à n faire
3. A(i, i) d 1
4. pour k 5 1 à n faire
5. pour j 5 1 à n faire
6.
pour i 5 1 à n faire
7.
A1 i, j2 d A1 i, j2 1
# A1 i, k2 3 A 1 k, j2
La figure 3.7 illustre sur l’exemple pré cé dent le dérou le ment de cet algo rithme ;
lors de chaque ité ra tion k on a enca dré cer tains 1 : ils cor res pondent aux arcs ajou -
tés, lors de cette ité ra tion, au graphe cou rant. Les som mets sont consi dé rés dans
l’ordre A, B, C, D, E, F et les rela tions de réflexi vité (boucles) ne sont pas prises en
compte. Ci- dessous ces som mets sont notés a, b, c, d, e et f (pour évi ter la confu sion
entre la matrice A et le som met A).
1 1 0 0 1 0
a b c d e f
0 1 1 0 0 0
0 0 1 1 0 0
0 0 0 1 0 1
0 1 1 0 1 1
0 0 0 0 0 1
a
b
c
d
e
f
a b c d e f
1 0 0 1 0
0
1 0 0 0
0 0
1 0 0
0 0 0
0 1
0 1 1 0
1
0 0 0 0 0
k = 1 (cf a)
1 1 1 1 1
0
1 1 0 1
0 0
1 0 1
0 0 0
0 1
0 1 1 1
1
0 0 0 0 0
k = 5 (cf e)
Initialisation
A =
1 1 1 1 1
0
1 1 0 1
0 0
1 0 1
0 0 0
0 1
0 1 1 1
1
0 0 0 0 0
k = 6 (cf f )
= M
a b c d e f
1 1 0 1 0
0
1 0 0 0
0 0
1 0 0
0 0 0
0 1
0 1 1 0
1
0 0 0 0 0
k = 2 (cf b)
1 1 1 1 1
0
1 1 0 1
0 0
1 0 1
0 0 0
0 1
0 1 1 1
1
0 0 0 0 0
k = 4 (cf d)
a
b
c
d
e
f
1 1 1 1 0
0
1 1 0 0
0 0
1 0 0
0 0 0
0 1
0 1 1 1
1
0 0 0 0 0
k = 3 (cf c)
a b c d e f