Guided Notes

Maximum Flow

Flow networks, capacities, the Ford-Fulkerson method, residual graphs, and Edmonds-Karp.

Flow networks

Slide 1 / 5

A flow network is a directed graph where each edge has a capacity — the most that can flow through it: water through pipes, cars along roads, data through network links.

Flow enters at the source (s) and leaves at the sink (t). Two rules: • Capacity — flow on an edge can't exceed its capacity. • Conservation — at every other vertex, flow in equals flow out.

The maximum flow problem asks: what's the most that can get from s to t?