Max-Flow Problem

Finde einen Maximalen Fluss in einem Flussnetzwerk.

Um dieses Problem zu lösen nutzen wir das Hilfskonstrukt Residualnetzwerk. Auf einem Residualnetzwerk kann auch einen Fluss definiert werden.

Algorithmen

Primaler Algorithmus: Ford-Fulkerson Algorithmus Dualer Algorithmus: Push-Relabel Algorithmus

Die Dualität des Problems liefert hier also eine obere und untere Schranke für die optimale Lösung.

Als Lineares Optimierungsproblem

max⁡x∈R∣A∣∑a∈δout (s)xa−∑a∈δin (s)xa s.t. 0≤xa≤ca fu¨r alle a∈A,∑a∈δin (v)xa=∑a∈δ out (v)xa fu¨r alle v∈V\{s,t}.\begin{aligned} \max _{x \in \mathbb{R}^{|A|}} & \sum_{a \in \delta^{\text {out }}(s)} x_{a}-\sum_{a \in \delta^{\text {in }}(s)} x_{a} \\ \text { s.t. } & 0 \leq x_{a} \leq c_{a} \text { für alle } a \in A, \\ & \sum_{a \in \delta^{\text {in }}(v)} x_{a}=\sum_{a \in \delta^{ \text { out }}(v)} x_{a} \text { für alle } v \in V \backslash\{s, t\} . \end{aligned}

Überlegen Sie sich, wann dieses LP unbeschränkt ist und welcher Situation im Digraphen D dieses Phänomen entspricht.