next up previous
suivant: Quelques exemples de problèmes monter: Quelques techniques utilisées sur précédent: Le graphe d'écart

La notion de coupe

On appelle coupe la partition de l'ensemble des n\oeuds d'un réseau en deux ensembles notés $ S$ et $ \overline{S}$. Une telle coupe est notée $ [S, \, \overline{S}]$ et devient une st-coupe si $ s \in S$ et $ t \in \overline{S}$. Deux ensembles d'arcs sont à étudier en particulier :

\begin{displaymath}
\left\{
\begin{array}{lclcl}
(S,\,\overline{S}) &=& \left...
...t } j \in
S \right \} &=& \omega^-(S)
\end{array}
\right.
\end{displaymath}

On définit la capacité de la st-coupe $ [S, \, \overline{S}]$, et l'on note $ u([S,\,\overline{S}])$, la quantité :

$\displaystyle u([S,\,\overline{S}]) = \sum_{(\ivj) \in (S,\,\overline{S})} u_{ij}
$


\begin{defi}[Coupe minimum]
On appelle \emph{coupe minimum}, la st-coupe de capacit\'e minimale.
\end{defi}

\begin{theo}[Th\'eor\\lq eme flot-max / coupe-min]
La valeur maximale du flot pouv...
... sur un r\'eseau est \'egale \\lq a la
capacit\'e de la coupe minimum.
\end{theo}
Cette notion sera étudiée plus en détails lors de la présentation de l'algorithme de Ford et Fulkerson pour la recherche du flot max.

Bruno Garcia 2000-12-17