162
Recherche opérationnelle
Il est évident qu'on ne change pas de circuit hamiltonien optimal lorsqu'on diminue les
valeurs de tous les arcs partant de A d'une même quantité : en effet, cette opération, étant
donné qu'un circuit hamiltonien quelconque emprunte un seul arc issu de A, ne fait que
diminuer de cette quantité les valeurs de tous les circuits hamiltoniens existant dans le
graphe considéré. Dans ces conditions, on peut diminuer tous les éléments de la
première ligne de la matrice ci-dessus d'une quantité telle que l'on fasse apparaître un
zéro. Cette quantité est ici égale à 11. On peut faire le même raisonnement sur les lignes
relatives à B, à C, etc., si bien que l'on fait apparaître un zéro en moins sur la ligne :
La somme des éléments ôtés aux différentes lignes est :
.
Comme tous les éléments de la nouvelle matrice sont positifs ou nuls, tout circuit
hamiltonien a une valeur, calculée à partir de ces éléments, également positive ou nulle,
ce qui signifie que, puisqu'en diminuant les éléments d'une ligne on diminuait d'autant
les valeurs de l'ensemble des circuits hamiltoniens, la valeur de ces derniers est au moins
égale à .
Mais on peut faire le même raisonnement sur les colonnes puisqu'un circuit hamiltonien
emprunte un seul des arcs arrivant à un sommet.
On voit alors qu'on peut enlever 2 aux éléments de la nouvelle
et à ceux de la
colonne D, ce qui donne la nouvelle matrice :
A
B
C D E
A +
15 17 16 11
B 15 +
6
10 9
C 17 6
+
12 +
D 16 10 12 +
13
E 11 9
+
13 +
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 1
Matrice 2
- 11
- 6
- 6
- 10
- 9
A
B
C D E
A +
15 17 16 11
B 15 +
6
10 9
C 17 6
+
12 +
D 16 10 12 +
13
E 11 9
+
13 +
Matrice 1