Flows, cuts and the max-flow min-cut theorem
Studying this course? Keep your progress in one place.
Key facts
- A feasible flow keeps every arc within its capacity and has flow in equal to flow out at every intermediate node.
- The capacity of a cut counts only arcs from the source side to the sink side.
- The value of any flow is at most the capacity of any cut.
- Max-flow min-cut theorem: the maximum flow equals the capacity of the minimum cut.
- Several sources or sinks are joined to a supersource or supersink.
Flow networks
A feasible flow stays within every arc's capacity and has flow in equal to flow out at each intermediate node.
A network flow problem uses directed arcs, each with a capacity. Flow enters at a source and leaves at a sink .
The value of a flow is the total leaving the source, which equals the total arriving at the sink. An arc is saturated when its flow equals its capacity.
- On every arc flow capacity
- At every intermediate nodeflow in = flow out
Worked example
Arcs carrying 6 and 5 units enter a node. One outgoing arc carries 7. How much does the other outgoing arc carry?
- 1
Flow in .
- 2
By conservation, flow out is also 11.
- 3
Other arc .
An arc has capacity 8 and flow 8. What is it called?
Cuts and their capacity
A cut splits the nodes into a source side and a sink side, and its capacity counts only arcs going from source side to sink side.
A cut divides the nodes into two sets, containing the source and containing the sink.
The capacity of a cut is the sum of the capacities of the arcs directed from to . Arcs from to are not counted.
The cut has capacity ; arc is ignored. Every unit of flow must cross every cut, so any flow has value at most any cut's capacity. The minimum cut has the smallest capacity.
For the same network, what is the capacity of the cut ?
The max-flow min-cut theorem
The value of the maximum flow equals the capacity of the minimum cut.
The maximum flow-minimum cut theorem applies to any network.
- To prove a flow is maximal, find a cut whose capacity equals the flow's value. No flow can exceed that cut.
- To find the maximum flow, find the minimum cut by listing cuts systematically, for example by growing the source set one node at a time.
The arcs of a minimum cut are the bottleneck: they are all saturated in a maximum flow.
- Maximum flowcapacity of the minimum cut
A flow of value 12 is found, and a cut of capacity 12 exists. What do you conclude?
Supersources and supersinks
Join several sources to one supersource and several sinks to one supersink, so the usual methods apply.
Add a supersource , with a directed arc from to each real source, and/or a supersink , with a directed arc from each real sink to .
The capacity of each added arc is the most that source can supply or that sink can absorb. If no limit is given, the arc has unlimited capacity.
Example: factories able to supply 10 and 8 units become arcs (10) and (8); shops able to take 8 and 6 become arcs (8) and (6).
- 1
Add a supersource S
arc from S to each factory, capacity = its supply
- 2
Keep the real network
factories, depots and shops with their arc capacities
- 3
Add a supersink Z
arc from each shop to Z, capacity = what it can take
Two sinks can absorb 5 and 9 units. Describe the arcs you add.
Finding the maximum flow
List every cut, find the smallest capacity, and that is the maximum flow; say what the bottleneck means in context.
In context, if the arcs were pipes in litres per second, the answer says what the whole system can deliver. To interpret a cut, say what it means: all flow must pass through those arcs, so their combined capacity limits the whole network.
Worked example
Find the maximum flow from to by considering cuts.
- 1
: .
- 2
: arcs , , : .
- 3
: arcs , , : .
- 4
: arcs , : .
Why does the capacity of a cut limit the whole flow?
Try an exam question
A network has arcs 8, 5, 2, 4 and 7, all directed away from towards . Find the capacity of each of the four cuts , , and (the set containing ), and state the maximum flow.
[5 marks]
- [1]: .
- [1]: .
- [1]: .
- [1]: .
- [1]The minimum cut is , so by the max-flow min-cut theorem the maximum flow is .
That's the notes covered.
Carry on to the next subtopic.
Try a question
Find the capacity of the cut that separates from .
1 mark, marked against the mark scheme
Find the capacity of the cut that separates from .
1 mark, marked against the mark scheme