Cuts, labelling procedure and max-flow min-cut
Studying this course? Keep your progress in one place.
Key facts
- A feasible flow keeps and has flow in flow out at every vertex except S and T.
- The capacity of a cut counts only arcs directed from (with S) to (with T).
- The labelling procedure finds a route with spare capacity and increases the flow by the smallest label on it.
- When T cannot be labelled, the flow is maximum.
- Max-flow min-cut: the maximum flow equals the capacity of the minimum cut.
Networks and flows
A flow sends material from the source S to the sink T along directed arcs, within each arc's capacity and conserving flow at every other vertex.
A network of directed arcs has a source S, where flow starts, and a sink T, where it ends. Each arc has a capacity, the greatest flow it can carry.
A feasible flow obeys two rules: on every arc , and at every other vertex flow in = flow out.
The value of a flow is the amount leaving S, which equals the amount entering T. An arc is saturated when its flow equals its capacity.
At vertex A, flow in is 5 along one arc. Flow out goes along two arcs, one carrying 2. How much does the other carry?
Cuts and their capacity
A cut splits the vertices into (with S) and (with T). Its capacity is the total capacity of arcs from to .
A cut divides the vertices into two sets, containing the source S and containing the sink T.
The capacity of the cut is the sum of the capacities of the arcs directed from to . Arcs from to are not counted.
Every flow is at most the capacity of every cut, because all the flow must cross from to . So the value of a flow is at most the minimum cut.
- Capacity of a cutarcs from to only
Worked example
In the network above, find the capacity of the cuts , and , .
- 1
First cut: the arcs from to are SB, AB and AT: .
- 2
Second cut: the arcs from to are AT and BT: .
A cut has . Which arcs count?
The labelling procedure
Label vertices reachable from S using spare capacity forwards or flow that can be reduced backwards. If T is labelled, augment along the route.
The labelling procedure finds a flow-augmenting route from S to T and the amount to increase the flow by.
Each arc carries two numbers. The one in the arc's direction is the amount the flow can be increased (capacity minus flow). The one in the opposite direction is the amount it can be reduced (the current flow).
From S, label vertices reachable by a forward arc with spare capacity or a backward arc with flow. If T is labelled, trace back a route and increase the flow by the smallest number on it. Repeat until T cannot be labelled.
- 1
Label from S
forward arcs with spare capacity, backward arcs with flow
- 2
Is T labelled?
if not, the flow is maximum
- 3
Trace the route
back from T to S
- 4
Find the increase
the smallest label on the route
- 5
Update the flow
add on forward arcs, subtract on backward arcs
A route has spare capacities 4, 2 and 7. By how much can the flow increase?
A worked example
Augment along routes with spare capacity until T cannot be reached, then find a cut equal to the flow.
Arcs have capacities SA 9, SB 7, AB 4, AC 5, BC 6, BT 4, CT 8. The current flow is SA 5, SB 3, AB 2, AC 3, BC 3, BT 2, CT 6, with value 8.
Find the maximum flow, then prove it is maximum.
Increase the flow by the smallest label on the route, never the largest: the tightest arc limits the route.
Worked example
Increase the flow of value 8 to the maximum and prove it is maximum.
- 1
Route S, A, C, T: spare capacities 4 (SA), 2 (AC) and 2 (CT). Increase by 2 to 10.
- 2
Route S, B, T: spare capacity 4 on SB and 2 on BT. Increase by 2 to 12.
- 3
BT and CT are now both saturated, so every route to T is blocked.
- 4
Take the cut , . Its capacity is .
After the second augmentation, why is the flow of 12 maximum?
Max-flow min-cut
The maximum value of a flow equals the capacity of the minimum cut.
Max-flow min-cut theorem: the maximum value of a flow in a network equals the capacity of the minimum cut.
To prove a flow is maximum, find a cut whose capacity equals the value of the flow. No flow can exceed any cut, so the flow cannot be larger and the cut is a minimum cut. The cut's arcs from to are all saturated, and arcs from to carry no flow.
Increasing the capacity of an arc not in the minimum cut does not raise the maximum flow.
- Maximum flowcapacity of the minimum cut
A flow has value 15 and a cut has capacity 15. What can you conclude?
Try an exam question
A network has arcs SA (capacity 6), SB (4), AB (2), AT (3) and BT (5), all directed as written. (a) Find a feasible flow of value 8. (b) Use a cut to prove that 8 is the maximum flow.
[4 marks]
- [1]A feasible flow of value 8, for example SA 4, SB 4, AB 1, AT 3, BT 5.
- [1]Flow in equals flow out at A () and at B ().
- [1]The cut , has capacity .
- [1]The flow equals the cut capacity, so by max-flow min-cut the maximum flow is 8.
That's the notes covered.
Carry on to the next subtopic.
Try a question
What is the capacity of the cut that separates from ?
1 mark, marked against the mark scheme
What is the capacity of the cut that separates from ?
1 mark, marked against the mark scheme