3.1 Élé ments de la théo rie des graphes
69
© Dunod – Toute reproduction non autorisée est un délit.
1
2
Figure 3.8
A B C D E F G
A B F C D E G
A
B
C
M D
E
F
G
A
B
F
C
D
E
G
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
0 0 0 1 1 1 1
0 0 0 1 1 1 1
0 0 0 1 1 1 1
0 0 0 1 1 1 1
1 1 1 1 1 1 1
0 0 1 1 1 0 1
0 0 1 1 1 0 1
0 0 1 1 1 0 1
1 1 1 1 1 1 1
0 0 1 1 1 0 1
ˆ
À cha cune de ces matrices car rées cor res pond une compo sante for te ment connexe
du graphe. c 1 5 5A, B, F6 et c 2 5 5C, D, E, G6 sont les ensembles de som mets des
deux compo santes for te ment connexes du graphe de la figure 3.8.
Remarques. 1) Lorsqu’un graphe comporte un cir cuit hamiltonien, il est
for te ment connexe et la matrice 1 I 1
# M2
3n214
ne contient que des 1. Mais le
fait que la matrice 1 I 1
# M2
3n214
soit uni que ment for mée de 1 n’implique pas
l’exis tence d’un cir cuit hamiltonien : cela veut sim ple ment dire que le graphe
est for te ment connexe. Par exemple G 5 1 X, U2 où :
X 5 ({A, B, C, D} ; U 5 {(A, B) ; (B, C) ; (C, A) ; (C, D) ; (D, B)}
2) Tous les som mets appar te nant à un même cir cuit, appar tiennent néces sai re -
ment à la même compo sante for te ment connexe.
Un algo rithme très effi cace, dû à Tarjan, per met de déter mi ner les compo santes for
te ment connexes d’un graphe. Cet algo rithme effec tue un seul par cours en pro fon deur
du graphe (cf. 3.2.d) et est de complexité O(m), où m est le nombre d’arcs (sup posé ici
supé rieur ou égal à n). Le lec teur pourra consul ter la réfé rence [8] pour la des crip tion et la
preuve de cet algo rithme. Nous conseillons au lecteur l’exercice corrigé en fin de ce chapitre donnant l’algorithme plus simple mais efficace, dû à Kosaraju et Sharis, également
en O(m), aboutissant au même résultat, mais en effectuant deux parcours en profondeur.
3.1.5 Uti lité du concept de graphe en recherche
opé ra tion nelle
Un graphe peut repré sen ter toutes sortes de situa tions dans les phé no mènes d’orga -
ni sa tion. Par exemple, un réseau de transport, c’est- à-dire un graphe compor tant une
entrée et une sor tie, peut cor res pondre à des cana li sa tions où cir cule un fluide (liquide,
gaz). Dans ce cas, il véri fie la loi des nœuds ou loi de Kirchhoff, bien connue en élec
tri cité, et selon laquelle les quan ti tés entrantes (par unité de temps) en un som met sont
égales aux quan ti tés sor tantes (par unité de temps) en ce même som met (figure 3.9). Il
est facile, en effet, de comprendre que, si trois cana li sa tions apportent en un som met
A des débits res pec tifs de 2, 3 et 1 litres/mn, soit en tout 6 O/mn, les cana li sa tions qui
partent de A doivent avoir un débit total de 6 O/mn.
69
© Dunod – Toute reproduction non autorisée est un délit.
1
2
Figure 3.8
A B C D E F G
A B F C D E G
A
B
C
M D
E
F
G
A
B
F
C
D
E
G
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
0 0 0 1 1 1 1
0 0 0 1 1 1 1
0 0 0 1 1 1 1
0 0 0 1 1 1 1
1 1 1 1 1 1 1
0 0 1 1 1 0 1
0 0 1 1 1 0 1
0 0 1 1 1 0 1
1 1 1 1 1 1 1
0 0 1 1 1 0 1
ˆ
À cha cune de ces matrices car rées cor res pond une compo sante for te ment connexe
du graphe. c 1 5 5A, B, F6 et c 2 5 5C, D, E, G6 sont les ensembles de som mets des
deux compo santes for te ment connexes du graphe de la figure 3.8.
Remarques. 1) Lorsqu’un graphe comporte un cir cuit hamiltonien, il est
for te ment connexe et la matrice 1 I 1
# M2
3n214
ne contient que des 1. Mais le
fait que la matrice 1 I 1
# M2
3n214
soit uni que ment for mée de 1 n’implique pas
l’exis tence d’un cir cuit hamiltonien : cela veut sim ple ment dire que le graphe
est for te ment connexe. Par exemple G 5 1 X, U2 où :
X 5 ({A, B, C, D} ; U 5 {(A, B) ; (B, C) ; (C, A) ; (C, D) ; (D, B)}
2) Tous les som mets appar te nant à un même cir cuit, appar tiennent néces sai re -
ment à la même compo sante for te ment connexe.
Un algo rithme très effi cace, dû à Tarjan, per met de déter mi ner les compo santes for
te ment connexes d’un graphe. Cet algo rithme effec tue un seul par cours en pro fon deur
du graphe (cf. 3.2.d) et est de complexité O(m), où m est le nombre d’arcs (sup posé ici
supé rieur ou égal à n). Le lec teur pourra consul ter la réfé rence [8] pour la des crip tion et la
preuve de cet algo rithme. Nous conseillons au lecteur l’exercice corrigé en fin de ce chapitre donnant l’algorithme plus simple mais efficace, dû à Kosaraju et Sharis, également
en O(m), aboutissant au même résultat, mais en effectuant deux parcours en profondeur.
3.1.5 Uti lité du concept de graphe en recherche
opé ra tion nelle
Un graphe peut repré sen ter toutes sortes de situa tions dans les phé no mènes d’orga -
ni sa tion. Par exemple, un réseau de transport, c’est- à-dire un graphe compor tant une
entrée et une sor tie, peut cor res pondre à des cana li sa tions où cir cule un fluide (liquide,
gaz). Dans ce cas, il véri fie la loi des nœuds ou loi de Kirchhoff, bien connue en élec
tri cité, et selon laquelle les quan ti tés entrantes (par unité de temps) en un som met sont
égales aux quan ti tés sor tantes (par unité de temps) en ce même som met (figure 3.9). Il
est facile, en effet, de comprendre que, si trois cana li sa tions apportent en un som met
A des débits res pec tifs de 2, 3 et 1 litres/mn, soit en tout 6 O/mn, les cana li sa tions qui
partent de A doivent avoir un débit total de 6 O/mn.