Chapitre 3 • Éléments de la théorie des graphes
62
Une chaîne qui se ferme sur elle- même (et qui est simple) est un cycle.
Un graphe est connexe s’il existe au moins une chaîne entre toute paire de som -
mets ; s’il n’est pas connexe, les sous-ensembles maximaux (au sens de l’inclu sion)
de som mets tels qu’entre deux som mets quel conques d’un même sous- ensemble
existe une chaîne, sont nom més « compo santes connexes » du graphe. Ce concept ne
fait donc pas appel à l’orientation du graphe.
N.B. Nous définirons plus loin la forte connexité qui, elle, concerne les graphes
orientés.
Le graphe ci- dessus est connexe ; la sup pres sion des arêtes [A, B], [A, C], [D, A],
[D, E] et [E, C] le ren drait non connexe, le graphe res tant compor te rait p 5 2 compo -
santes connexes : {A, E} et {B, C, D}.
Le degré d’un som met x est le nombre d’arêtes ayant une extré mité en x :
d A 5 4, d B 5 2 (la boucle est exclue), d C 5 4, etc.
Un arbre est un graphe connexe et sans cycle (cette notion ne fait donc pas
appel à l’orien ta tion du graphe) ; dans la figure 3.3 si l’on sup prime les arcs (A, B),
(B, B), (D, A), (E, A) et (C, E), le graphe res tant est un arbre (illustré par les arêtes
grasses de la fig. 3.3). Un arbre de n som mets comporte n 2 1 arêtes (arcs). Insis -
tons sur le fait qu’un arbre n’est pas orienté a priori.
Une arbo res cence, dans un graphe orienté, est un arbre compor tant un som met par -
ti cu lier r, nommé racine de l’arbo res cence ; depuis r, il existe dans l’arbo res cence un
che min (et un seul) vers tout autre som met (cette notion fait donc bien appel à l’orien -
ta tion du graphe) ; en sup pri mant tous les arcs de la fig. 3.3 sauf les n 2 1 5 4 arcs
sui vants : (B, C), (C, D), (D, A) et (D, E), on obtient une arbo res cence de racine B.
N.B. Cer tains infor ma ti ciens nomment “arbre” ce qui – en théo rie des graphes –
est une arbo res cence.
Tout graphe peut être défini par sa matrice
d’adja cence M qui est boo léenne. L’exis tence
d’un arc de X vers Y se tra duit par la pré sence
d’un 1 à l’inter sec tion de la ligne X et de la
colonne Y de la matrice M ; l’absence d’arc,
par la pré sence d’un 0. La matrice d’adja cence
rela tive au graphe de la figure 3.3 est don née
ci-contre. En excluant les boucles : la somme
des termes de la ligne X est : d
+ x , de la colonne
Y : d
– y .
À une matrice asso ciée symé trique (voir le chap. 1 sur les rela tions) cor res -
pond un graphe symé trique : si (x, y)PU alors (y, x)PU une matrice asso ciée
anti sy mé trique, un graphe anti sy mé trique : si (x, y)PU alors (y, x) x U.
Un graphe est complet si, pour tout arc (x, y), on a :
[(x, y) x U] entraîne [(y, x)PU]
Figure 3.4 Matrice boo léenne asso ciée
62
Une chaîne qui se ferme sur elle- même (et qui est simple) est un cycle.
Un graphe est connexe s’il existe au moins une chaîne entre toute paire de som -
mets ; s’il n’est pas connexe, les sous-ensembles maximaux (au sens de l’inclu sion)
de som mets tels qu’entre deux som mets quel conques d’un même sous- ensemble
existe une chaîne, sont nom més « compo santes connexes » du graphe. Ce concept ne
fait donc pas appel à l’orientation du graphe.
N.B. Nous définirons plus loin la forte connexité qui, elle, concerne les graphes
orientés.
Le graphe ci- dessus est connexe ; la sup pres sion des arêtes [A, B], [A, C], [D, A],
[D, E] et [E, C] le ren drait non connexe, le graphe res tant compor te rait p 5 2 compo -
santes connexes : {A, E} et {B, C, D}.
Le degré d’un som met x est le nombre d’arêtes ayant une extré mité en x :
d A 5 4, d B 5 2 (la boucle est exclue), d C 5 4, etc.
Un arbre est un graphe connexe et sans cycle (cette notion ne fait donc pas
appel à l’orien ta tion du graphe) ; dans la figure 3.3 si l’on sup prime les arcs (A, B),
(B, B), (D, A), (E, A) et (C, E), le graphe res tant est un arbre (illustré par les arêtes
grasses de la fig. 3.3). Un arbre de n som mets comporte n 2 1 arêtes (arcs). Insis -
tons sur le fait qu’un arbre n’est pas orienté a priori.
Une arbo res cence, dans un graphe orienté, est un arbre compor tant un som met par -
ti cu lier r, nommé racine de l’arbo res cence ; depuis r, il existe dans l’arbo res cence un
che min (et un seul) vers tout autre som met (cette notion fait donc bien appel à l’orien -
ta tion du graphe) ; en sup pri mant tous les arcs de la fig. 3.3 sauf les n 2 1 5 4 arcs
sui vants : (B, C), (C, D), (D, A) et (D, E), on obtient une arbo res cence de racine B.
N.B. Cer tains infor ma ti ciens nomment “arbre” ce qui – en théo rie des graphes –
est une arbo res cence.
Tout graphe peut être défini par sa matrice
d’adja cence M qui est boo léenne. L’exis tence
d’un arc de X vers Y se tra duit par la pré sence
d’un 1 à l’inter sec tion de la ligne X et de la
colonne Y de la matrice M ; l’absence d’arc,
par la pré sence d’un 0. La matrice d’adja cence
rela tive au graphe de la figure 3.3 est don née
ci-contre. En excluant les boucles : la somme
des termes de la ligne X est : d
+ x , de la colonne
Y : d
– y .
À une matrice asso ciée symé trique (voir le chap. 1 sur les rela tions) cor res -
pond un graphe symé trique : si (x, y)PU alors (y, x)PU une matrice asso ciée
anti sy mé trique, un graphe anti sy mé trique : si (x, y)PU alors (y, x) x U.
Un graphe est complet si, pour tout arc (x, y), on a :
[(x, y) x U] entraîne [(y, x)PU]
Figure 3.4 Matrice boo léenne asso ciée