5.4 The max-flow min-cut theorem¶
Part 3 · Flows · Chapter 5 · Chapter 5: Maximum flow · Lecture notes, volume 3 (PDF) · Exercises: Maximum flow · App: Maximum flow: Ford–Fulkerson and Edmonds–Karp
Theorem 5.8: max-flow min-cut
Let \(\vet{x}\) be a feasible flow of value \(v\). The following statements are equivalent:
-
(a) \(\vet{x}\) is a maximum flow;
-
(b) the residual network \(G(\vet{x})\) has no augmenting path;
-
(c) \(v=u(S,N \setminus S)\) for some \(s\)–\(t\) cut \((S,N \setminus S)\).
Moreover, a maximum flow exists, and the maximum value of a flow equals the minimum capacity of an \(s\)–\(t\) cut:
Proof
(a) implies (b). An augmenting path would give, by Lemma 5.7, a feasible flow of value \(v+\delta>v\).
(b) implies (c). Let \(S\) be the set of the nodes reachable from \(s\) in \(G(\vet{x})\); then \(s \in S\) and, by (b), \(t \notin S\).
-
If an arc \((i,j) \in \delta^+(S)\) had \(x_{ij}<u_{ij}\), the forward arc \((i,j)\) would be in \(G(\vet{x})\), and \(j\) would be reachable: hence \(x_{ij}=u_{ij}\).
-
If an arc \((i,j) \in \delta^-(S)\) had \(x_{ij}>0\), the backward arc \((j,i)\), with \(j \in S\), would be in \(G(\vet{x})\), and \(i\) would be reachable: hence \(x_{ij}=0\).
-
By Corollary 5.4, \(v=u(S,N \setminus S)\).
(c) implies (a). By Corollary 5.4.
Existence and equality. The feasible region of the \(\mathrm{MF}\) model is nonempty (\(\vet{x}=\vet{0}\), \(v=0\)) and bounded (\(0 \le x_{ij} \le u_{ij}\) and \(|v| \le \sum_{(i,j) \in A} u_{ij}\)), so the model has an optimal solution (Chapter 15 «The geometry of Linear Programming»). For a maximum flow, (a) implies (c): some cut has capacity \(\tilde{v}\), and by Corollary 5.4 no cut has a smaller capacity. □
-
The proof of (b) implies (c) is constructive: at a maximum flow, the nodes reachable from \(s\) in the residual network form a minimum cut.
-
A flow and a cut with \(v=u(S,N \setminus S)\) certify each other: the cut proves that no flow is better, and the flow proves that no cut is smaller.
Example 5.5: the maximum flow of the reference network
On the reference network of Example 5.1 the flow
| arc | \((1,2)\) | \((1,3)\) | \((2,4)\) | \((3,2)\) | \((3,5)\) | \((4,3)\) | \((4,6)\) | \((5,4)\) | \((5,6)\) |
|---|---|---|---|---|---|---|---|---|---|
| \(\tilde{x}_{ij}\) | \(3\) | \(4\) | \(3\) | \(0\) | \(4\) | \(0\) | \(4\) | \(1\) | \(3\) |
| \(u_{ij}\) | \(5\) | \(4\) | \(3\) | \(2\) | \(4\) | \(2\) | \(4\) | \(2\) | \(3\) |
is feasible, with value \(\tilde{x}_{12}+\tilde{x}_{13}=7\). For \(S=\{1,2\}\) the forward arcs \((1,3)\), \((2,4)\) are saturated and the backward arc \((3,2)\) is empty, so
By Theorem 5.8, \(\tilde{\vet{x}}\) is a maximum flow, \(\tilde{v}=7\), and \((\{1,2\},\{3,4,5,6\})\) is a minimum cut. In \(G(\tilde{\vet{x}})\) the nodes reachable from \(1\) are exactly \(1\) and \(2\). In the figure, \(S\) is shaded and the forward arcs of the cut are green.
-
Uniqueness. By Corollary 5.4, every maximum flow saturates the forward arcs and empties the backward arcs of each of the three minimum cuts of Example 5.2:
\[ \begin{aligned} S=\{1,2\}: &\quad x_{13}=4,~ x_{24}=3,~ x_{32}=0,\\ S=\{1,2,3\}: &\quad x_{35}=4,~ x_{43}=0,\\ S=\{1,2,3,4,5\}: &\quad x_{46}=4,~ x_{56}=3. \end{aligned} \]Conservation at nodes \(1\) and \(4\) then gives \(x_{12}=7-x_{13}=3\) and \(x_{54}=x_{43}+x_{46}-x_{24}=1\): \(\tilde{\vet{x}}\) is the unique maximum flow, while the minimum cut is not unique.
Saturated arcs and cuts
The saturated arcs of a maximum flow do not form a cut in general. Under \(\tilde{\vet{x}}\) the saturated arcs are \((1,3)\), \((2,4)\), \((3,5)\), \((4,6)\), \((5,6)\), with total capacity \(18\). A minimum cut is read from the nodes reachable from \(s\) in the residual network.
A flow is maximum if and only if its residual network has no augmenting path, if and only if its value equals the capacity of a cut. The maximum value equals the minimum cut capacity, and the nodes reachable from \(s\) in the residual network of a maximum flow form a minimum cut.