Problèmes de flots
233
Sur la matrice 3, par exemple, cette procédure donne :
On retrouve bien
Remarquons que l'on pourrait se passer de cette procédure puisque le traitement du
graphe associé
nous a déjà fourni les ensembles
; mais parfois le
couplage maximal est tellement évident qu'il ne nécessite pas la prise en considération
de ce graphe et que l'on peut alors travailler directement sur la matrice des coûts.
À présent, nous savons qu'il faut isoler le tableau
pour y repérer l'élément de
plus faible valeur.
On voit alors qu'il suffit sur la matrice précédente de rayer les lignes non marquées et les
colonnes marquées pour obtenir le tableau restant
. On vérifie que tous les
éléments non rayés sont bien strictement positifs. On cherche alors le plus petit de ces
éléments positifs; c'est ici l'élément
égal à . On sait dans ces conditions :
a) qu'on le retranche des éléments non rayés
.
b) qu'on l'ajoute aux éléments
c'est-à-dire aux éléments rayés deux fois.
c) qu'on ne touche pas aux éléments
et
c'est-à-dire aux éléments rayés
une seule fois.
Ces opérations donnent alors la nouvelle matrice des coûts, la matrice 4 :
a
b
c
d
e
f
A
4
1
9
0
0
10
B
14
4
8
0
7
4
C
0
0
0
1
3
0
D
6
5
7
0
7
5
E
5
4
10
0
2
4
F
2
7
13
0
4
1
-1
-1
-1
-1
-1
+1
a
b
c
d
e
f
A
4
1
9
1
0
10
B
13
3
7
0
6
3
C
0
0
0
2
3
0
D
5
4
6
0
6
4
E
4
3
9
0
1
3
F
1
6
12
0
3
0