Flow Networks and Bottlenecks
A flow network models any system where something moves through a graph with capacity constraints: water in pipes, data in internet links, cars on highways, goods through supply chains. Each directed edge has a capacity — the maximum flow it can carry. The central question is: what is the maximum total flow from a designated source to a designated sink? This deceptively simple question spawned one of the most beautiful results in combinatorial optimization.
The Ford-Fulkerson Method
Published in 1956, the Ford-Fulkerson method finds maximum flow by repeatedly searching for augmenting paths — routes from source to sink with available capacity. Along each path, the algorithm pushes as much flow as the bottleneck edge allows. The key insight is the residual graph: a modified graph that tracks remaining forward capacity and allows 'undoing' flow by sending flow backward along already-used edges. When no augmenting path exists, the flow is maximum.
The Duality of Max Flow and Min Cut
The max-flow min-cut theorem, proved by Ford and Fulkerson, reveals a profound duality: the maximum flow through a network exactly equals the capacity of the minimum cut. A cut partitions the vertices so that source and sink are on opposite sides; its capacity is the sum of edge capacities crossing the partition. This means the bottleneck of the network — its weakest point — completely determines its maximum throughput. This duality has deep connections to linear programming.
Applications Everywhere
Network flow is one of the most broadly applicable algorithmic tools. Bipartite matching — assigning workers to jobs — reduces to max flow. Image segmentation in computer vision uses min-cut to separate foreground from background. Airline scheduling, baseball elimination, project selection, and telecommunications routing all have elegant flow formulations. The Edmonds-Karp variant (BFS-based Ford-Fulkerson) guarantees polynomial time, making these applications practical even at scale.