Network Flows Explained: Max Flow and Min Cut Made Simple

A flow network is a directed graph where each edge has a capacity — the maximum amount of stuff it can carry — and the goal is to push as much flow as possible from a source vertex s to a sink vertex t. The max-flow min-cut theorem says the maximum achievable flow exactly equals the capacity of the smallest cut separating s from t.

Network flows matter because "how much can get through?" is everywhere: water through pipes, traffic through roads, data through network links. Max flow finds the system's true throughput, and min cut finds its bottleneck.

Key Concepts

• Capacity c(u, v): the maximum flow an edge can carry.
• Flow conservation: at every vertex except s and t, inflow equals outflow — flow is neither created nor destroyed in the middle.
• Value of a flow: the total flow leaving the source (equivalently, arriving at the sink).
• Cut: a split of vertices into S (containing s) and T (containing t); its capacity is the sum of capacities of edges from S to T.
• Max-flow min-cut theorem: the maximum flow value equals the minimum cut capacity.
• Residual graph: tracks remaining capacity on each edge plus reverse edges that allow "undoing" flow — the key to the Ford-Fulkerson method.

How It Works

Ford-Fulkerson: (1) start with zero flow; (2) find any s–t path with leftover capacity — an augmenting path; (3) push as much flow as the path's tightest edge allows; (4) update the residual graph, adding reverse edges so later steps can reroute earlier choices; (5) repeat until no s–t path remains. The flow is then maximum, because every s–t cut's capacity upper-bounds any flow, and at termination the vertices reachable from s define a cut whose capacity exactly equals the flow.

Worked Example

Capacities: s→A = 10, s→B = 10, A→t = 8, B→t = 12, A→B = 4. Augment s→A→t: bottleneck min(10, 8) = 8; push 8. Augment s→B→t: bottleneck min(10, 12) = 10; push 10. Augment s→A→B→t: bottlenecks are 2 (s→A left), 4, 2 (B→t left) — push 2. Total flow = 8 + 10 + 2 = 20. Now s→A and s→B are saturated, so no augmenting path remains. Min cut check: S = {s}, T = {A, B, t} has capacity 10 + 10 = 20 = flow value — maximum, confirmed by the theorem. The bottleneck is the source's outgoing edges.

Common Misconceptions

• Max flow is limited by cuts, not by the longest path. Beginners look for one big path; the answer is about the total across all routes and the narrowest cross-section of the network.
• A min cut is found by the algorithm, not guessed. The vertices reachable from s in the final residual graph define the minimum cut exactly.

Real-World Applications

• Supply chains: maximum goods shippable from factories to stores through limited-capacity routes.
• Traffic engineering: the most vehicles a road network can carry; the min cut is the congestion bottleneck to widen.
• Telecommunications: data throughput of a network; cuts reveal the critical links whose failure hurts most.
• Image segmentation: min cut separates foreground from background in computer vision.

A flow network pushes stuff from source to sink through limited pipes, and the max-flow min-cut theorem ties it together: the best throughput equals the narrowest bottleneck. Find the min cut and you find both the limit and where to fix it.