Chapitre 3 • Éléments de la théorie des graphes
68
(3)
(2)
4
(3)
(3)
(4)
(4)
C
B
A
E
F
D
Figure 3.7 : Un exemple d’exé cu tion de l’algo rithme de Roy- Warshall
L’ité ra tion k 5 1 n’ajoute aucun arc car a est une entrée. L’ité ra tion 2 ajoute
l’arc (a, c) car le graphe cou rant comporte (a, b) et (b, c), l’itération 3 ajoute les arcs
(a, d ), (b, d ) et (e, d ) etc. L’ité ra tion 6 n’ajoute aucun arc car f est une sor tie. La
matrice M se déduit de M en éga lant à 1 tous les termes de sa dia go nale : M 5 M 1
# I,
où M est la matrice obtenue en fin d’application de l’algorithme.
Le lec teur inté ressé pourra consul ter les ouvrages cités en biblio gra phie pour
trou ver la preuve de cet algo rithme.
3.1.4 Forte connexité
Cette notion, contrai re ment à celle de la connexité, fait appel à l’orien ta tion du
graphe. Soit la rela tion binaire défi nie sur l’ensemble des som mets X : « il existe
au moins un che min de x à y et au moins un che min de y à x » ; elle est réflexive
(de tout som met x vers lui- même existe un che min de lon gueur 0), symé trique,
(par défi ni tion), et tran si tive : s’il existe un che min de x à y et un che min de y à z,
la mise bout à bout ou « conca té na tion » de ces deux che mins four nit un che min
de x à z ; de même avec un che min de y à x et un che min de z à y.
C’est donc une rela tion d’équi va lence. Les classes de cette rela tion d’équi va lence
se nomment les compo santes for te ment connexes du graphe
1
.
Un graphe est for te ment connexe s’il comporte une seule compo sante for te ment
connexe. Si l’on ajoute l’arc (d, a) au graphe de la Figure 3.6 (ou 3.7), il devient
fortement connexe.
Consi dé rons, à titre d’exemple, le graphe de la figure 3.8 pour lequel k X k 5 n 5 7.
Si l’on observe la matrice M 5 (I 1
# M)
364
, on constate qu’un nou vel arran ge ment
des colonnes et des lignes per met de faire appa raître des matrices car rées, uni que -
ment for mées de 1, s’appuyant sur la dia go nale prin ci pale.
1. Dans toute compo sante for te ment connexe c, il existe donc un che min entre tout couple de
som mets de c.
ˆ
ˆ
ˆ
68
(3)
(2)
4
(3)
(3)
(4)
(4)
C
B
A
E
F
D
Figure 3.7 : Un exemple d’exé cu tion de l’algo rithme de Roy- Warshall
L’ité ra tion k 5 1 n’ajoute aucun arc car a est une entrée. L’ité ra tion 2 ajoute
l’arc (a, c) car le graphe cou rant comporte (a, b) et (b, c), l’itération 3 ajoute les arcs
(a, d ), (b, d ) et (e, d ) etc. L’ité ra tion 6 n’ajoute aucun arc car f est une sor tie. La
matrice M se déduit de M en éga lant à 1 tous les termes de sa dia go nale : M 5 M 1
# I,
où M est la matrice obtenue en fin d’application de l’algorithme.
Le lec teur inté ressé pourra consul ter les ouvrages cités en biblio gra phie pour
trou ver la preuve de cet algo rithme.
3.1.4 Forte connexité
Cette notion, contrai re ment à celle de la connexité, fait appel à l’orien ta tion du
graphe. Soit la rela tion binaire défi nie sur l’ensemble des som mets X : « il existe
au moins un che min de x à y et au moins un che min de y à x » ; elle est réflexive
(de tout som met x vers lui- même existe un che min de lon gueur 0), symé trique,
(par défi ni tion), et tran si tive : s’il existe un che min de x à y et un che min de y à z,
la mise bout à bout ou « conca té na tion » de ces deux che mins four nit un che min
de x à z ; de même avec un che min de y à x et un che min de z à y.
C’est donc une rela tion d’équi va lence. Les classes de cette rela tion d’équi va lence
se nomment les compo santes for te ment connexes du graphe
1
.
Un graphe est for te ment connexe s’il comporte une seule compo sante for te ment
connexe. Si l’on ajoute l’arc (d, a) au graphe de la Figure 3.6 (ou 3.7), il devient
fortement connexe.
Consi dé rons, à titre d’exemple, le graphe de la figure 3.8 pour lequel k X k 5 n 5 7.
Si l’on observe la matrice M 5 (I 1
# M)
364
, on constate qu’un nou vel arran ge ment
des colonnes et des lignes per met de faire appa raître des matrices car rées, uni que -
ment for mées de 1, s’appuyant sur la dia go nale prin ci pale.
1. Dans toute compo sante for te ment connexe c, il existe donc un che min entre tout couple de
som mets de c.
ˆ
ˆ
ˆ