Kapazitäten von Schnitten und Flüssen

für Kapazitäten c:      c(S) = $\sum${c(e) | e $\in$ (S,$\overline{S}$)}.

Lemma; für jeden Fluß f und jeden Schnitt S gilt: f (N)$\le$c(S).

Folgerung: max{f (N) | $f$ ist Fluß für $N$}$\le$min{c(S) | $S$ ist Schnitt für $N$}

Satz (Max-Flow-Min-Cut): Hier gilt Gleichheit.