Chapitre 3 • Éléments de la théorie des graphes
60
Graphes et hyper graphes (1971), d’où un renou vel le ment, un essor des recherches,
notamment en France, en Hongrie, aux États- Unis, en Union Sovié tique (aujourd’hui
Russie) et au Japon.
La théo rie des graphes est deve nue l’un des ins tru ments les plus effi caces pour
repré sen ter (modé li ser), puis résoudre de nom breux pro blèmes dis crets que pose la
recherche opé ra tion nelle. Claude Berge a reconnu que la R.O. contri bue aux pro grès
de la théo rie des graphes, en sus ci tant de nou velles recherches (voir, par exemple,
l’avant- propos de Graphes et hyper graphes).
3.1.2 Voca bu laire de la théo rie des graphes ;
connexité, arbres
Consi dé rons les « points » A, B, C, D et E et un cer tain nombre de « flèches » joi
gnant entre eux plu sieurs couples de ces points (figure 3.2). Désor mais ces points
seront nom més som mets et ces flèches, arcs.
A
B
E
D
C
Figure 3.2
À chaque som met de l’ensemble X 5 5A, B, C, D, E6 cor res pond par l’appli ca -
tion G
1
(nom mée appli ca tion suc ces seurs), un sous- ensemble de X ; ainsi en sui vant
les arcs (flèches), on voit que :
G
1
1 A2 5 5B,C6 ; G
1
1 B2 5 5D, E6 ; G
1
1 C 2 5 5E6 ; G
1
1 D 2 5 5C6 ; G
1
(E) 5 0.
le som met E, qui n’a pas de suc ces seur, est appelé sor tie du graphe (un graphe peut
compor ter zéro, une ou plu sieurs sor ties).
Si l’on remonte main te nant les arcs, on obtient l’appli ca tion réci proque,
nom mée appli ca tion pré dé ces seurs et notée G
2
: G
2
(A) 5 0 ; G
2
1 B 2 5 5A6 ;
G
2
1 C 2 5 5A, D6 ; G
2
1 D 2 5 5B6 ; G
2
1 E 2 5 5B, C6 ;
Le som met A, qui n’a pas de pré dé ces seur, est appelé entrée du graphe.
Le sommet E, qui n’a pas de successeur, est appelé sortie du graphe.
Ainsi un graphe est défini lorsque l’on connaît l’ensemble X de ses som mets et
l’appli ca tion suc ces seur G
1
, d’où l’écri ture G 5 1 X, G
1
2 . Ou bien si l’on connaît X
et G
2
; on note alors : G 5 1 X, G
2
2 .
Tout arc u peut être dési gné par le couple formé par son som met, extré mité
ini tiale, puis son extré mité extrémale. Par exemple l’arc reliant A à B est noté :
60
Graphes et hyper graphes (1971), d’où un renou vel le ment, un essor des recherches,
notamment en France, en Hongrie, aux États- Unis, en Union Sovié tique (aujourd’hui
Russie) et au Japon.
La théo rie des graphes est deve nue l’un des ins tru ments les plus effi caces pour
repré sen ter (modé li ser), puis résoudre de nom breux pro blèmes dis crets que pose la
recherche opé ra tion nelle. Claude Berge a reconnu que la R.O. contri bue aux pro grès
de la théo rie des graphes, en sus ci tant de nou velles recherches (voir, par exemple,
l’avant- propos de Graphes et hyper graphes).
3.1.2 Voca bu laire de la théo rie des graphes ;
connexité, arbres
Consi dé rons les « points » A, B, C, D et E et un cer tain nombre de « flèches » joi
gnant entre eux plu sieurs couples de ces points (figure 3.2). Désor mais ces points
seront nom més som mets et ces flèches, arcs.
A
B
E
D
C
Figure 3.2
À chaque som met de l’ensemble X 5 5A, B, C, D, E6 cor res pond par l’appli ca -
tion G
1
(nom mée appli ca tion suc ces seurs), un sous- ensemble de X ; ainsi en sui vant
les arcs (flèches), on voit que :
G
1
1 A2 5 5B,C6 ; G
1
1 B2 5 5D, E6 ; G
1
1 C 2 5 5E6 ; G
1
1 D 2 5 5C6 ; G
1
(E) 5 0.
le som met E, qui n’a pas de suc ces seur, est appelé sor tie du graphe (un graphe peut
compor ter zéro, une ou plu sieurs sor ties).
Si l’on remonte main te nant les arcs, on obtient l’appli ca tion réci proque,
nom mée appli ca tion pré dé ces seurs et notée G
2
: G
2
(A) 5 0 ; G
2
1 B 2 5 5A6 ;
G
2
1 C 2 5 5A, D6 ; G
2
1 D 2 5 5B6 ; G
2
1 E 2 5 5B, C6 ;
Le som met A, qui n’a pas de pré dé ces seur, est appelé entrée du graphe.
Le sommet E, qui n’a pas de successeur, est appelé sortie du graphe.
Ainsi un graphe est défini lorsque l’on connaît l’ensemble X de ses som mets et
l’appli ca tion suc ces seur G
1
, d’où l’écri ture G 5 1 X, G
1
2 . Ou bien si l’on connaît X
et G
2
; on note alors : G 5 1 X, G
2
2 .
Tout arc u peut être dési gné par le couple formé par son som met, extré mité
ini tiale, puis son extré mité extrémale. Par exemple l’arc reliant A à B est noté :