Arbres et arborescences
169
0
=
0
=
2
=
DE
DB
CB
On sélectionne donc l'arc
pour partitionner en
et
(cf. l'arborescence complète
page suivante). Pour
( ,
,
), la matrice correspondante est :
qui donne toujours une évaluation par défaut égale à 52.
Sur la matrice 9, le regret maximal est
d'où H7 et H8. H7 d'évaluation infinie
est vide; quant à H8 il correspond à la nouvelle matrice :
Regret maximal
d'où
(vide) et
où il n'y a plus qu'un circuit possible :
,
,
,
, de valeur 54, et qui est donc terminal non vide.
Mais, du coup, le sommet pendant
a une évaluation par défaut inférieure à celle du
sommet terminal non vide. On doit donc reprendre les calculs en
.
Les regrets calculés sur la matrice 5 donnent :
3
=
2
=
0
=
2
=
DA
CB
BD
BC
0
=
0
=
0
=
ED
EB
DB
D'où sélection de
pour séparer
avec la matrice 11 pour
.
B
C
E
B +
0
0
C 0
+
+
D 0
2
0
Matrice 9
C
E
B 0
0
D 2
0
Matrice 10