"'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
GRAPHES
ET ORDONNANCEMENT
6.1 Représentations d'un graphe
6.2 Chemins d'un graphe
6.3 Niveau des sommets d'un graphe sans circuit
6.4 Méthode MPM d'ordonnancement d'un graphe
> Savoir mettre en œuvre des algorithmes de recherche de niveaux,
d'optimisation et de constructions de graphes ordonnés.
6.1 REPRÉSENTATIONS D'UN GRAPHE
Un site internet est composé de cinq pages notées A, B, C, D et E. En un clic, on
peut passer d'une page à certaines autres selon les possibilités suivantes :
• De la page A, on peut passer en un clic aux pages C et E.
• De la page B, on peut passer aux pages A et D.
• Depuis la page C, on peut accéder à la page Bou rester sur C.
Quand on est sur la page D, on peut seulement aller sur la page Cet de la page E,
on ne peut aller que sur la page A.
On peut modéliser cette situation avec un graphique sagittal (fig. 6.1), constitué
de l'ensemble S = {A ;B ;C;D;E } des sommets, et de flèches orientées appelées arcs.
A
B
E
D
Figure 6.1
147