Solutions
462
4.4 Appli quons l’algo rithme de Ford :
Ini tia le ment, l A 5 0 , l B 5 l C 5 l D 5 l E 5 l F 5 1`
puis exa mi nons tour à tour les arcs per met tant de faire décroître les l i :
1 A , D2 : l A 5 0 , l D 5 6 , l B 5 l C 5 l E 5 l F 5 1`
1 A , B 2 : l A 5 0 , l B 5 3 , l C 5 1` , l D 5 6 , l E 5 l F 5 1`
1 B, E2 : l A 5 0 , l B 5 3 , l C 5 1` , l D 5 6 , l E 5 9 , l F 5 1`
1 D, F2 : l A 5 0 , l B 5 3 , l C 5 1` , l D 5 6 , l E 5 9 , l F 5 13
1 A , C2 : l A 5 0 , l B 5 3 , l C 5 8 , l D 5 6 , l E 5 9 , l F 5 13
( B, D) : l A 5 0 , l B 5 3 , l C 5 8 , l D 5 1 , l E 5 9 , l F 5 13
( D, F) : l A 5 0 , l B 5 3 , l C 5 8 , l D 5 1 , l E 5 9 , l F 5 8
1 D, C2 : l A 5 0 , l B 5 3 , l C 5 3 , l D 5 1 , l E 5 9 , l F 5 8
( C, E) : l A 5 0 , l B 5 3 , l C 5 3 , l D 5 1 , l E 5 4 , l F 5 8
( D, F) : l A 5 0 , l B 5 3 , l C 5 3 , l D 5 1 , l E 5 4 , l F 5 6
Aucun arc ne per met plus de faire décroître les l,
(A, B, D, C, E, F) est alors un che min mini mal de A à F, son coût est l F 5 6 . C’est aussi
un chemin hamiltonien.
4.5 1) Nous allons véri fier qu’il existe N, une numé ro ta tion topologique des som mets de G :
N(x 1 ) = 1, N(x 2 ) = 2, N(x 5 ) = 3, N(x 3 ) = 4, N(x 6 ) = 5, N(x 8 ) = 6, N(x 4 ) = 7, N(x 7 ) = 8, N(x 9 ) = 9,
N(x 10 ) = 10, est bien une telle numé ro ta tion (le numéro de l’ori gine de tout arc est infé rieur au
numéro de son extré mité). G est donc sans cir cuit. (Cf la fin du paragraphe 3. 2 du cours).
2) Ini tia le ment, l (x 1 ) 5 0 , l (x 2 ) 5 c 5 l(x 10 ) 5 2`.
Exa mi nons tout à tour les som mets sui vant l’ordre topologique :
x 1 : l (x 1 ) 5 0, l (x 2 ) 5 3, l (x 3 ) 5 5, l (x 4 ) 5 4, l (x 5 ) 5 c 5 l (x 10 ) 5 2`
x 2 : l 1 x 1 2 5 0, l 1 x 2 2 5 3, l 1 x 3 2 5 6, l 1 x 4 2 5 4, l 1 x 5 2 5 11,
l 1 x 6 2 5 c 5 l 1 x 10 2 5 2`
x 5 : l (x 1 ) 5 0, l (x 2 ) 5 3, l (x 3 ) 5 13, l (x 4 ) 5 4, l (x 5 ) 5 11, l (x 6 ) 5 l (x 7 ) 5 2`
l (x 8 ) 5 16, l (x 9 ) 5 l (x 10 ) 5 2`
x 3 : 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 16, l (x 8 ) 5 16, l (x 9 ) 5 l (x 10 ) 5 2`
x 6 : 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 16, l (x 8 ) 5 22, l (x 9 ) 5 29, l (x 10 ) 5 2`
x 8 : 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 16, l (x 8 ) 5 22, l (x 9 ) 5 29, l (x 10 ) 5 23
x 4 : 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 23
x 7 : 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 23
462
4.4 Appli quons l’algo rithme de Ford :
Ini tia le ment, l A 5 0 , l B 5 l C 5 l D 5 l E 5 l F 5 1`
puis exa mi nons tour à tour les arcs per met tant de faire décroître les l i :
1 A , D2 : l A 5 0 , l D 5 6 , l B 5 l C 5 l E 5 l F 5 1`
1 A , B 2 : l A 5 0 , l B 5 3 , l C 5 1` , l D 5 6 , l E 5 l F 5 1`
1 B, E2 : l A 5 0 , l B 5 3 , l C 5 1` , l D 5 6 , l E 5 9 , l F 5 1`
1 D, F2 : l A 5 0 , l B 5 3 , l C 5 1` , l D 5 6 , l E 5 9 , l F 5 13
1 A , C2 : l A 5 0 , l B 5 3 , l C 5 8 , l D 5 6 , l E 5 9 , l F 5 13
( B, D) : l A 5 0 , l B 5 3 , l C 5 8 , l D 5 1 , l E 5 9 , l F 5 13
( D, F) : l A 5 0 , l B 5 3 , l C 5 8 , l D 5 1 , l E 5 9 , l F 5 8
1 D, C2 : l A 5 0 , l B 5 3 , l C 5 3 , l D 5 1 , l E 5 9 , l F 5 8
( C, E) : l A 5 0 , l B 5 3 , l C 5 3 , l D 5 1 , l E 5 4 , l F 5 8
( D, F) : l A 5 0 , l B 5 3 , l C 5 3 , l D 5 1 , l E 5 4 , l F 5 6
Aucun arc ne per met plus de faire décroître les l,
(A, B, D, C, E, F) est alors un che min mini mal de A à F, son coût est l F 5 6 . C’est aussi
un chemin hamiltonien.
4.5 1) Nous allons véri fier qu’il existe N, une numé ro ta tion topologique des som mets de G :
N(x 1 ) = 1, N(x 2 ) = 2, N(x 5 ) = 3, N(x 3 ) = 4, N(x 6 ) = 5, N(x 8 ) = 6, N(x 4 ) = 7, N(x 7 ) = 8, N(x 9 ) = 9,
N(x 10 ) = 10, est bien une telle numé ro ta tion (le numéro de l’ori gine de tout arc est infé rieur au
numéro de son extré mité). G est donc sans cir cuit. (Cf la fin du paragraphe 3. 2 du cours).
2) Ini tia le ment, l (x 1 ) 5 0 , l (x 2 ) 5 c 5 l(x 10 ) 5 2`.
Exa mi nons tout à tour les som mets sui vant l’ordre topologique :
x 1 : l (x 1 ) 5 0, l (x 2 ) 5 3, l (x 3 ) 5 5, l (x 4 ) 5 4, l (x 5 ) 5 c 5 l (x 10 ) 5 2`
x 2 : l 1 x 1 2 5 0, l 1 x 2 2 5 3, l 1 x 3 2 5 6, l 1 x 4 2 5 4, l 1 x 5 2 5 11,
l 1 x 6 2 5 c 5 l 1 x 10 2 5 2`
x 5 : l (x 1 ) 5 0, l (x 2 ) 5 3, l (x 3 ) 5 13, l (x 4 ) 5 4, l (x 5 ) 5 11, l (x 6 ) 5 l (x 7 ) 5 2`
l (x 8 ) 5 16, l (x 9 ) 5 l (x 10 ) 5 2`
x 3 : 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 16, l (x 8 ) 5 16, l (x 9 ) 5 l (x 10 ) 5 2`
x 6 : 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 16, l (x 8 ) 5 22, l (x 9 ) 5 29, l (x 10 ) 5 2`
x 8 : 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 16, l (x 8 ) 5 22, l (x 9 ) 5 29, l (x 10 ) 5 23
x 4 : 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 23
x 7 : 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 23