"'O
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
Chapitre 6 • Graphes et ordonnancement
150
La première ligne montre que r + (A)= {C;O}. La troisième ligne montre que C n'a
pas de successeur. On peut ainsi reconstituer le graphe :
A
B
D
c
Figure 6.3
Le nombre de l sur une ligne est le nombre de successeurs du sommet correspondant à la ligne. Concernant les colonnes, le nombre de 1 est le nombre de prédécesseurs du sommet qui correspond à la colonne.
6.2 CHEMINS D'UN GRAPHE
Reprenons le graphe du paragraphe 6.1.
A
B
E
D
Figure 6.4
En suivant des arcs, on peut aller du sommet E au sommet B en passant par les
sommets A puis C.
La suite ordonnée (E,A, C,B) est un chemin constitué de trois arcs. Ce chemin est
de longueur 3. On peut remarquer que chaque arc de ce chemin peut être considéré
comme un chemin de longueur 1.
(A,B,D) n'est pas un chemin car il n'y a pas d'arc qui permet de passer de A à B.
(D, C,B,D) est un chemin dont le premier sommet est le même que le dernier
sommet : c'est un circuit.
(E,A,B,C,D) est un chemin qui passe par tous les sommets, une fois et une seule:
on dit que c'est un chemin hamiltonien.
6.2.1 Chemin et longueur
Dans un graphe orienté, un chemin est une suite ordonnée de sommets dans laquelle
chaque sommet, à part le premier, est un successeur du sommet qui le précède.