Questions on flows in networks: cuts and capacity

Question 1

A cut crosses arcs of capacity 9 and 6 towards the sink and an arc of capacity 5 back towards the source. Find its capacity and explain the treatment of the third arc.

Accepted Answer

9 + 6 = 15. The arc crossing back towards the source contributes nothing. It carries flow away from the sink, so it can only reduce what gets through, never add to the ceiling the cut imposes. Adding all three capacities to get 20 is the standard error, and it gives a figure that is not the capacity of the cut. B1 for the capacity, B1 for the treatment of the backward arc.

Question 2

Explain why the capacity of any cut is an upper bound for the flow through the network.

Accepted Answer

A cut separates the source from the sink, so every unit of flow arriving at the sink must cross the cut in the forward direction at least once. The forward arcs cannot carry more than their total capacity, so the flow cannot exceed that total. B1 for every unit crossing the cut, B1 for the capacity limit.

Question 3

A cut is described by splitting the vertices of a network into two sets. State what must be true of those two sets, and state which arcs contribute to the cut's capacity.

Accepted Answer

Every vertex goes into exactly one of the two sets, the source lies in one of them and the sink in the other. B1 for both conditions. The capacity counts only the arcs directed from the set holding the source to the set holding the sink, each at its full capacity. B1 for the forward-crossing arcs alone.

Question 4

A network has a source, a sink and four other vertices. Find how many different cuts it has.

Accepted Answer

The source and the sink are fixed on opposite sides, and each of the other four vertices goes to one side or the other independently, so there are 2⁴ = 16 cuts. M1 for two choices per free vertex, A1 for 16.

Question 5

A network has SA 12, SB 9, AC 7, AD 6, BD 8, CT 10, DT 11, all arcs directed away from S and towards T. Find the capacity of the cut round the source, the cut round the sink, and the cut separating {S, A, B, D} from {C, T}.

Accepted Answer

Round the source, the arcs are SA and SB: 12 + 9 = 21.
Round the sink, the arcs are CT and DT: 10 + 11 = 21.
For the third cut the forward arcs are AC and DT: 7 + 11 = 18, with no arc crossing back.
So the flow cannot exceed 18, and neither of the two obvious cuts was the binding one. B1 B1 for the first two cuts, M1 for the forward arcs of the third, A1 for 18, A1 for the bound on the flow.

Question 6

A network has arcs SA 12, SB 9, AC 7, AD 6, BD 8, CT 10 and DT 11, all directed away from S and towards T. Find the capacity of the cut separating {S, B} from {A, C, D, T}, and explain why a cut of capacity 20 tells you less than a cut of capacity 18.

Accepted Answer

The arcs running forward across the cut are SA and BD, giving 12 + 8 = 20, with no arc crossing back.
Every cut is an upper bound, so the flow is at most 20 and also at most 18. The smaller bound is the only one that bites. M1 for the forward arcs SA and BD, A1 for 20, B1 for the smaller bound being the binding one.

Question 7

A different network has two factories and three shops. Describe how to bring it into the standard one-source, one-sink form.

Accepted Answer

Add a supersource joined to each factory by an arc whose capacity is that factory's output, and a supersink reached from each shop by an arc whose capacity is that shop's demand. The network then has a single source and a single sink, and every method for cuts and flows applies without modification. B1 for the supersource and its capacities, B1 for the supersink and its capacities, B1 for the reduction to standard form.

Question 8

A network has vertices S, A, B and T and arcs SA 0 to 11, SB 0 to 9, AB 3 to 5, AT 0 to 8 and BT 0 to 10, the first number of each pair being the arc's lower capacity. Find the value of the cut separating {S, B} from {A, T}.

Accepted Answer

Crossing towards the sink are SA, of upper capacity 11, and BT, of upper capacity 10, contributing 11 + 10 = 21. M1 for the forward arcs at their upper capacities, A1 for 21. Crossing back is AB, running from A on the sink side to B on the source side, and with a floor it no longer contributes nothing: it must carry at least 3 units away from the sink side, so 3 is subtracted. M1 for subtracting the lower capacity of the backward arc. The value is 21 − 3 = 18. A1.

Question 9

Two factories, F with an output of 14 and G with an output of 10, supply two shops, U with a demand of 12 and V with a demand of 9. The routes between them are FP 9, FQ 7, GQ 6, PU 10, QU 5 and QV 8. Bring the network to the standard one-source, one-sink form, and find the capacity of the cut round the source, the cut round the sink and the cut separating the source and the two factories from the rest. Then find a cut whose capacity is smaller than all three, and state the bound on the flow that it gives.

Accepted Answer

