Min Cut and the Max-Flow Min-Cut Theorem

Defines s-t cuts and their capacity, establishes weak duality between flows and cuts, and states the max-flow min-cut theorem. Shows how to extract a minimum cut from the residual graph after Ford-Fulkerson terminates, and how to use the theorem to compute max-flow values via cut enumeration.

Step 1 of 157%

Tutorial

s-t Cuts and Cut Capacity

An $s$ - $t$ cut in a flow network $G = (V, E)$ with source $s$ and sink $t$ is a partition of the vertex set into two pieces $(S, T)$ with $s \in S$ and $t \in T$ .

The capacity of the cut $(S, T)$ is the sum of the capacities of edges going from $S$ to $T$ :

c(S, T) = \sum\limits_{\substack{u \in S,\ v \in T \\ (u, v) \in E}} c(u, v).

Edges directed from $T$ back to $S$ (backward edges, relative to the cut) do not contribute.

For example, consider the network with edges

s \to a:\ 4,\quad s \to b:\ 7,\quad a \to b:\ 3,\quad a \to t:\ 5,\quad b \to t:\ 6.

The cut $S = \{s\}$ , $T = \{a, b, t\}$ has only two edges leaving $S$ , namely $s \to a$ and $s \to b$ . So

c(S, T) = 4 + 7 = 11.