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.
WHAT YOU PROBABLY THINK
Once every route from source to sink contains a saturated arc, the flow must be maximal.
Labelling and augmenting
On each arc write two numbers: the spare capacity, as an arrow in the direction of the arc, and the flow already there, 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 after pushing that much, at least one arc becomes saturated. Update both labels on every arc of the path and look for another.
Backwards steps are why the opening claim is wrong. A path can still exist through an arc that is full, by reducing flow elsewhere, so saturation on every direct route does not settle the matter. 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. Since every flow is bounded by every cut, exhibiting a flow and a cut of the same value proves both are optimal at once, and that is what a full answer must do.
Finding the cut is easier than it looks. After 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 saturated, and every arc entering it is empty, so the cut's capacity equals the flow.
Questions may add constraints: 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 rather than by a new method.
YOUR TURN
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.
THE EXAM BIT
- 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.
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
u
n
i
t
s
,
t
h
e
s
m
a
l
l
e
s
t
s
p
a
r
e
c
a
p
a
c
i
t
y
a
l
o
n
g
t
h
e
p
a
t
h
.
T
h
e
a
r
c
w
i
t
h
s
p
a
r
e
c
a
p
a
c
i
t
y
3
b
e
c
o
m
e
s
s
a
t
u
r
a
t
e
d
a
n
d
c
a
n
n
o
t
t
a
k
e
a
n
y
m
o
r
e
.
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.
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.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- 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.
Open the full revision checklist to see every objective in the course in one place.
No animated video for this topic yet; these notes stand alone.