Add a supersource S with arcs SF 14 and SG 10, the outputs of the two factories, and a supersink T with arcs UT 12 and VT 9, the demands of the two shops. B1 for both, with the four capacities. Round the source the arcs crossing forward are SF and SG: 14 + 10 = 24. Round the sink they are UT and VT: 12 + 9 = 21. M1 for taking the arcs directed away from the set, A1 for 24 and 21. For the third cut the set is {S, F, G} and the arcs leaving it are FP, FQ and GQ: 9 + 7 + 6 = 22. A1. Now move U across to the source side, leaving the set {S, F, G, P, Q, U}. The arcs PU and QU no longer cross, and the only arcs directed out of the set are QV and UT: 8 + 12 = 20. M1 for a set that keeps U on the source side, A1 for 20 and the flow being at most 20. The bound is attained, by the flow SF 14, SG 6, FP 7, FQ 7, GQ 6, PU 7, QU 5, QV 8, UT 12, VT 8, which balances at every vertex and carries 20, so 20 is the maximum flow and no cut is worth less.

Question 10

A network has source S, sink T and arcs SP 8, SQ 11, PQ 4, PR 6, QR 5, QT 7 and RT 9. A student offers the pair of arcs SP and PR as a cut. Explain why it is not one, and find the capacity of the cut separating {S, P} from {Q, R, T}.

Accepted Answer

Removing a cut has to leave the sink unreachable from the source. Delete SP and PR and the route S, Q, T is untouched, so the source still reaches the sink and those two arcs are not a cut. B1 for the requirement, B1 for a surviving route.
For the cut with source side {S, P}, the arcs directed from that set to {Q, R, T} are SQ, PQ and PR, so the capacity is 11 + 4 + 6 = 21. M1 for the three forward arcs, A1 for 21.

Question 11

A network has source S, sink T and arcs SP 12, SQ 7, PR 6, QP 4, PT 5, QT 9 and RT 8, and carries the flow SP 8, SQ 7, PR 6, QP 3, PT 5, QT 4, RT 6. State the value of the flow. Then show that the flow crossing the cut separating {S, P} from {Q, R, T} towards the sink, less the flow crossing it back, is that same value. Give the capacity of the cut, and state what it and the flow together say about the maximum flow.

Accepted Answer

The flow leaving S is 8 + 7 = 15 and the flow reaching T is 5 + 4 + 6 = 15, so the value is 15. B1.
The arcs running from {S, P} to {Q, R, T} are SQ, PR and PT, carrying 7 + 6 + 5 = 18. M1 for the three forward arcs at their flows.
The only arc running the other way is QP, carrying 3, so the net flow across the cut is 18 − 3 = 15, the value of the flow. A1 for subtracting the backward flow to reach 15.
The capacity of the cut counts the same three forward arcs at their full capacities, 7 + 6 + 5 = 18, and QP contributes nothing. B1 for 18. A flow of 15 exists and no flow can pass 18, so the maximum lies between 15 and 18, so the flow of 15 is not yet shown to be the maximum. B1 for the two-sided statement.

Question 12

A network has arcs SA 12, SB 9, AC 7, AD 6, BD 8, CT 10 and DT 11, all directed away from S and towards T, and vertex D can handle at most 8 units in total. Explain how to model the restriction on D, find the capacity of the cut separating {S, A, B, D} from {C, T}, and by stating a flow of that value prove that it is the maximum.

Accepted Answer

Split D into D-in and D-out. The arcs AD and BD now arrive at D-in, the arc DT now leaves D-out, and a single arc from D-in to D-out carries capacity 8. Every route through D is forced along that arc, which is what the restriction means. Draw the split vertex rather than describing it in words. The cut now crosses AC and the new arc rather than DT, so its capacity is 7 + 8 = 15, and the flow is at most 15. Now exhibit a flow of 15: SA 7, SB 8, AC 7, AD 0, BD 8, CT 7, DT 8. Each arc is within capacity, D carries exactly 8, and flow in equals flow out at every intermediate vertex, so 15 units reach T. A flow of 15 and a cut of 15 pin the answer between the same two numbers, so the maximum flow is 15. M1 A1 for splitting D with an arc of capacity 8, M1 A1 for the cut capacity, M1 A1 for a feasible flow of that value, A1 for the conclusion.

Question 13

In a network whose arcs carry lower capacities as well as upper ones, explain why the value of a cut is the total of the upper capacities crossing forward minus the total of the lower capacities crossing back, and why exhibiting a feasible flow becomes a piece of work in its own right.

Accepted Answer

The flow across a cut is the flow forward less the flow back. Forward arcs can carry at most their upper capacities, exactly as before; but an arc crossing back is now obliged to carry at least its floor, so at least that much is removed from what crosses towards the sink. B1 for the forward-minus-back accounting. The value of the cut is therefore the forward uppers minus the backward floors, and it still bounds every flow the network can carry. B1 for the bound surviving. Without floors, the zero flow is feasible and any flow can be grown from it; with floors, a flow must meet every arc's lower number and still balance at each intermediate vertex, and no flow at all is guaranteed to exist, so producing one is the first piece of the argument rather than a formality. B1 for feasibility no longer being free.

