"'O
0
c
:J
0
:<:;
li)
.,,
..--t
c::
:l
0
~
N
"
@
~
.......
0
J::
:;
O'l
"'
·;::::
c::
0
>c::
o.
c::
0
.9
u
ü
:l
.,,
2
o.
~
"
:;
0
11
.,,
0
c:
:l
0
QJ
6.1 • Représentations d'un graphe
A B c DE
A 0 0 1 0 1
B 1 0 0 1 0
c 0 1 1 0 0
D 0 0 1 0 0
E
1 0 0 0 0
Figure 6.2
6.1.1 Vocabulaire des graphes
Un graphe simple orienté est défini par un ensemble fini S = { a 1 ;a 2 ; .. . ;a 11
} dont les
éléments sont appelés sommets, et par un ensemble G de couples appartenant au
produit cartésien S
2 dont les éléments sont appelés arcs.
Un couple (ai ;a) appartient à G si et seulement si, sur le diagramme sagittal, on
peut relier le sommet ai au sommet aj par une flèche orientée.
Le sommet ai de l'arc est appelé origine et le sommet aj est appelé extrémité. Si
l'origine et l'extrémité sont confondues, l'arc est une boucle.
Soit (ai;a) un arc d'un graphe G :
• Le sommet aj est un successeur de ai et ai est un prédécesseur de a/
• L' ensemble des successeurs d ' un sommet ai se note r + (aJ
• L' ensemble des prédécesseurs d'un sommet aj se note r- (a).
Exemple
Reprenons l'exemple étudié en début de chapitre :
- Les successeurs de A sont Cet E donc r + (A)= {C;E}. De même, r + (8) = {A;O}.
- Les prédécesseurs de A sont B et E donc r- (A)= {8;E}. De même, r- (8) = {Q.
6.1.2 Matrice d'adjacence d'un graphe
Soit G un graphe orienté ayant n sommets a 1 , a 2 , ... , aw La matrice d'adjacence du
graphe est la matrice carrée M = (mi) d' ordre n telle que : mi,j = 1 si et seulement si
(ai; a) est un arc de G, et mi,j = 0 sinon.
Exemple
Soit M =
0 0 1 1
1 0 0 1
0 0 0 0
0 0 1 0
la matrice d'adjacence d'un graphe définie sur S = {A;8;C;O}.
149