La notion de coupe

On appelle coupe la partition de l'ensemble des nuds 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 :

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

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

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

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.