How much can flow from a source to a sink through a capacitated network?
Model flow in a directed network, find the maximum flow, and use the maximum-flow minimum-cut relationship.
How to model flow in a directed capacitated network, find the maximum flow from source to sink, identify cuts, and apply the maximum-flow minimum-cut theorem.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
Jump to a section
What this dot point is asking
You must model a capacitated directed network, find cuts and their capacities, and use the maximum-flow minimum-cut theorem to find the most that can flow.
Flow networks
A flow network is a directed graph where each edge has a capacity, the most it can carry (water in a pipe, cars on a road, data on a link). Flow enters at the source and leaves at the sink, and at every other vertex flow in equals flow out.
The maximum-flow minimum-cut theorem
The central result makes maximum flow easy to find: the bottleneck is the weakest cut.
When totalling a cut's capacity, count only edges directed from the source side to the sink side; edges pointing back do not add to that cut.
Finding the minimum cut
Test the sensible cuts, total the forward capacities of each, and pick the smallest. Only forward edges (source side to sink side) count towards a cut; this is the step most often done wrong.