13. Incremental Improvement: Max Flow, Min Cut

What this lecture covers

The lecture answers how to compute the maximum rate of flow from a source to a sink in a network with capacity-limited edges. It opens the second half of MIT's 6.046 course, moving from graph algorithms like shortest paths and minimum spanning trees into network flow, an optimization problem that will later be used as a tool for other problems such as bipartite matching.

By the end, you can define a flow network and a valid flow, compute the value of a flow and the capacity of a cut, understand why the value of any flow equals the flow across any s-t cut, and build a residual network to find augmenting paths — the mechanism behind the Ford-Fulkerson algorithm, whose full correctness proof is deferred to the next lecture.

Key ideas

• Flow network: a directed graph with a source s and sink t, where every edge (u,v) has a non-negative capacity c(u,v), and non-edges are treated as having capacity zero.
• Flow conservation: at every vertex other than the source and sink, the total flow in must equal the total flow out — no accumulation is allowed, analogous to Kirchhoff's current law.
• Skew symmetry: flow is defined so that f(u,v) = -f(v,u) for any pair of vertices, which lets the lecture treat 'positive flow' and 'net flow' as the same thing once self-loops and two-cycles between vertex pairs are disallowed.
• Value of a flow: the total flow leaving the source, f(S,V) in implicit summation notation; the lecture proves this always equals the total flow entering the sink.
• Cut: a partition of the vertices into sets S and T with the source in S and the sink in T; the flow across a cut always equals the value of the flow, regardless of how the cut is chosen (as long as s and t are separated).
• Capacity of a cut: the sum of capacities of edges going from S to T only; this gives an upper bound on the value of any flow, which is the core intuition behind the (not-yet-proved) max-flow min-cut theorem.
• Residual network: a graph on the same vertices where each edge represents remaining capacity (c(u,v) - f(u,v)) to increase flow, plus a reverse edge for any existing flow that could be decreased.
• Augmenting path: a path from s to t in the residual network; if one exists, the current flow is not maximum and can be increased by the minimum residual capacity along the path (this is the core step of Ford-Fulkerson).

Walkthrough

Defining flow networks (0:00)

The lecture introduces flow networks as directed graphs with a source and sink, edges carrying non-negative capacities, and a conservation law requiring everything entering an intermediate vertex to leave it. It notes that cycles are allowed in the graph, unlike in many earlier shortest-path examples, and frames the max flow problem as pushing as much 'commodity' as possible from source to sink without violating capacity or conservation.

A worked flow example and increasing flow (9:05)

Using a hand-drawn network with flow/capacity pairs on each edge, the lecture checks that conservation holds at each intermediate vertex and computes an initial flow value of three into the sink. It then shows that increasing the flow to four requires decreasing the flow on one edge while increasing others — demonstrating that max flow algorithms are not simply monotonic like Dijkstra or a greedy MST algorithm, which motivates the need for a more careful algorithmic approach.

Notation: flow value and skew symmetry (26:20)

The lecture formalizes flow as a function satisfying capacity constraints, conservation, and skew symmetry (f(u,v) = -f(v,u)), then introduces implicit summation notation, where a capital-letter set argument means summing over its members. Basic identities are established, such as f(X,X) = 0 and f(X union Y, Z) = f(X,Z) + f(Y,Z) for disjoint X and Y, setting up tools for the proofs that follow.

Value of a flow equals flow into the sink (38:38)

Using the implicit-summation identities, the lecture proves that the value of a flow, defined as everything pushed out of the source, exactly equals everything that arrives at the sink. The proof splits the vertex set around the source and sink and repeatedly applies flow conservation at intermediate vertices to cancel terms, illustrating how the notation shortens what would otherwise be a longer case-by-case argument.

Cuts and their capacity (46:45)

A cut is defined as any partition of the vertices into two sets with the source in one and the sink in the other — not necessarily a contiguous split. The lecture computes the flow across a specific example cut using skew symmetry to handle edges in both directions, then defines the capacity of a cut as the sum of capacities of edges crossing from the source side to the sink side, which only counts forward edges.

Flow across any cut equals the flow value, and the min-cut bound (1:01:00)

The lecture proves that for any cut, the flow across it equals the overall flow value, using the same implicit-summation technique and flow conservation on vertices outside {s, t}. Combined with the earlier observation that a cut's flow is bounded by its capacity, this gives an upper bound on the maximum possible flow value from any single cut — the foundation of the max-flow min-cut theorem, whose full proof is saved for the next lecture.

Residual networks and the Ford-Fulkerson step (1:08:02)

The residual network G_f has the same vertices as the original graph but includes an edge wherever residual capacity c(u,v) - f(u,v) is strictly positive, including reverse edges representing the option to shrink existing flow. The lecture builds a residual network for the earlier example, then defines an augmenting path as any s-to-t path in the residual network; if one exists, the flow can be increased by the minimum residual capacity along that path. Working through a concrete example, the lecture finds an augmenting path of value one, updates the flow on each edge accordingly (increasing some, decreasing one), and shows the resulting residual network has no further augmenting path — indicating the flow is maximal, though the general correctness argument is left for the next lecture.

Before you watch

• Review basic directed graph terminology (vertices, edges, paths, cycles) and be comfortable with summation notation.
• No specific prior algorithm from this course is required, but familiarity with how Dijkstra's algorithm and the MST algorithms from earlier lectures behave helps appreciate why max flow needs a different, non-monotonic approach.

Check your understanding

1. Why does the lecture disallow self-loops and two-vertex cycles in flow networks, and how does this simplify the relationship between 'positive flow' and 'net flow'?
2. Using implicit summation notation, sketch why the value of a flow out of the source must equal the total flow into the sink.
3. Why does the flow across any s-t cut equal the overall flow value, regardless of how the cut is chosen, and why does this give an upper bound on the maximum possible flow?
4. What does an edge in the residual network represent, and why can an augmenting path found there always be used to increase the original flow?