Mathematik für Faule: Effizientes Rechnen/Flüsse

Satz (Der Fluss entlang einer Dichotomie ist gleich dem Gesamtfluss):

Es sei ein gerichtetes Netzwerk $N=(V,E)$ gegeben, zusammen mit einer Kapazitätszuordnung $c:E\to \mathbb {R} _{\geq 0}$ und einem Fluss $f:E\to \mathbb {R} _{\geq 0}$ bezüglich der Start- bzw. Zielvertex $s,t$. Ferner sei $V=S\sqcup T$ eine Dichotomie von $V$ mit $s\in S$ und $t\in T$. Dann gilt:

$|f|=f(S,T)$.

Beweis: Wir können die Dichotomie $S\sqcup T$ erhalten, indem wir zuerst $S=\{s\}$ setzen, und dann in beliebiger (aber fester) Reihenfolge Vertizes von $T$ wegnehmen und gleichzeitig zu $S$ hinzufügen. Wenn wir beweisen, dass dabei $f(S,T)$ unverändert bleibt, so sind wir fertig, denn am Anfang ist dieser Wert gerade $|f|$ nach Definition. Also: Wird ein Vertex $v$ von $T$ nach $S$ verschoben, so muss $f(S,T)$ wie folgt verändert werden:

1. Für alle Kanten, die vom alten $S$ zu $v$ gehen, muss die Flussstärke abgezogen werden, denn sie war ja vorher in $f(S,T)$ mit eingerechnet, da ja $v\in T$ war.
2. Für alle Kanten, die von $v$ zum alten $S$ gehen, muss die Flussstärke hinzugefügt werden.
3. Für alle Kanten, die von $v$ zum alten $T$ gehen, muss die Flussstärke offensichtlich hinzugefügt werden.
4. Für alle Kanten, die vom alten $T$ zu $v$ gehen, muss die Flussstärke abgezogen werden.

Mit anderen Worten: Alle ausgehenden Flussstärken werden hinzugefügt, und alle eingehenden Flussstärken werden abgezogen. Dass $f(S,T)$ gleich bleibt, folgt nun aus der Flusserhaltungsgleichung. $\Box$