Démonstration du théorème Flot max / Coupe min : le début

La capacité résiduelle $$r_{[S,\,\bar{S}]}$$ d'une st-coupe $[S,\,\bar{S}]$ s'écrit :

$$r_{[S,\,\bar{S}]}=\sum_{(i,\,j) \: \in \: (S,\,\bar{S})} r_{ij}$$

Soit $v$ la valeur du flot. Mettant à profit la notion de coupe, nous pouvons l'écrire ainsi :

$$v = \sum_{j : (s,\:j) \: \in \: E} x_{sj} \quad = \quad \sum_{i \... ...\in \: G } x_{ij} \quad - \quad \sum_{j:(j,\:i) \: \in \: G} x_{ji} \right]$$

Soient maintenant 2 sommets $p$ et $q$ appartenant tous deux à $S$. Il est possible de simplifier l'expression précédente en remarquant que $x_{pq}$ et $x_{qp}$ vont apparaître des deux côtés du signe $-$, une fois lors de la somme portant sur $p$ et une fois lors de la somme portant sur $q$. Aussi, l'on peut réécrire $v$ :

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

où l'on notera :

$$\left\{ \begin{array}{l@{\quad}l} \displaystyle\sum_{(i,\... ... arri\\lq ere de la coupe $[S,\,\bar{S}]$} \end{array} \right.$$

La valeur du flot $v$ est donc égale au flot net de la coupe $[S,\,\bar{S}]$. On a :

$$\sum_{(i,\,j) \: \in (S,\,\bar{S})} x_{ij} \quad \leqslant \quad \sum_{(i,\,j) \: \in (S,\,\bar{S})} u_{ij}$$

et comme :

$$\sum_{(i,\,j) \: \in (\bar{S},\,S)} x_{ij} \quad \geqslant \quad 0$$

alors :

$$v \quad \leqslant \quad \sum_{(i,\,j) \: \in (S,\,\bar{S})} u_{ij} = u_{[S,\,\bar{S}]}$$

On obtient donc que la valeur du flot est inférieure ou égale à la capacité de toute st-coupe du réseau. Par extension, si l'on découvre un flot de valeur égale à la capacité d'une coupe, alors :

1. Le flot est maximal
2. La coupe est de capacité minimale