Solu tions des exer cices du cha pitre 4
463
© Dunod – Toute reproduction non autorisée est un délit.
x 9 : l (x 1 ) 5 0, l (x 2 ) 5 3, l (x 3 ) 5 13, l (x 4 ) 5 15, l (x 5 ) 5 11, l (x 6 ) 5 20,
l (x 7 ) 5 19, l (x 8 ) 5 22, l (x 9 ) 5 29, l (x 10 ) 5 34
x 1
x 4
x 7
x 9
x 10
x 8
x 5
x 6
x 2
x 3
19
29
34
22
11
3
0
15
13
2
9
4
7
8
2
3
2
20
Ci-dessus : l’arborescence des chemins de valeur maximale de x 1 vers les autres sommets.
NB : Nous avons détaillé à l’extrême les calculs ; en pratique il vaut mieux les présenter en
tableau.
4.6 1) Le pro blème du livreur consiste à trou ver un plus court che min de A à H. Cha cune
des arêtes du graphe d’ori gine est dédou blée en deux arcs d’orien ta tions oppo sées qui sont
valués par les durées de tra jets entre les car re fours cor res pon dants (sauf pour les arcs issus
de A et ceux aboutissant en H). Le graphe obtenu est donc orienté et avec des valuations
posi tives.
2) Appli quons l’algo rithme :
Ini tia le ment, l A 5 0 , l B 5 l C 5 l D 5 l E 5 l F 5 l G 5 l H 5 1`
puis exa mi nons tour à tour les som mets (l X est une valeur pro vi soire ; l x , défi ni tive) :
l A 5 0 , l B 5 2 , l C 5 1` , l D 5 5 , l E 5 7 , l F 5 l G 5 l H 5 1`
l A 5 0 , l B 5 2 , l C 5 11 , l D 5 5 , l E 5 6 , l F 5 l G 5 l H 5 1`
l A 5 0 , l B 5 2 , l C 5 11 , l D 5 5 , l E 5 6 , l F 5 9 , l G 5 l H 5 1`
l A 5 0 , l B 5 2 , l C 5 10 , l D 5 5 , l E 5 6 , l F 5 9 , l G 5 10, l H 5 1`
l A 5 0 , l B 5 2 , l C 5 10 , l D 5 5 , l E 5 6 , l F 5 9 , l G 5 10, l H 5 14
l A 5 0 , l B 5 2 , l C 5 10 , l D 5 5 , l E 5 6 , l F 5 9 , l G 5 10, l H 5 14
l A 5 0 , l B 5 2 , l C 5 10 , l D 5 5 , l E 5 6 , l F 5 9 , l G 5 10, l H 5 14
l A 5 0 , l B 5 2 , l C 5 10 , l D 5 5 , l E 5 6 , l F 5 9 , l G 5 10, l H 5 14
Ainsi en pre nant le tra jet A, B, E, F, H la livrai son sera faite en 14 mn.