Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
110
1 2 3 4 5 6
1
2
D 0  D 1  3
4
5
6
  3 8 6    
      2 6  
        1  
    2     7
          2
           
1 2 3 4 5 6
1
2
D 2  3
4
5
6
  3 8 5 9  
      2 6  
        1  
    2     7
          2
           
En effet, D 0 5 D 1 , car aucun che min n’a X 0 comme som met inter mé diaire, X 0
étant une entrée.
D’autre part :
vr
112
14 5 v
112
12 1 v
112
24 5 5, et vr
112
15 5 v
112
12 1 v
112
25 5 9,
d’où :
v
122
14 5 min55, 66 5 5 ; v
122
15 5 min59, 1 ` 6 5 9.
1 2 3 4 5 6
1
2
D 4  3
4
5
6
  3 7 5 8 12
    4 2 5 9
        1  
    2   3 7
          2
           
1 2 3 4 5 6
1
2
D 3  3
4
5
6
  3 8 5 9  
      2 6  
        1  
    2   3 7
          2
           
1 2 3 4 5 6
1
2
D 5  3
4
5
6
  3 7 5 8 10
    4 2 5 7
        1 3
    2   3 5
          2
           
Les cal culs les plus longs ont lieu pour k 5 4 :
vr
132
13 5 v
132
14 1 v
132
43
5 7
vr
132
23 5 v
132
24 1 v
132
43
5 12
vr
132
15 5 v
132
14 1 v
132
45
5 8
vr
132
25 5 v
132
24 1 v
132
45
5 5
vr
132
16 5 v
132
14 1 v
132
46
5 9
vr
132
26 5 v
132
24 1 v
132
46
5 9
d’où :
v
142
13 5 min57, 86
5 7
v
142
23 5 min54, 1 ` 6 5 4
v
142
15 5 min58, 96
5 8
v
142
25 5 min55, 66
5 5
v
142
16 5 min512, 1 ` 6 5 12
v
142
26 5 min59, 1 ` 6 5 9