Max-Flow Min-Cut Theorem

Graph Theory · Axiom Academy

LESSON Max-Flow Min-Cut Theorem One of the most elegant results in graph theory, connecting maximum flow through a network with minimum capacity cuts. Source vertex s: where flow originates Sink vertex t: where flow terminates Capacity function c(u,v) ≥ 0: maximum flow on edge (u,v) Flow function f(u,v): actual flow on edge (u,v) Flow must satisfy two key constraints: capacity constraint (flow cannot exceed capacity) and flow conservation (flow into a vertex equals flow out, except at s and t). The animation below builds a simple flow network step by step. An s-t cut "separates" the source from the sink by partitioning the network into two parts. Think of it as a barrier that prevents flow from reaching the destination. Different cuts have different capacities, and finding the minimum capacity cut is central to the theorem. The capacity of a cut represents the maximum flow that could possibly cross from S to T. Different cuts have different capacities. The minimum cut is the cut with the smallest capacity among all possible s-t cuts. 4. Statement of the Max-Flow Min-Cut Theorem In any flow network, the maximum value of an s-t flow equals the minimum capacity of an s-t cut: In other words: The maximum amount of flow you can push through the network equals the capacity of the tightest bottleneck separating source from sink.

This is the written version of the interactive lesson above. See the full Graph Theory course.