Questions on maximum flow and the labelling procedure

Question 1

Explain what the two numbers written on each arc during the labelling procedure represent.

Accepted 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.

Question 2

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.

Accepted 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.

Question 3

At one intermediate vertex of a network the arcs arriving carry 5, 7 and 2 units and the arcs leaving carry 9 and 4 units. State whether the flow conserves at this vertex, and give the discrepancy.

Accepted Answer

Flow conservation asks that the total arriving equals the total leaving. Here 5 + 7 + 2 = 14 arrives and 9 + 4 = 13 leaves, so the flow does not conserve at this vertex. B1 for comparing the two totals. The discrepancy is 14 − 13 = 1 unit. B1 for 1 with the direction, more arriving than leaving.

Question 4

An arc has lower capacity 3 and upper capacity 8, and at present carries 5 units. State the two labels the labelling procedure writes on this arc, and say what each of them means.

Accepted Answer

The forward label is the upper capacity less the flow, 8 − 5 = 3: that is how much more can be pushed along the arc. B1 for 3 forwards with its meaning. The backward label is the flow less the lower capacity, 5 − 3 = 2: only flow above the floor is available to be given back, since the arc has to keep carrying at least 3. B1 for 2 backwards with its meaning.

Question 5

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.

Accepted 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.

Question 6

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.

Accepted 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.

Question 7

A student argues that once every route from source to sink contains a saturated arc, the flow must be maximal. Explain the error.

Accepted 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.

Question 8

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.

Accepted Answer

Begin with 4 units already on BD, so that arc opens with spare capacity 8 − 4 = 4 and potential backflow 4 − 4 = 0, so no augmenting path can take the flow on BD 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.

Question 9

A network has source S, sink T and arcs SP 10, SQ 8, PQ 5, PT 9 and QT 12. A student proposes the flow SP 10, SQ 6, PQ 4, PT 5, QT 10. Check this flow at each intermediate vertex and at the two ends, state what is wrong with it, and give one way of correcting it.

Accepted Answer

Every arc is inside its capacity, so the fault is not there.
At Q, 6 + 4 = 10 arrives and 10 leaves, so Q balances. At P, 10 arrives while 4 + 5 = 9 leaves, so P does not balance and one unit is unaccounted for. M1 for comparing flow in with flow out at both vertices, A1 for P with 10 in against 9 out.
The same unit shows at the ends: 10 + 6 = 16 leaves S while 5 + 10 = 15 reaches T, and for any legal flow those two agree. B1 for the two end totals disagreeing.
Either reduce SP to 9, leaving a legal flow of value 15, or raise PT to 6, which is inside PT's capacity of 9 and leaves a legal flow of value 16. B1 for a correction that restores the balance at P.

Question 10

Two factories F and G supply a single depot T. F can despatch at most 9 units and G at most 6. The routes and their capacities are FP 7, FQ 4, GQ 6, PT 8 and QT 5. Bring the network to standard form, find the maximum flow, and prove that it is maximal.

Accepted Answer

Add a supersource S joined to each factory by an arc carrying that factory's output: SF of capacity 9 and SG of capacity 6. The network then has one source and one sink and every method applies unchanged. B1 for the supersource with those two capacities. Augment from zero. S-F-P-T has spare capacities 9, 7 and 8, so push 7, saturating FP. S-F-Q-T then has 2, 4 and 5 left, so push 2, which uses up SF. S-G-Q-T has 6, 6 and 3 left, so push 3, saturating QT. Total flow = 7 + 2 + 3 = 12. M1 for a flow-augmenting path with the flow it carries, A1 for the three paths, A1 for 12. The arcs then carry SF 9, SG 3, FP 7, FQ 2, GQ 3, PT 7, QT 5, and each of F, G, P and Q takes in exactly what it sends out. For maximality take the source side to be {S, F, G, Q}, everything still reachable from S: SG has spare capacity so G is reachable, GQ has spare capacity so Q is, and F is reached from Q by a backward step along FQ, which carries 2. The arcs from that set to {P, T} are FP and QT, of capacities 7 and 5, so the cut has capacity 12. Flow and cut agree, so by the max-flow min-cut theorem the flow is maximal. M1 for a cut, A1 for its capacity 12 with the theorem named. PT is left with a spare unit, and there is no need to fill it: what limits the depot is FP together with QT, not the last stretch into T.

Question 11

A network has a single source S and a single sink T, no arc enters S and no arc leaves T. Show that for any flow the total leaving S equals the total entering T.

Accepted Answer

Take each vertex in turn and form (flow out) − (flow in). Adding that quantity over every vertex counts each arc twice, once with a plus at its tail and once with a minus at its head, so the whole sum is zero. M1 for summing out minus in over every vertex and seeing each arc cancel.
At every intermediate vertex flow conservation makes out minus in zero, so only the two ends survive: (out of S) − (into S) + (out of T) − (into T) = 0. A1 for the intermediate terms vanishing.
Nothing enters S and nothing leaves T, so this reads (out of S) − (into T) = 0: the total leaving S equals the total entering T. B1 for the conclusion.

