Edexcel A-Level Further Maths
Cuts, labelling procedure and max-flow min-cut
Total 27 marks
Name
Class
Date
- 1A network has source S, sink T and intermediate vertices A and B. The directed arcs and their capacities are: SA 7, SB 5, AB 3, AT 4 and BT 6 (for example, arc SA goes from S to A and has capacity 7).(a)What is the capacity of the cut that separates from ?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: D(b)A flow has SA 5, SB 3, AB 1, AT 4 and BT 4. What is the value of this flow?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: C(c)A flow of value is found: SA 7, SB 3, AB 3, AT 4 and BT 6. Use a cut to prove that this flow is a maximum flow.[2 marks]Show the mark scheme
Mark scheme
B1: cut , with capacity AT BT
B1: the flow value equals the capacity of this cut, so by the max-flow min-cut theorem the flow is maximum
Do not accept: a cut with capacity greater thanTotal for question 1: 4 marks
- 2A network has source S, sink T and intermediate vertices A, B and C. The directed arcs and their capacities are: SA 9, SB 7, AB 4, AC 5, BC 6, BT 4 and CT 8. A flow is already in the network: SA 5, SB 3, AB 2, AC 3, BC 3, BT 2 and CT 6, so the flow value is 8.(a)By how much can the flow along arc AC be increased?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: B(b)In the labelling procedure, which pair of labels is written on arc SB?[1 mark]- A in the direction S to B and in the direction B to S
- B in the direction S to B and in the direction B to S
- C in the direction S to B and in the direction B to S
- D in the direction S to B and in the direction B to S
Show the mark scheme
Mark scheme
Answer: A(c)Find the amount by which the flow can be increased along the route S, A, C, T, and state the new flow value.[2 marks]Show the mark scheme
Mark scheme
B1: spare capacities SA , AC , CT , so the flow increases by
B1: new flow value
Accept: labels , , shown on the routeTotal for question 2: 4 marks
- 3A network has source S, sink T and intermediate vertices A, B, C and D. The directed arcs and their capacities are: SA 10, SB 8, AC 7, BA 3, BD 6, CT 9, DC 4 and DT 5.(a)Find the capacity of the cut that separates from , and of the cut that separates from . What do these tell you about the maximum flow?[3 marks]
Show the mark scheme
Mark scheme
B1: first cut: arcs SB and CT from to , capacity (BA and DC are directed from to and are not counted)
B1: second cut: arcs AC and BD, capacity
B1: the maximum flow is at most
Do not accept: counting arcs directed from to(b)A flow has SA 7, SB 5, AC 7, BD 5, CT 7 and DT 5, and zero flow on BA and DC. Use the labelling procedure to find a flow-augmenting route, increase the flow, and prove that the new flow is a maximum.[4 marks]Show the mark scheme
Mark scheme
M1: labelling gives a route S, B, D, C, T using spare capacities SB , BD , DC (forward), CT
A1: flow increased by , so the new flow value is
M1: the flow value equals the capacity of the cut , found in (a)
R1: so by the max-flow min-cut theorem the flow is maximum
Accept: another route that reaches the same totalTotal for question 3: 7 marks
- 4A network has source S, sink T and intermediate vertices A, B, C and D. The directed arcs and their capacities are: SA 9, SB 8, AB 3, AD 3, BC 4, BD 3, BT 8, CT 11 and DT 5. A flow of value 3 is already in the network, with a flow of 3 along each of SA, AB, BD and DT, and zero flow elsewhere.(a)Use the labelling procedure to find the maximum flow, stating each flow-augmenting route and the amount by which the flow increases.[6 marks]
Show the mark scheme
Mark scheme
M1: a valid first route using forward spare capacity only, for example S, B, T
A1: correct amount, for example (flow now )
M1: a second valid route, for example S, A, D, T
M1: a route using the backward label on BD, that is reducing the flow in BD, for example S, A, D, B, C, T
A1: its amount (after the routes above)
A1: maximum flow
Accept: any valid order of routes, if a route uses the backward arc DB and the total is(b)(i) Prove that the flow in (a) is a maximum flow. (ii) The owner can pay to increase the capacity of either CT from to , or SB from to . Evaluate which, if either, is worth doing.[6 marks]Show the mark scheme
Mark scheme
M1: (i) cut , using arcs SB, AB, AD
A1: capacity , equal to the flow, so the flow is maximum (max-flow min-cut)
B1: (ii) CT is not directed from to in this cut, so increasing it leaves the cut capacity, and so the maximum flow, at
M1: increasing SB by raises this cut to
A1: the next smallest cut has capacity at least (for example has ), so the maximum flow rises to
R1: increasing SB is worthwhile (flow up by ); increasing CT gives no benefit
Accept: any valid argument that the minimum cut has becomeTotal for question 4: 12 marks
End of questions