Arbres et arborescences
163
On a ôté encore 6 aux valeurs des circuits hamiltoniens en conservant des valeurs
positives ou nulles aux arcs. Au total, on est sûr que la valeur d'un circuit hamiltonien du
graphe est supérieure ou égale à . On dira que 48 constitue une évaluation par défaut
sur l'ensemble des circuits hamiltoniens du graphe.
2) Séparation
Appelons
l'ensemble des circuits hamiltoniens du graphe. Nous allons partitionner
l'ensemble
en deux sous-ensembles disjoints : le sous-ensemble des circuits
hamiltoniens qui passent par un certain arc et ceux qui n'y passent pas. Comment choisir
cet arc ? L'algorithme de Little propose le raisonnement suivant : prenons un zéro de la
matrice 3, par exemple le zéro de l'arc
, et considérons les circuits hamiltoniens qui
ne passent pas par
. On peut alors calculer une nouvelle évaluation par défaut de la
valeur de ces circuits hamiltoniens particuliers. En effet, comme un circuit hamiltonien
quelconque doit emprunter un arc issu de A, l'arc le plus court après
qu'il puisse
emprunter est
de valeur 1; de même, puisqu'il doit emprunter un arc arrivant sur E,
l'arc de ce type le plus court est
ou
, de valeur 3. On voit que le fait d'exclure l'arc
d'un circuit hamiltonien fait que ce circuit, calculé sur la matrice 3 a une valeur au
moins égale à
, donc, calculé sur la matrice 1, une valeur au moins égale à
.
Cette quantité égale à 4 sera appelée regret pour l'arc
. Sur la matrice 3, on peut ainsi
calculer les regrets pour tous les arcs de valeur nulle, par la formule (si
sont les
éléments de la matrice).
j
ik
j
i
a
a

min
min
=
i
j
k

On obtient :
2
=
0
=
2
=
2
0
=
4
=
CB
BD
BC
AE
0
=
0
=
4
=
2
=
ED
EB
EA
DB
17
A
B
C D E
A +
4
6
5
0
B 9
+
0
4
3
C 11 0
+
6
+
D 6
0
2
+
3
E 2
0
+
4
+
Matrice 2
- 2
- 4
A
B
C D E
A +
4
6
1
0
B 7
+
0
0
3
C 9
0
+
2
+
D 4
0
2
+
3
E 0
0
+
0
+
Matrice 3