next up previous
suivant: Forme naïve de l'algorithme monter: L'algorithme de Ford & précédent: Démonstration du théorème Flot

Augmentation maximale du flot

Connaissant une valeur de flot $ v$ et considérant une st-coupe quelconque $ [S,\,\bar{S}]$, de quelle valeur $ \Delta v$ peut-on encore espérer augmenter $ v$ ? Supposons donc qu'il existe un flot $ x'$ de valeur $ v \, + \, \Delta v$. Par la relation précédente, l'on a :

$\displaystyle v \,+\, \Delta v \quad \leqslant \quad \sum_{(i,\,j) \: \in (S,\,\bar{S})} u_{ij}
$

pour toute st-coupe $ [S,\,\bar{S}]$. Or, nous avons vu dans la démonstration précédente que $ v$ est égal au flot net dans la coupe, soit :

$\displaystyle v = \sum_{(i,\:j) \: \in \: (S,\,\bar{S})} x_{ij} -
\sum_{(i,\:j) \: \in \: (\bar{S},\,S)} x_{ij}
$

qui est aussi égal à :

$\displaystyle v = \sum_{(i,\:j) \: \in \: (S,\,\bar{S})} x_{ij} -
\sum_{(i,\:j) \: \in \: (\bar{S},\,S)} x_{ji}
$

d'où :

$\displaystyle v \,+\, \Delta v \, - \, v \quad \leqslant\
\sum_{(i,\,j) \: \in...
...in \: (S,\,\bar{S})} x_{ij}
+
\sum_{(i,\:j) \: \in \: (\bar{S},\,S)} x_{ij}
$

soit :

$\displaystyle \Delta v \quad \leqslant \quad \sum_{(i,\,j) \: \in (S,\,\bar{S})} (u_{ij}-x_{ij})
+
\sum_{(i,\:j) \: \in \: (\bar{S},\,S)} x_{ij}
$

où encore :

$\displaystyle \Delta v \quad \leqslant \quad \sum_{(i,\,j) \: \in (S,\,\bar{S})} (u_{ij}-x_{ij})
+
\sum_{(i,\:j) \: \in \: (\bar{S},\,S)} x_{ij}
$

Soit finalement :

$\displaystyle \Delta v \quad \leqslant \quad \sum_{(i,\,j) \: \in (S,\,\bar{S})} r_{ij}
+
\sum_{(i,\:j) \: \in \: (\bar{S},\,S)} x_{ij}
$

Or, comme un flot est une quantité positive, l'on en déduit donc que l'augmentation maximale est bornée par la capacité résiduelle de la coupe.

Bruno Garcia 2000-12-17