Practise › Questions › Flows in networks: cuts and capacity
Flows in networks: cuts and capacity questions
Every way of separating the source from the sink puts a ceiling on the flow. Finding the tightest of those ceilings is half of proving a flow cannot be beaten.
6 original questions · 22 marks · the flows in networks: cuts and capacity 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.
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.
Worked 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 produces a bound that is not even valid. B1 for the capacity, B1 for the treatment of the backward arc.Explain why the capacity of any cut is an upper bound for the flow through the network.
Worked 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.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}.
Worked 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.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.
Worked 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. Quoting the first cut you happen to draw, rather than hunting for the smallest, is what costs the final accuracy mark.A different network has two factories and three shops. Describe how to bring it into the standard one-source, one-sink form.
Worked 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.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.
Worked 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; the method mark is for the diagram, not for a sentence about it.
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. A bound alone never finishes the argument; the marks for proving maximality are for the matching flow. 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.
The same practice on paper: the printable workbook for this topic, questions and a worked answer book.
Practise flows in networks: cuts and capacity 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.