Max flow, min cut, and the Ford-Fulkerson algorithm
Network flow models the transportation of commodities through a network from a source to a sink. Each edge has a capacity limit, and we want to maximize the total flow while respecting these constraints.
Flow theory connects graph structure to optimization: the Ford-Fulkerson algorithm finds maximum flow by iteratively discovering augmenting paths, while the max-flow min-cut theorem reveals a deep duality between flow and connectivity.
A flow network is a directed graph where each edge has a capacity. Flow travels from a source to a sink, obeying capacity constraints and conservation laws. Click edges to adjust flow and observe how the constraints interact.
Click an edge to select it, then use controls below to adjust flow
Key insight: A valid flow must satisfy two constraints at every node: capacity (flow cannot exceed edge capacity) and conservation (flow in equals flow out at intermediate nodes).
The Ford-Fulkerson algorithm finds maximum flow by repeatedly discovering augmenting paths from source to sink in the residual graph and pushing flow along them. This implementation uses BFS (Edmonds-Karp variant), guaranteeing O(VE^2) time.
Key insight: The residual graph includes backward edges that allow the algorithm to “undo” previous flow decisions, ensuring it always converges to the global optimum.
The max-flow min-cut theorem states that the maximum flow from source to sink equals the minimum capacity of any cut separating them. A cut partitions vertices into two sets, with the source in one and the sink in the other.
Key insight: This duality between flow and cuts is a cornerstone of combinatorial optimization — the bottleneck of any network is determined by its weakest separating boundary.
Maximum bipartite matching reduces to a max-flow problem: connect a source to one partition, the other partition to a sink, and set all capacities to 1. The maximum flow equals the size of the largest matching.
Green edges = matched pairs in optimal solution
Key insight: Reducing matching to flow demonstrates the power of network flow as a general framework — many optimization problems on bipartite structures can be solved this way.