Question 14

A network has source S, sink T and arcs SP 0 to 5, SQ 0 to 9, PQ 6 to 7, PT 0 to 4 and QT 0 to 11, the first number of each pair being the arc's lower capacity. Show that the network carries no feasible flow at all. Find the least upper capacity on SP for which one exists, and with SP at that value find the value of the cut separating {S, Q} from {P, T}.

Accepted Answer

SP is the only arc into P, so P can take in at most 5. PQ is the only arc out of P that has to carry anything, and its floor is 6, so P has to send out at least 6. B1 for the two totals at P. No assignment of flows can balance 5 in against 6 out, so no feasible flow exists. A1 for the conclusion.
Raising SP's upper capacity to 6 is enough and nothing smaller will do, since P still has to send at least 6. With SP at 6 the flow SP 6, SQ 5, PQ 6, PT 0, QT 11 meets every floor, sits inside every ceiling and balances at P, with 6 in and 6 out, and at Q, with 5 + 6 in and 11 out. B1 for 6 with a feasible flow exhibited.
For the cut with source side {S, Q}, the arcs crossing towards the sink are SP, of upper capacity 6, and QT, of upper capacity 11, giving 6 + 11 = 17. The arc crossing back is PQ, which runs from P on the sink side to Q on the source side and has to carry its floor of 6, so 6 is subtracted. M1 for the forward uppers, A1 for subtracting the floor. The value of the cut is 17 − 6 = 11. A1.
The flow above has value 6 + 5 = 11 as well, so the bound is attained and 11 is the maximum. PT is left empty throughout: everything P receives is committed to PQ's floor before PT is considered at all.

Question 15

In a network every route from the source to the sink passes through one of three depots P, Q and R, which can handle at most 6, 5 and 4 units respectively. Show that the flow through the network cannot exceed 15.

Accepted Answer

Split each depot into two vertices, an in-vertex collecting everything that arrives and an out-vertex issuing everything that leaves, joined by a single arc whose capacity is that depot's limit: 6, 5 and 4. Every route through a depot is forced along its own arc. M1 for the three splitting arcs with their capacities.
Delete those three arcs. Every route from the source to the sink used a depot, so every route is broken and the sink is unreachable. B1 for the deletion separating the source from the sink.
Now take the source side of a cut to be the vertices still reachable from the source once the three arcs are deleted. Any arc leaving that set must be one of the three, since otherwise its head would have been reachable too. M1 for the cut built from what remains reachable, A1 for its forward arcs being among the three.
The capacity of that cut is therefore at most 6 + 5 + 4 = 15, and every flow is bounded by every cut, so the flow cannot exceed 15. A1.

Question 16

The network shows a system of pipes, each arc directed and labelled with its capacity in litres per second, with source S and sink T. Find the capacity of the cut that separates {S, B, D} from {A, C, T}, explaining how you have treated every arc that crosses it. Find also the capacity of the cut round the sink. Then find a cut of smaller capacity than either of those, and state what your smallest cut shows about the maximum flow from S to T.

Accepted Answer

For the cut separating {S, B, D} from {A, C, T}, look at every arc with one end in each set. Running from the source side to the sink side are SA 14, BA 4 and DT 10. M1 for picking out the arcs that cross forwards.
Its capacity is 14 + 4 + 10 = 28. A1 for the capacity 28.
Two arcs cross the other way, AD 5 and CD 3, from the sink side back to the source side. They contribute nothing: they carry flow away from the sink, so they can only reduce what gets through, never raise the ceiling. Adding them in to get 36 double-counts what the cut lets through. B1 for the treatment of the backward arcs.
The cut round the sink separates {S, A, B, C, D} from {T}, and only CT and DT cross it, giving 12 + 10 = 22. B1 for the capacity of the cut round the sink.
Now move D across to the source side, taking the cut separating {S, A, B, D} from {C, T}. The arcs crossing forwards are AC 9 and DT 10, giving a capacity of 9 + 10 = 19; CD 3 crosses back and so contributes nothing. M1 for a cut that puts D with the source, A1 for 19.
Every cut is an upper bound for the flow, because every unit reaching T must cross it in the forward direction, so the maximum flow is at most 19 litres per second. B1 for the bound the cut puts on the flow.
The bound of 19 is the tightest of the three, and moving one vertex across the cut was what found it: SA at 14 looked generous, but of what reaches A only AC's 9 crosses this cut; the rest goes to D and leaves through DT.