Arbres et arborescences
167
Cette matrice comporte déjà un zéro par ligne et par colonne et ne permet donc pas de
corriger l'évaluation par défaut qui reste .
On voit ainsi se dessiner une arborescence : chaque sommet de cette arborescence
représente un sous-ensemble de l'ensemble des circuits hamiltoniens du graphe
considéré.
Chaque sommet donne naissance à deux sommets représentant deux parties du sousensemble représenté par le sommet initial; chacune de ces parties est spécifiée par la
présence ou non de tel ou tel arc dans les circuits hamiltoniens qui les constituent.
Lorsque l'on passe d'un sommet à ses deux successeurs, on dit que l'on sépare le sousensemble correspondant au sommet.
Par ailleurs, on dispose en chaque sommet d'une quantité qui est inférieure à la valeur de
tous les circuits hamiltoniens appartenant au sous-ensemble correspondant à ce sommet :
on dit qu'on a une évaluation par défaut de la fonction.
Supposons alors que l'on poursuive la procédure commencée en adoptant la règle
suivante : à chaque étape, on essaie de séparer le sommet obtenu où l'évaluation par
défaut calculée est la plus faible possible.
B
C D E
A 3
5
0
+
B +
0
0
0
C 0
+
2
+
D 0
2
+
0
Matrice 8
(AE + EA)
48
52
H
H1
H2
AE
AE
H3
H4
EA
EA
52
52
56