Maths › Decision Mathematics 2 › Maximum flow and the labelling procedure
Maximum flow and the labelling procedure
Push flow along any route with room to spare, then look again. When no route is left the flow is maximal, and a cut of the same capacity proves it beyond argument.
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.
COMMON MISCONCEPTION
Once every route from source to sink contains a saturated arc, the flow must be maximal.
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. Keeping both is what makes the procedure reliable.
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 arc is saturated. Update both labels on every arc of the path, then look for another.
Those backwards steps matter. A path can still run through 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, whose outlet DT is 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.
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.
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.
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 that arc?
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.
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.
Open the full revision checklist to see every objective in the course in one place.