next up previous
suivant: Augmentation maximale du flot monter: L'algorithme de Ford & précédent: Capacité résiduelle dans le

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

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

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

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

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

où l'on notera :

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

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

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

et comme :

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

alors :

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

next up previous
suivant: Augmentation maximale du flot monter: L'algorithme de Ford & précédent: Capacité résiduelle dans le
Bruno Garcia 2000-12-17