Problèmes de flots
231
En effet, pour 1), s'il en était ainsi, le sommet de , extrémité initiale de l'arc saturé
entre
et serait marqué. Tous les arcs
sont donc de flot nul.
Pour 2), c'est également évident, car les arcs
étant de capacité infinie, un arc entre
et , le sommet initial dans
étant marqué, entraînerait le marquage du sommet
de .
On peut alors réécrire la matrice des coûts (ici la matrice 3) en réordonnant les lignes et
les colonnes de la façon suivante :
D'après ce qu'on vient de voir, les éléments
sont tous positifs (pas d'arcs
dans le graphe équivalent). Aucun des éléments
n'est un zéro encadré.
Prenons alors le plus petit élément du tableau
; soit cet élément. On a
.
Retranchons des lignes ; on fait apparaître au moins un zéro dans le tableau
.
Comme il peut y avoir des zéros dans le tableau
, nous allons ajouter
aux
colonnes . Cette double opération se traduit par le bilan final :
Comme les zéros encadrés du couplage maximal se trouvent dans les tableaux
et
on voit que l'on n'a transformé aucun de ces zéros. Par contre, on a fait
apparaître un zéro dans le tableau
. Ce faisant on est sûr d'obtenir un nouveau
couplage de taille au moins égale à celle du couplage précédent.
Plus précisément, une fois la matrice transformée suivant les opérations décrites cidessous, on considère le nouveau graphe associé pour y chercher le flot maximal, donc
le couplage maximal.
Y1
Y2
X1
Pas de 0
ni de 0
X2
pas de 0
Y1
Y2
X1
X2
-α + = 0 - α
+ α
0