218
Recherche opérationnelle
Soit
Soit encore
Mais on a également
(flot sortant de la coupe)
Donc :
car est non saturant.
Cette opération a donc entraîné une augmentation de
.
À chaque fois donc que l'on trouve un flot non saturant, mais maximal sur , on peut
changer de telle façon que
augmente. Or
est borné supérieurement par
l'ensemble des valeurs
,
étant saturé. Au bout d'un certain temps donc, on
obtiendra un flot saturant sur , et donc le flot de coût minimal.
Par ailleurs, lorsqu'on a un flot
non saturant sur
, on continue l'algorithme de la
façon suivante.
On augmente les
pour les
et on diminue les
pour les
d'une même
quantité, de telle façon qu'une quantité
devienne égale à
. Cette opération
consiste donc à ajouter un arc
:
- Soit le sommet
n'était pas saturé, et on va, en partant du flot précédent,
pouvoir saturer ce sommet et donc augmenter le flot.
- Soit le sommet
était saturé, alors on n'augmente pas nécessairement le flot,
mais on augmente par contre le nombre de sommets marqués , puisque qu'on
marque
(les autres sommets marqués de restent marqués, puisqu'ils
n'étaient pas marqués par les arcs
, les seuls qui risquent d'être supprimés
par la modification de .)