"'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
Exercices corrigés
lflJ1 Un graphe est défini par le tableau 6.17. Déterminer les prédécesseurs de
chaque sommet. Pourquoi peut-on affirmer que le graphe est une arborescence ?
Dessiner cette arborescence.
Tableau 6.1 7
Sommets
A
B
c D
E
F
G
H
I
J
K
L
Successeurs
B,L
D,K
--A,)
C,G, I
--F
--H
Mid Sept villes notées A, B, C, D, E, F et G constituent un réseau. Sur le graphe
valué suivant (fig. 6.25) figurent les liaisons et leurs durées en heures.
c
A- - - D
4
• B 4 • G
~7 7
E~ F
Figure 6.25
a) On va rechercher le chemin minimal pour aller de A à G. Pour cela, on va se servir
de la propriété « tout chemin optimal est composé de chemins eux-mêmes
optimaux». À chaque sommet, on va attribuer une marque en appliquant l'algorithme suivant :
• Les sommets de niveau 0 reçoivent la marque O.
• Les sommets de niveau 1 reçoivent une marque égale à la valeur minimale des
chemins venant du niveau O.
• Les sommets des autres niveaux reçoivent une marque égale à la valeur minimale
de tous les chemins provenant des niveaux précédents.
Appliquer cet algorithme sur le graphe et en déduire la durée minimale du trajet pour
aller de A à G.
b) On donne maintenant les distances entre les villes, en kilomètres : AC = 500,
AD = 200, AE = 210, BG = 250, CG = 200, DB = 250, EB = 180, EF = 200,
EG = 450, FG = 210. Appliquer l'algorithme sur le graphe et en déduire la
longueur minimale du trajet pour aller de A à G.
ldlf4 Sur le graphe de la fig. 6.26, déterminer le chemin de longueur minimale
reliant A à /, puis le chemin de longueur maximale reliant A à I.
171