236
Recherche opérationnelle
On continue alors en revenant à la phase 2; graphe associé à la matrice 5, et muni du
couplage précédent :
On n'arrive pas à marquer . Le couplage précédent reste optimal. On a ici l'exemple
d'une itération sans progrès apparent, puisque la taille du couplage n'augmente pas.
Cependant, comme on l'avait annoncé, c'est la taille de l'ensemble
qui augmente,
passant de 1 à 2. La matrice 5 décomposée, donne :
x 0
A
B
C
D
E
F
a
b
c
d
e
f
z
x 0
x 0
-d
+D
-e
+E
a
b
c
d
e
f
A
4
1
9
2
0
10
B
12
2
6
0
5
2
C
0
0
0
3
3
0
D
4
3
5
0
5
3
E
3
2
8
0
0
2
F
1
6
12
1
3
0