ein Fluß in einem Netzwerk.

Es sei N ein Netzwerk mit der Eckenmenge E(N), der Bogenmenge B(N), der Quelle u, der Senke v und der Kapazitätsfunktion c. Ist f : B(N) → ℝ eine weitere Funktion und A ⊆ B(N), so setzen wir

\begin{eqnarray}f(A)=\displaystyle \sum _{k\in A}f(k).\end{eqnarray}

Sind X, Y ⊆ E(N), so bedeute im folgenden (X, Y) die Menge der Bogen aus B (N), die ihre Anfangsecke in X und ihre Endecke in Y besitzen. Ist X ⊆ E(N) und \(\bar{X}=E(N)\backslash X\), so setzen wir \({f}^{+}(X)=f((X,\bar{X}))\) und \({f}^{-}(X)=f((\bar{X},X))\). Darüber hinaus sei f⁺ (x) = f⁺ ({x}) und f⁻(x) = f⁻ ({x}) für eine Ecke x ∈ E(N). Die Funktion f heißt nun Netzwerkfluß oder Fluß im Netzwerk N, wenn sie für alle k ∈ B(N) und alle x ∈ E(N) \{u, v} die beiden folgenden Bedingungen erfüllt:

\begin{eqnarray}0\le f(k)\le c(k),\quad\quad\quad\quad\quad{f}^{+}(x)={f}^{-}(x).\end{eqnarray}

Die erste Bedingung nennt man Kapazitätsbeschränkung und die zweite Kirchhoffsche Regel. Die Kirchhoffsche Regel f⁺ (x) = f⁻ (x) besagt, daß bei einem Fluß in jeder Ecke, die von der Quelle und der Senke verschieden ist, der einlaufende und der auslaufende Gesamtfluß übereinstimmen.

Ist f ein Netzwerkfluß in N, so überlegt man sich leicht die Identität f⁺ (u) = f⁻ (v) und nennt

\begin{eqnarray}w(f)={f}^{+}(u)={f}^{-}(v)\end{eqnarray}

Flußstärke oder Wert von f. Man spricht von einem maximalen Fluß f in N, wenn w(f) ≥ w(f′) für jeden Fluß f' inN gilt. Man beachte, daß a priori die Existenz eines maximalen Flusses durchaus nicht selbstverständlich ist. Man kann aber zeigen, daß es einen derartigen Fluß immer geben muß. Dazu benötigen wir noch einige Begriffe.

Ist X ⊆ E(N) mit u ∈ X und \(v\in \bar{X}\), so nennt man \((X,\bar{X})\subseteq B(N)\) einen Schnitt in N, und

\begin{eqnarray}\text{cap}\quad(X,\bar{X})=\displaystyle \sum _{k\in (X,\bar{X})}c(k)\end{eqnarray}

Kapazität des Schnittes \((X,\bar{X})\). Gibt es in N keinen Schnitt \((Y,\bar{Y})\) mit \(\text{cap}\quad(Y,\bar{Y})\lt \text{cap}\quad(X,\bar{X})\), so heißt \((X,\bar{X})\) minimaler Schnitt in N. Da es nur endlich viele Schnitte in einem Netzwerk gibt, existiert natürlich stets ein minimaler Schnitt. Nun kommen wir zu einem der Hauptergebnisse der Flußtheorie, das insbesondere die Existenz eines maximalen Flusses sichert.

In jedem Netzwerk stimmt die Flußstärke eines maximalen Flusses mit der Kapazität eines minimalen Schnittes überein.

Dieser Satz ist in der Literatur unter dem Namen Max-Flow-Min-Cut-Theorem bekannt und wurde 1956 von L.R. Ford und D.R. Fulkerson, und unabhängig im gleichen Jahr von P. Elias, A. Feinstein undC.E. Shannon entdeckt. Darüber hinaus bewiesen Ford und Fulkerson 1956 noch den sogenannten Ganzheitssatz (auch Integral-Flow-Theorem genannt), der viele interessante Anwendungen besitzt.

Ein Netzwerk mit einer ganzzahligen Kapazitätsfunktion besitzt einen ganzzahligen maximalen Fluß.

Mit Hilfe des Ganzheitssatzes lassen sich z. B. die Mengerschen Sätze beweisen. Liegt ein Netzwerk N mit rationalen Kapazitäten vor, so existieren verschiedene polynomiale Algorithmen, mit deren Hilfe man einen maximalen Fluß bestimmen kann. Ein erster solcher Algorithmus der Komplexität O(|E(N)||B(N)|²) wurde 1972 von J. Edmonds und R.M. Karp gegeben.

Ist c die Kapazitätsfunktion in einem Netzwerk N, und gilt c(k) = 0 oder c(k) = 1 für alle k ∈ B(N), so spricht man auch von einem NullEins-Netzwerk. Ein Fluß f in einem Netzwerk heißt Null-Eins-Fluß, wenn f nur die Werte 0 oder 1 annimmt. Für eine Reihe von kombinatorischen Anwendungen benötigt man nur Null-Eins-Flüsse in Null-Eins-Netzwerken, und für solche Netzwerke existieren spezielle Algorithmen, mit deren Hilfe man viel schneller maximale Null-Eins-Flüsse berechnen kann.

[1] Ahuja, R.K.; Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, New Yersey, 1993.