Question 12

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.

Accepted 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.

Question 13

A network has source S, sink T and arcs SP 0 to 9, SQ 0 to 7, PQ 3 to 5, PT 0 to 6 and QT 0 to 8, the first number of each pair being the arc's lower capacity. Explain why the labelling procedure cannot start from the zero flow, establish a feasible flow, augment it as far as it will go, and prove that the flow you reach is maximal.

Accepted Answer

The zero flow breaks PQ's floor of 3, so it is not feasible and there is nothing to label. B1 for the floor ruling the zero flow out.
Build a feasible flow first. Send 3 along S, P, Q, T: that meets PQ's floor, balances at P and at Q, and is inside every upper capacity, giving SP 3, PQ 3, QT 3, a flow of value 3. M1 for carrying the floor's requirement the whole way from S to T, A1 for a feasible flow.
Now augment. S, P, T has forward labels 9 − 3 = 6 and 6, so push 6: SP becomes 9 and PT 6, both full. S, Q, T has 7 and 8 − 3 = 5, so push 5: SQ becomes 5 and QT 8, which fills it. The flow is SP 9, SQ 5, PQ 3, PT 6, QT 8, of value 14, with P taking in 9 and sending out 3 + 6 and Q taking in 5 + 3 and sending out 8. M1 for the two augmenting paths, A1 for 14 with conservation checked.
Nothing further is available: SQ still has spare capacity 2, so Q can be reached, but QT is full and PQ's backward label is 3 − 3 = 0, so no flow can be taken off it. Take the source side to be {S, Q}. Crossing towards the sink are SP, of upper capacity 9, and QT, of upper capacity 8; crossing back is PQ, which has to carry its floor of 3. The cut is worth 9 + 8 − 3 = 14, matching the flow, so by the max-flow min-cut theorem the flow is maximal. A1 for the cut valued with the floor subtracted and the conclusion.

Question 14

A network has source S, sink T and arcs SP 9, SQ 6, PR 5, PQ 4, QT 7 and RT 8. Its maximum flow is 12 and its minimum cut separates {S, P, Q} from {R, T}. One arc, chosen by the operator, may have its capacity increased by any amount. Find the greatest maximum flow that can then be achieved, name every arc whose increase achieves it, and explain why increasing any other arc achieves nothing.

Accepted Answer

That cut crosses PR and QT, of capacities 5 and 7, so its capacity is 5 + 7 = 12. Enlarging an arc that is not one of those two leaves the cut at 12, and every flow is bounded by every cut, so the maximum stays at 12. B1 for the two arcs the cut crosses and why enlarging the others changes nothing.
Raise PR to 5 + k and that cut becomes 12 + k, but the cut round the source is untouched at 9 + 6 = 15, so no flow can pass 15 however large k is. M1 for the second cut as the new ceiling.
PR at 8 reaches it: SP 9, SQ 6, PR 8, PQ 1, QT 7, RT 8 is inside every capacity and balances at P, at Q and at R, so the flow is 15. A1 for 15 with a flow that attains it. QT at 10 does the same, with SP 9, SQ 6, PR 5, PQ 4, QT 10, RT 5. A1 for both arcs named.
So the greatest attainable maximum is 15, reached by raising PR to at least 8 or QT to at least 10, and any increase beyond those two figures is idle because the source can release only 15. B1 for the conclusion with the two amounts.

Question 15

The labelling procedure has stopped, and X is the set of vertices that can still be reached from the source S by an augmenting step, forwards along an arc with spare capacity or backwards along an arc carrying flow. The sink T is not in X. Show that every arc from X to the remaining vertices is saturated and every arc from them into X is empty, and deduce that the value of the flow equals the capacity of the cut that X defines.

Accepted Answer

Let Y be the vertices outside X. Then S is in X and T is in Y, so X and Y define a cut.
Take an arc running from a vertex of X to a vertex of Y. If it had any spare capacity its head could be reached from S by one more forward step and would lie in X, so it has none: every such arc is saturated. B1.
Take an arc running from a vertex of Y to a vertex of X. If it carried any flow its tail could be reached by one backward step and would lie in X, so it carries none: every such arc is empty. B1.
The value of a flow is the flow forward across the cut less the flow back across it, because each unit delivered to T crosses from X to Y once more than it crosses back. M1 A1 for the value as forward less backward.
The forward arcs are all full, so they contribute the total of their capacities, and the backward arcs are all empty, so they take nothing away. The value of the flow is therefore exactly the capacity of this cut. A1.
Every flow is bounded by every cut, so a flow and a cut of equal value are both optimal at once, and the set the procedure stops on hands over the minimum cut with no search for it.