The flow network
A flow network is a directed graph where each edge has a capacity, the most units that may travel along it. One node is the source and one is the sink. We want to push as many units as possible from source to sink without exceeding any capacity.
Two rules every flow obeys
- Capacity rule: the flow on an edge never exceeds its capacity.
- Conservation rule: at every node except source and sink, flow in equals flow out. Nothing is created or lost in the middle.
The total leaving the source is the value of the flow. The largest possible value is the maximum flow.
What a cut is
A cut splits the nodes into two sides, one holding the source and the other holding the sink. The capacity of the cut is the sum of capacities on edges crossing from the source side to the sink side. The smallest such total is the minimum cut.
The famous theorem
The max flow min cut theorem says these two numbers are always equal. The most you can push equals the cheapest set of edges whose removal disconnects source from sink. Intuitively, a bottleneck both limits flow and forms the natural place to cut.
Key idea
Maximum flow through a network always equals the capacity of its minimum cut, so a bottleneck both caps throughput and reveals the weakest barrier.