Maths › Decision Mathematics 2 › Maximum flow and the labelling procedure
Maximum flow and the labelling procedure
The labelling procedure increases a flow by finding routes with spare capacity, repeating until none remain. A cut whose capacity equals the final flow then proves that the flow is maximal.
Builds on Flows in networks: cuts and capacity and Shortest paths: Dijkstra and Floyd.
IN THIS TOPIC
- Use the labelling procedure with excess and potential-backflow arrows.
- Find flow-augmenting paths and state the extra flow each carries.
- Prove a flow is maximal by exhibiting a cut of the same capacity.
- Check flow conservation at every intermediate vertex.
- Establish a feasible flow and augment it when arcs carry lower capacities as well as upper ones.
COMMON MISCONCEPTION
Once every route from source to sink contains a saturated arc, the flow must be maximal.
A flow-augmenting path may use an arc backwards, reducing the flow already on it, so a saturated arc on every direct route settles nothing. What proves maximality is the absence of any augmenting path, and the way to show that is a cut whose capacity equals the flow: by the max-flow min-cut theorem the two match exactly when both are optimal.
Labelling and augmenting
Write two numbers on each arc. The spare capacity goes as an arrow in the direction of the arc, and the flow already there goes as an arrow against it. The first says how much more can be pushed forward; the second says how much could be taken back.
A flow-augmenting path runs from source to sink using arcs with spare capacity forwards, or existing flow backwards. The extra flow it carries is the smallest of those numbers along it, and once you have pushed that much at least one forward arc is saturated or one backward arc emptied. Update both labels on every arc of the path, then look for another.
Those backwards steps matter. A path can still get past an arc that is full, by reducing flow somewhere else, so saturation on every direct route settles nothing. Only the absence of any augmenting path does.
WORKED EXAMPLE
Building a maximum flow
For the network SA 10, SB 8, AC 6, AD 5, BD 7, CT 9, DT 10, find the maximum flow.
S-A-C-T has spare capacities 10, 6, 9, so push 6 and saturate AC.
S-A-D-T has 4, 5, 10 left, so push 4. S-B-D-T has 8, 7, 6 left, so push 6.
Total flow = 6 + 4 + 6 = 16, with SA carrying 10, SB 6 and DT 10.
No augmenting path remains: from S only B has spare capacity, and from B only D, and from D only A, by taking flow back along AD; the arcs leaving {S, A, B, D}, AC and DT, are both full.
Proving it is maximal
The max-flow min-cut theorem says the maximum flow equals the capacity of the minimum cut. Every flow is bounded by every cut, so producing a flow and a cut of the same value proves both are optimal at once. A full answer has to do exactly that.
Finding the cut is easier than it looks. Once the procedure stops, take the source side to be every vertex still reachable from the source by an augmenting step. Every arc leaving that set is then saturated and every arc entering it is empty, so the cut's capacity equals the flow.
Questions sometimes add constraints, such as a minimum flow along certain arcs or a required flow rate to be achieved as cheaply as possible. Those are handled by adjusting the labels, not by a new method, and the last section runs the first of them through in full.
GUIDED PRACTICE
The proof
Prove that the flow of 16 found above is maximal.
Show the working
Take the source side to be {S, A, B, D}, which is everything still reachable from S.
The arcs from that set to {C, T} are AC and DT, of capacities 6 and 10.
That cut has capacity 16, and both its arcs are carrying their full capacity.
A flow of 16 and a cut of 16 match, so by the max-flow min-cut theorem the flow is maximal and the cut is minimal.
When the arcs have floors
An arc with a lower capacity has to carry something whether the flow wants it there or not, and two things follow. The starting flow of zero is no longer available, since zero breaks any floor, and the two labels mean slightly different things.
So build a feasible flow first. Send enough round each arc with a floor to meet it, carrying that flow all the way from the source to the sink so that each intermediate vertex still balances, and check the arcs it passes along against their ceilings on the way. Then label as before with one change: the forward label on an arc is its upper capacity less the flow, as ever, while the backward label is the flow less the lower capacity, because only flow above the floor is available to be given back.
The proof of maximality works as it did, with the cut valued by the rule for a cut: upper capacities forward, minus the floors of the arcs crossing back.
WORKED EXAMPLE
Augmenting with a floor in place
Take the network with SA 0 to 10, SB 0 to 8, AB 2 to 6, AT 0 to 7 and BT 0 to 9. Find the maximum flow.
A feasible flow first. Push 2 along S, A, B, T, which meets AB's floor and balances at A and B, giving SA 2, AB 2 and BT 2.
Now augment. S, A, T has forward labels 8 and 7, so push 7: SA becomes 9 and AT 7, which saturates AT.
S, B, T has forward labels 8 and 7, so push 7: SB becomes 7 and BT 9, which saturates BT.
Nothing is left. Both arcs into T are full, and AB's backward label is 2 − 2 = 0, so no flow can be taken off it either.
The flow is 16, and the cut separating {S, A, B} from {T} is worth 7 + 9 = 16 with nothing crossing back, so 16 is the maximum.
GUIDED PRACTICE
A floor that costs you flow
In the same network, raise AB's lower capacity to 6, its whole capacity, so the arc has to run full. Find the maximum flow and prove it with a cut.
Show the working
AB now carries 6 whatever else happens, and A has no other supply, so 6 of SA's 10 units are committed before AT sees any and AT is left with at most 4.
B passes on those 6, and BT's ceiling of 9 leaves room for only 3 of whatever SB brings.
So the flow into T is at most 4 + 9 = 13, and SA 10, SB 3, AB 6, AT 4, BT 9 achieves it while balancing at A and B.
For the proof, cut {S, B} from {A, T}: forward SA 10 and BT 9, and AB crosses back with a floor of 6, so the value is 10 + 9 − 6 = 13.
Flow 13 and cut 13, so the flow is maximal. The floor has cost three units against the 16 above, which is the point of carrying the subtraction through the cut rule rather than ignoring arcs that cross back.
ASSESSMENT FOCUS
- Label both directions on every arc and update both after each augmenting path.
- List each flow-augmenting path with the extra flow it carries.
- Always finish by naming a cut of the same capacity as your flow, and say the theorem's name.
- Check flow conservation at every intermediate vertex before claiming a total.
- Do not forget backwards steps. A path may reduce the flow on one arc in order to increase the total.
- With floors on the arcs, start from a feasible flow rather than from zero, and say how you built it.
- With floors on the arcs, the backward label is the flow less the lower capacity, so a full floor leaves nothing to give back.
CHECK YOURSELF
A flow-augmenting path has spare capacities 7, 3 and 9 along it. How much extra flow can it carry, and what happens to the arc that limits it?
Show a hint
The bottleneck decides.
Show the answer
3 units, the smallest spare capacity along the path. The arc with spare capacity 3 becomes saturated and cannot take any more.
Label spare capacity forwards and existing flow backwards; an augmenting path carries the smallest of those numbers along it.
The maximum flow equals the minimum cut, so a flow is proved maximal by exhibiting a cut of the same capacity.
The minimum cut separates the vertices still reachable from the source from those that are not.
Where arcs carry floors, start from a feasible flow and label backwards with the flow less the lower capacity.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the maximum flow and the labelling procedure questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Use the labelling procedure with excess and potential-backflow arrows.
- Find flow-augmenting paths and state the extra flow each carries.
- Prove a flow is maximal by exhibiting a cut of the same capacity.
- Check flow conservation at every intermediate vertex.
- Establish a feasible flow and augment it when arcs carry lower capacities as well as upper ones.
Open the full revision checklist to see every objective in the course in one place.