Arbres et arborescences
165
Et on obtient alors une évaluation par défaut sur
égale à
.
3) Création d'une arborescence et choix du sommet à séparer.
Recommençons sur
l'opération que l'on vient de faire sur H. Nous reprenons la
matrice 3 en remplaçant le zéro de
par
puisque
est caractérisé par le fait que
l'arc
n'est pas emprunté.
Ce qui donne, par soustraction des éléments convenables, la matrice 7 (soustraction de 1
à la ligne A et de 3 à la colonne E).
A
B
C
D
B 3
+
0
0
C 5
0
+
2
D 0
0
2
+
E +
0
+
0
Matrice 5
48
52
H
H1
H2
AE
AE
52
A
B
C D E
A +
4
6
1
+
B 7
+
0
0
3
C 9
0
+
2
+
D 4
0
2
+
3
E 0
0
+
0
+
Matrice 6
- 1
- 3
165
Et on obtient alors une évaluation par défaut sur
égale à
.
3) Création d'une arborescence et choix du sommet à séparer.
Recommençons sur
l'opération que l'on vient de faire sur H. Nous reprenons la
matrice 3 en remplaçant le zéro de
par
puisque
est caractérisé par le fait que
l'arc
n'est pas emprunté.
Ce qui donne, par soustraction des éléments convenables, la matrice 7 (soustraction de 1
à la ligne A et de 3 à la colonne E).
A
B
C
D
B 3
+
0
0
C 5
0
+
2
D 0
0
2
+
E +
0
+
0
Matrice 5
48
52
H
H1
H2
AE
AE
52
A
B
C D E
A +
4
6
1
+
B 7
+
0
0
3
C 9
0
+
2
+
D 4
0
2
+
3
E 0
0
+
0
+
Matrice 6
- 1
- 3