5.2 Cuts¶
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
Definition 5.2: \(s\)–\(t\) cut
Let \(S \subseteq N\) with \(s \in S\) and \(t \notin S\). The \(s\)–\(t\) cut \((S,N \setminus S)\) is the partition of the nodes into \(S\) and \(N \setminus S\).
-
Its forward arcs are the arcs of \(\delta^+(S)\), from \(S\) to \(N \setminus S\), and its backward arcs the arcs of \(\delta^-(S)\), from \(N \setminus S\) to \(S\).
-
Its capacity is the total capacity of the forward arcs:
\[ u(S,N \setminus S)=\sum_{(i,j) \in \delta^+(S)} u_{ij} . \] -
A minimum cut is an \(s\)–\(t\) cut of minimum capacity.
-
The capacities of the backward arcs do not enter \(u(S,N \setminus S)\).
-
Each node other than \(s\) and \(t\) can be on either side, so a network has \(2^{n-2}\) \(s\)–\(t\) cuts.
-
As in Chapter 4, \(x(F)=\sum_{(i,j) \in F} x_{ij}\) for a set of arcs \(F\).
Lemma 5.3: flow across an \(s\)–\(t\) cut
Let \(\vet{x}\) be a feasible flow of value \(v\). Then, for every \(s\)–\(t\) cut \((S,N \setminus S)\),
In particular, with \(S=N \setminus \{t\}\), the net inflow of \(t\) is \(v\).
Proof
Let \(b_i\) be the net outflow of node \(i\) under \(\vet{x}\): \(b_s=v\) and \(b_i=0\) for \(i \notin \{s,t\}\). Then \(\vet{x}\) satisfies flow conservation with these balances, and Chapter 4, Lemma «flow across a cut» gives \(x(\delta^+(S))-x(\delta^-(S))=\sum_{i \in S} b_i\) for every \(S \subseteq N\).
-
With \(S=N\) no arc leaves or enters \(S\), so \(\sum_{i \in N} b_i=0\) and \(b_t=-v\).
-
For an \(s\)–\(t\) cut, \(s \in S\) and \(t \notin S\), so \(\sum_{i \in S} b_i=b_s=v\). □
Corollary 5.4: weak duality
For every feasible flow \(\vet{x}\) of value \(v\) and every \(s\)–\(t\) cut \((S,N \setminus S)\),
with equality if and only if \(x_{ij}=u_{ij}\) for every \((i,j) \in \delta^+(S)\) and \(x_{ij}=0\) for every \((i,j) \in \delta^-(S)\). In case of equality, \(\vet{x}\) is a maximum flow and \((S,N \setminus S)\) is a minimum cut.
Proof
By Lemma 5.3 and the bounds \(x_{ij} \le u_{ij}\) on \(\delta^+(S)\) and \(x_{ij} \ge 0\) on \(\delta^-(S)\),
-
Equality holds if and only if every bound used is tight, arc by arc.
-
In case of equality, every feasible flow \(\vet{x}'\) has value \(v' \le u(S,N \setminus S)=v\), and every \(s\)–\(t\) cut \((S',N \setminus S')\) has \(u(S',N \setminus S') \ge v=u(S,N \setminus S)\).
□
Example 5.2: the cuts of the reference network
The reference network of Example 5.1 has \(2^4=16\) \(s\)–\(t\) cuts. Next to each set \(S\), the capacity \(u(S,N \setminus S)\):
-
The minimum capacity is \(7\), attained by three cuts: \(S=\{1,2\}\), \(S=\{1,2,3\}\) and \(S=\{1,2,3,4,5\}\). By Corollary 5.4, no feasible flow has value larger than \(7\).
-
For \(S=\{1,2,3\}\) the forward arcs are \((2,4)\), \((3,5)\) and the backward arc is \((4,3)\). With the flow \(\bar{\vet{x}}\) of Example 5.1,
\[ \bar{x}_{24}+\bar{x}_{35}-\bar{x}_{43}=3+2-2=3=v, \qquad u(S,N \setminus S)=u_{24}+u_{35}=3+4=7 . \]
The capacity of a cut
The capacity \(u(S,N \setminus S)\) adds up the capacities of the forward arcs only. For \(S=\{1,2,3\}\) it is \(u_{24}+u_{35}=7\); adding the capacity of the backward arc \((4,3)\) would give \(9\), which bounds nothing. A flow on a backward arc brings units back into \(S\) and lowers the net flow across the cut.
The net flow across every \(s\)–\(t\) cut is the value \(v\), so \(v \le u(S,N \setminus S)\) for every flow and every cut, with equality when the forward arcs are saturated and the backward arcs empty. On the reference network no flow has value larger than \(7\).
Next: 5.3 The residual network