3.1 Élé ments de la théo rie des graphes
61
© Dunod – Toute reproduction non autorisée est un délit.
(A, B). Soit U l’ensemble de tous les arcs du graphe ; le graphe peut aussi être
noté : G 5 1 X, U2 . Pour le graphe de la figure 3.2, on a :
U 5 5 1 A, B2 , 1 A, C 2 , 1 B, D 2 , 1 B, E 2 , 1 C, E 2 , 1 D, C 2 6
U étant un ensemble de couples, U est donc une rela tion binaire sur l’ensemble X des som mets (rap pel : une rela tion binaire sur un ensemble X est un
sous- ensemble du pro duit car té sien X 3 X : U ( X 3 X ; le pro duit car té sien
X 3 X est, par défi ni tion, l’ensemble de tous les couples (x, y) où x et y appar -
tiennent à X ).
Dans cer taines appli ca tions, on n’a pas besoin de noter (ou de conser ver) l’orien -
ta tion ini tiale des arcs : à tout graphe orienté cor res pond un graphe non orienté. Ses
arcs « déso rien tés » sont nom més arêtes ; ainsi l’arc (A, B), sans son orien ta tion,
donne l’arête [A, B] (qui peut être notée tout aussi bien : [B, A]). Mais si un graphe G
comporte à la fois l’arc (x, y) et l’arc (y, x), le graphe non orienté asso cié comporte
une seule arête : [x, y] (qu’on peut noter aussi : [y, x]).
Dans un graphe, on appelle che min une séquence d’arcs dont l’extré mité ter mi -
nale de cha cun, sauf pour le der nier, est l’extré mité ini tiale du sui vant.
Un che min qui se ferme sur lui- même est un cir cuit.
On exige, le plus sou vent, qu’un che min soit simple : un che min est simple s’il
ne passe qu’une fois par cha cun de ses arcs ; il est élé men taire s’il ne passe pas plus
d’une fois cha cun de ses som mets. (NB : un che min élé men taire est néces sai re ment
simple, mais la réciproque est fausse).
La lon gueur d’un che min est le nombre de ses arcs. Un cir cuit de lon gueur 1 est
une boucle.
La figure 3.3 repré sente un graphe dans lequel : (D, A, E, A, E, A) est un che min,
(A, C, D, A) un cir cuit ; en B existe une boucle. (D, A, E, A, E, A) n’est pas simple,
(D, A, E, A) est simple, mais pas élé men taire ; (D, A, E) est élé men taire.
Le “demi- degré exté rieur” du som met x est : d
1
x 5 card G
1
1 x2 : c’est le nombre
d’arcs ayant leur extré mité ini tiale en x (en excluant les boucles) ; le “demi- degré
inté rieur” du som met x est : d
2
x 5 card G
2
1 x2 : c’est le nombre d’arcs ayant leur
extré mité ter mi nale en x (boucles exclues).
Consi dé rons main te nant le graphe de
la figure 3.3 comme non orienté. C’est
le graphe G 5 1 X, V 2 , où V est l’ensemble des arêtes. On appelle chaîne une suite
d’arêtes, dont cha cune a une extré mité
commune avec l’arête pré cé dente (sauf la
pre mière) et l’autre commune avec l’arête
sui vante (sauf la der nière). Ainsi
[A, D, E, C] est une chaîne.
Figure 3.3
61
© Dunod – Toute reproduction non autorisée est un délit.
(A, B). Soit U l’ensemble de tous les arcs du graphe ; le graphe peut aussi être
noté : G 5 1 X, U2 . Pour le graphe de la figure 3.2, on a :
U 5 5 1 A, B2 , 1 A, C 2 , 1 B, D 2 , 1 B, E 2 , 1 C, E 2 , 1 D, C 2 6
U étant un ensemble de couples, U est donc une rela tion binaire sur l’ensemble X des som mets (rap pel : une rela tion binaire sur un ensemble X est un
sous- ensemble du pro duit car té sien X 3 X : U ( X 3 X ; le pro duit car té sien
X 3 X est, par défi ni tion, l’ensemble de tous les couples (x, y) où x et y appar -
tiennent à X ).
Dans cer taines appli ca tions, on n’a pas besoin de noter (ou de conser ver) l’orien -
ta tion ini tiale des arcs : à tout graphe orienté cor res pond un graphe non orienté. Ses
arcs « déso rien tés » sont nom més arêtes ; ainsi l’arc (A, B), sans son orien ta tion,
donne l’arête [A, B] (qui peut être notée tout aussi bien : [B, A]). Mais si un graphe G
comporte à la fois l’arc (x, y) et l’arc (y, x), le graphe non orienté asso cié comporte
une seule arête : [x, y] (qu’on peut noter aussi : [y, x]).
Dans un graphe, on appelle che min une séquence d’arcs dont l’extré mité ter mi -
nale de cha cun, sauf pour le der nier, est l’extré mité ini tiale du sui vant.
Un che min qui se ferme sur lui- même est un cir cuit.
On exige, le plus sou vent, qu’un che min soit simple : un che min est simple s’il
ne passe qu’une fois par cha cun de ses arcs ; il est élé men taire s’il ne passe pas plus
d’une fois cha cun de ses som mets. (NB : un che min élé men taire est néces sai re ment
simple, mais la réciproque est fausse).
La lon gueur d’un che min est le nombre de ses arcs. Un cir cuit de lon gueur 1 est
une boucle.
La figure 3.3 repré sente un graphe dans lequel : (D, A, E, A, E, A) est un che min,
(A, C, D, A) un cir cuit ; en B existe une boucle. (D, A, E, A, E, A) n’est pas simple,
(D, A, E, A) est simple, mais pas élé men taire ; (D, A, E) est élé men taire.
Le “demi- degré exté rieur” du som met x est : d
1
x 5 card G
1
1 x2 : c’est le nombre
d’arcs ayant leur extré mité ini tiale en x (en excluant les boucles) ; le “demi- degré
inté rieur” du som met x est : d
2
x 5 card G
2
1 x2 : c’est le nombre d’arcs ayant leur
extré mité ter mi nale en x (boucles exclues).
Consi dé rons main te nant le graphe de
la figure 3.3 comme non orienté. C’est
le graphe G 5 1 X, V 2 , où V est l’ensemble des arêtes. On appelle chaîne une suite
d’arêtes, dont cha cune a une extré mité
commune avec l’arête pré cé dente (sauf la
pre mière) et l’autre commune avec l’arête
sui vante (sauf la der nière). Ainsi
[A, D, E, C] est une chaîne.
Figure 3.3