4.10 Recherches arbo res centes
167
© Dunod – Toute reproduction non autorisée est un délit.
On obtient la matrice 7 bis et la borne du
som met (A, E) : 20 1 3 5 23.
Choi sir le som met pen dant de la borne la
plus petite : c’est NON (A, E), de type I, qui
a pour borne 22.
2. Il faut évi dem ment reprendre la matrice
5 (matrice des coûts rela tive au som met de
l’arbo res cence pré cé dant celui que l’on vient
d’adop ter) pour exé cu ter le bloc G, d’où la
matrice 8. Reve nir à C.
Matrice 9. Éva lua tion des regrets des zéros
de la matrice 8. Le plus petit vaut 2, la borne
de NON (D, F) devient 22 1 2 5 24.
Matrice 10. Obtenue par sup pres sion de la
ligne D et de la colonne F de la matrice 8,
puis inter dic tion de (F, B) : elle comporte au
moins un zéro dans toute rangée :
Borne de 1 D, F2 5 22 1 0 5 22.
Cal cul du min{24, 24, 23, 22} 5 22 pour trouver
le sommet pendant de plus petite borne.
Repar tir de (D, F), qui est de type II.
3. La matrice 11 donne les regrets de la
matrice 10 ; le plus fort vaut 3 : (F, E).
Borne de NON 1 F, E 2 5 22 1 3 5 25.
Borne de 1 F, E 2 5 22 1 1 5 23 (pas sage de
la matrice 12 à la matrice 12 bis).
Cal cul du min{24, 24, 25, 23, 23} 5 23.
On décide de conti nuer à par tir de (F, E), de
borne 23. L’arc parasite est (E, B).
4. La matrice 13 des regrets de la matrice 12
bis désigne (A, B), de plus fort regret :
Borne de NON 1 A, B2 5 23 1 7 5 30.
Borne de 1 A, B2 5 23 1 0 (matrice 14).
Cal cul du min{24, 24, 25, 30, 23, 23} 5 23.
On décide de conti nuer à par tir de (A, B) de
borne 23. L'arc parasite est (E, B).
5. La matrice 15 laisse le choix entre (C, A)
et (E, C). Arbi trai re ment : choix de (C, A).
Borne de NON 1 F, E 2 5 23 1 ` 5 1`.
Borne de 1 C, A2 5 23 1 0 (matrice 16).
Matrice 7 bis.
Matrice 8.
0 2 0
4 2 4 0
4 2 0
0 0 0
A B C E F
A B C F
C
C
A
D
D
E
E
F
F
0 5 5
1 0 1
1 6 0 6
0 0 0 0
3 2 3 0
Matrice 9. (regrets)
A B C E F
A B C F
C
C
A
A
D
E
E
F
F
2
0
0
0
0
0
0
0
0
0
0
6
3
3
2
2
2
1
1
1
Matrice 12.
Matrice 12 bis : on a
soustrait à la ligne C
C
C
A
A
0
0
0 2
1
6
5
1
0
0
0
0
2
B
C
A B
E
C
A
E
Matrice 13.
(regrets)
Matrice 14.
C
C
A
A
A
0
7
5
0
0
2
B
C
E
Matrice 11. (regrets)
A B C E
C
A
E
F
3
2
2
0
1
1
Matrice 10.
l’arc (F, B)
fermerait un
circuit parasite
avec les arcs
déjà retenus :
(B, D) puis
(D, F )
167
© Dunod – Toute reproduction non autorisée est un délit.
On obtient la matrice 7 bis et la borne du
som met (A, E) : 20 1 3 5 23.
Choi sir le som met pen dant de la borne la
plus petite : c’est NON (A, E), de type I, qui
a pour borne 22.
2. Il faut évi dem ment reprendre la matrice
5 (matrice des coûts rela tive au som met de
l’arbo res cence pré cé dant celui que l’on vient
d’adop ter) pour exé cu ter le bloc G, d’où la
matrice 8. Reve nir à C.
Matrice 9. Éva lua tion des regrets des zéros
de la matrice 8. Le plus petit vaut 2, la borne
de NON (D, F) devient 22 1 2 5 24.
Matrice 10. Obtenue par sup pres sion de la
ligne D et de la colonne F de la matrice 8,
puis inter dic tion de (F, B) : elle comporte au
moins un zéro dans toute rangée :
Borne de 1 D, F2 5 22 1 0 5 22.
Cal cul du min{24, 24, 23, 22} 5 22 pour trouver
le sommet pendant de plus petite borne.
Repar tir de (D, F), qui est de type II.
3. La matrice 11 donne les regrets de la
matrice 10 ; le plus fort vaut 3 : (F, E).
Borne de NON 1 F, E 2 5 22 1 3 5 25.
Borne de 1 F, E 2 5 22 1 1 5 23 (pas sage de
la matrice 12 à la matrice 12 bis).
Cal cul du min{24, 24, 25, 23, 23} 5 23.
On décide de conti nuer à par tir de (F, E), de
borne 23. L’arc parasite est (E, B).
4. La matrice 13 des regrets de la matrice 12
bis désigne (A, B), de plus fort regret :
Borne de NON 1 A, B2 5 23 1 7 5 30.
Borne de 1 A, B2 5 23 1 0 (matrice 14).
Cal cul du min{24, 24, 25, 30, 23, 23} 5 23.
On décide de conti nuer à par tir de (A, B) de
borne 23. L'arc parasite est (E, B).
5. La matrice 15 laisse le choix entre (C, A)
et (E, C). Arbi trai re ment : choix de (C, A).
Borne de NON 1 F, E 2 5 23 1 ` 5 1`.
Borne de 1 C, A2 5 23 1 0 (matrice 16).
Matrice 7 bis.
Matrice 8.
0 2 0
4 2 4 0
4 2 0
0 0 0
A B C E F
A B C F
C
C
A
D
D
E
E
F
F
0 5 5
1 0 1
1 6 0 6
0 0 0 0
3 2 3 0
Matrice 9. (regrets)
A B C E F
A B C F
C
C
A
A
D
E
E
F
F
2
0
0
0
0
0
0
0
0
0
0
6
3
3
2
2
2
1
1
1
Matrice 12.
Matrice 12 bis : on a
soustrait à la ligne C
C
C
A
A
0
0
0 2
1
6
5
1
0
0
0
0
2
B
C
A B
E
C
A
E
Matrice 13.
(regrets)
Matrice 14.
C
C
A
A
A
0
7
5
0
0
2
B
C
E
Matrice 11. (regrets)
A B C E
C
A
E
F
3
2
2
0
1
1
Matrice 10.
l’arc (F, B)
fermerait un
circuit parasite
avec les arcs
déjà retenus :
(B, D) puis
(D, F )