Practise › Questions › Maximum flow and the labelling procedure
Maximum flow and the labelling procedure questions
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.
7 original questions · 26 marks · the maximum flow and the labelling procedure notes · Decision Mathematics 2
Every question here is written for this library rather than taken from a past paper. Write your answer out before opening the worked one: the answers award marks point by point, and the marks are easier to see when you have something of your own to compare against.
Explain what the two numbers written on each arc during the labelling procedure represent.
Worked answer
One is the spare capacity, written as an arrow in the direction of the arc: how much more can be pushed forward. The other is the flow already there, written as an arrow against the arc: how much could be taken back. B1 B1 for the two labels. Both are needed, because an augmenting path may reduce the flow on an arc as well as increase it.A flow-augmenting path has spare capacities 9, 4 and 6 along it. State the extra flow it carries and what happens to one of its arcs.
Worked answer
It carries 4 units, the smallest spare capacity along the path. The arc that had spare capacity 4 becomes saturated, so no later path can use it in the forward direction. B1 for 4 units, B1 for the arc becoming saturated.A network has arcs SA 12, SB 9, AC 7, AD 6, BD 8, CT 10 and DT 11, with S the source and T the sink. Starting from zero flow, find the maximum flow, listing each flow-augmenting path with the flow it carries.
Worked answer
S-A-C-T has spare capacities 12, 7 and 10, so push 7 and saturate AC.
S-A-D-T now has 5, 6 and 11 available, so push 5, which uses up SA.
S-B-D-T has 9, 8 and 6 left, so push 6, saturating DT.
Total flow = 7 + 5 + 6 = 18. M1 for a flow-augmenting path with its flow, A1 for 7, A1 for 5, A1 for 6, A1 for the total 18, B1 for showing no augmenting path remains. The arcs then carry SA 12, SB 6, AC 7, AD 5, BD 6, CT 7, DT 11.
Check conservation before stopping: A takes in 12 and sends out 7 + 5, B takes in 6 and sends out 6, C takes 7 and sends 7, D takes 5 + 6 and sends 11.
No augmenting path remains. From S only SB has spare capacity, from B only BD, and D's only outlet DT is full.In a network with source S and sink T, the arcs SA 12, SB 9, AC 7, AD 6, BD 8, CT 10 and DT 11 carry a flow of 18, made up of SA 12, SB 6, AC 7, AD 5, BD 6, CT 7 and DT 11. Prove that this flow is maximal, naming the theorem you use.
Worked answer
Take the source side to be {S, A, B, D}, everything still reachable from S by an augmenting step. The arcs from that set to {C, T} are AC and DT, of capacities 7 and 11, so the cut has capacity 18. Both are carrying their full capacity, and BD, which runs inside the source side, is not counted.
A flow of 18 and a cut of 18 agree, so by the max-flow min-cut theorem the flow is maximal and this cut is minimal. M1 for choosing a cut, A1 for naming AC and DT, A1 for the capacity 18, B1 for quoting max-flow min-cut. State the arcs the cut crosses; a bare number identifies no cut.A student argues that once every route from source to sink contains a saturated arc, the flow must be maximal. Explain the error.
Worked answer
An augmenting path may run backwards along an arc that already carries flow, reducing it there so that more can travel by another route. A path can therefore still exist even when every direct route is blocked by a full arc. Only the absence of any flow-augmenting path, forwards or backwards, settles the matter, and a cut of matching capacity is what proves it. B1 for the backward step, B1 for the correct stopping condition.A network with source S and sink T has arcs SA 12, SB 9, AC 7, AD 6, BD 8, CT 10 and DT 11, and its maximum flow is 18. A new rule requires at least 4 units to travel along BD. State how the labelling procedure is started and whether 18 is still attainable.
Worked answer
Begin with 4 units already on BD, so that arc opens with spare capacity 8 − 4 = 4 and potential backflow 4, and no augmenting path is ever allowed to take the backflow below the required minimum.
The maximum is still 18. Every flow of 18 must send 7 along CT and 11 along DT, and since AD carries at most 6, BD must carry at least 11 − 6 = 5. The minimum of 4 was already being met, so it costs nothing. B1 for starting with 4 units on BD, M1 for showing BD must carry at least 5, A1 for 18 being attainable.A network has source S, sink T and arcs SA 6, SB 5, AB 3, AT 4 and BT 6. A student finds the flow SA 6, SB 3, AB 3, AT 3, BT 6, of value 9, and claims it is maximal because every route from S to T contains a saturated arc. Find a flow-augmenting path, state the flow it carries, give the maximum flow, and prove it is maximal.
Worked answer
The student's observation is correct as far as it goes. S-A-T is blocked by SA, S-A-B-T by SA, and S-B-T by BT. No forward path survives.
Now allow a backward step. On the path S-B-A-T the labels are: SB has spare capacity 5 − 3 = 2; AB is traversed against its direction, so the label to use is the flow on it, 3; AT has spare capacity 4 − 3 = 1. The path therefore carries 1 unit, limited by AT.
Update: SB rises to 4, AB falls to 2, AT rises to 4. The flow is now SA 6, SB 4, AB 2, AT 4, BT 6, of value 10. Conservation holds at A (6 in, 2 + 4 out) and at B (4 + 2 in, 6 out).
To prove 10 is maximal, take the cut with source side {S, A, B}. It crosses AT and BT only, of capacities 4 and 6, giving 10. Flow and cut agree, so by the max-flow min-cut theorem the flow is maximal.
M1 for finding a path with a backward step, A1 for the three labels, A1 for 1 unit, A1 for the new flow of 10, M1 for choosing a cut, A1 for the cut capacity 10, B1 for quoting max-flow min-cut.
The unit sent backwards along AB did not vanish. It was rerouted: B now draws that unit from S instead of from A, which frees A to send it straight to T.
The same practice on paper: the printable workbook for this topic, questions and a worked answer book.
Practise maximum flow and the labelling procedure one question at a time
The player marks nothing for you. It shows one question, waits, then shows the worked answer so you can mark yourself, and brings a question back sooner when it went badly.