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 :

$$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 :

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

qui est aussi égal à :

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

d'où :

$$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 :

$$\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 :

$$\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 :

$$\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.