Edexcel A-Level Further Maths
Multiple sources and sinks, restricted capacities and optimal flow
Total 27 marks
Name
Class
Date
- 1Two depots, P and Q, supply goods to two shops, U and V, through junctions A and B. Depot P can supply at most 9 units and depot Q at most 6 units. Shop U can receive at most 7 units and shop V at most 8 units. The directed roads and their capacities, in units, are: PA 6, PB 4, QB 5, AU 4, AV 3, BU 2 and BV 6. To find the greatest total delivery, a super source S and a super sink T are added.(a)Which arcs and capacities should join the super source S to the depots?[1 mark]
- ASP with capacity 9 and SQ with capacity 6
- BSP with capacity 6 and SQ with capacity 9
- CSP with capacity 7 and SQ with capacity 8
- DSP and SQ, each with infinite capacity
Show the mark scheme
Mark scheme
Answer: A(b)What is the capacity of the cut that separates from ?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: B(c)A flow of value is found in which depot P supplies units. Show that this flow is a maximum flow, and find how much of the supply at depot Q is not used.[2 marks]Show the mark scheme
Mark scheme
B1: cut separating from the other vertices: arcs SP and QB, capacity , equal to the flow, so the flow is maximum
B1: Q supplies units, so unit of Q's supply is unused
Accept: any correct cut of capacityTotal for question 1: 4 marks
- 2A pipeline network has source S, sink T and junctions A, B, C and D. The directed pipes and their capacities, in units per hour, are: SA 8, SB 7, AC 6, AT 3, BC 5, CT 6, CD 4 and DT 5. Junction C can handle at most 7 units per hour in total.(a)Which of these correctly models the restriction at junction C?[1 mark]
- AReduce the capacity of arc CT to 7
- BDelete junction C and all its arcs
- CReplace C by two vertices, and , with arcs into C ending at , arcs out of C starting at , and an arc of capacity 7
- DAdd a super sink with capacity 7
Show the mark scheme
Mark scheme
Answer: C(b)What is the maximum flow through the network, in units per hour?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: D(c)The restriction at junction C is removed. Find the new maximum flow and justify your answer.[2 marks]Show the mark scheme
Mark scheme
B1: cut separating from the other vertices has capacity SA BC , so the maximum flow is at most
B1: a flow of exists, for example SA 8, SB 5, AT 3, AC 5, BC 5, CT 6, CD 4, DT 4, so the maximum flow is
Accept: any valid flow of valueTotal for question 2: 4 marks
- 3A network has source S, sink T and vertices A, B and C. Each arc has a lower and an upper capacity, written [lower, upper]: SA [3, 9], SB [2, 6], AB [1, 4], AC [0, 5], BC [2, 6], BT [0, 4] and CT [4, 10].(a)Find the capacity of the cut with and , and of the cut with and . What can you deduce about the maximum flow?[3 marks]
Show the mark scheme
Mark scheme
B1: first cut: upper capacities SA, BC and BT, , minus the lower capacity of AB, which is directed from to :
B1: second cut: BT and CT,
B1: the maximum flow is at most
Do not accept: for the first cut(b)A feasible flow is SA 5, SB 4, AB 1, AC 4, BC 3, BT 2 and CT 7, with value . In the labelling procedure, state the two labels on arc AB and explain the second. Then find a flow-augmenting route that uses arc SB, and the new flow value.[4 marks]Show the mark scheme
Mark scheme
B1: arc AB labels: in its own direction () and in the opposite direction ()
R1: the flow cannot be reduced because it is already at the lower capacity of
M1: route S, B, T with spare capacities SB and BT
A1: flow increases by , so the new flow value is
Accept: the route S, B, C, T if the amounts are correct and give the same new flowTotal for question 3: 7 marks
- 4A network of pipes has source S, sink T and junctions A, B and C. Each pipe has a minimum and a maximum flow, written [minimum, maximum], in units per minute: SA [1, 11], SB [0, 10], AB [3, 9], AC [1, 9], AT [3, 7], BT [2, 8] and CT [0, 5]. A feasible flow of value 12 has SA 8, SB 4, AB 4, AC 1, AT 3, BT 8 and CT 1.(a)Use the labelling procedure to find the maximum flow, stating each flow-augmenting route and the amount by which the flow increases. Show how the label on the backward arc is found.[6 marks]
Show the mark scheme
Mark scheme
M1: a valid first route using forward spare capacity, for example S, A, T
A1: correct amount, for example (spare capacities SA , AT ), giving flow value
M1: a route using arc AB backwards, for example S, B, A, T
B1: backward label on AB is flow minus lower capacity,
A1: the route increases the flow by (other labels at least )
A1: maximum flow
Accept: any valid order of routes that uses the backward arc and finishes with flow(b)(i) Prove that the flow in (a) is a maximum. (ii) The operator can either reduce the minimum flow in AB from to , or raise the maximum flow in CT from to . Evaluate which is worth doing.[6 marks]Show the mark scheme
Mark scheme
M1: (i) cut with and : upper capacities SA BT
A1: subtract the lower capacity of AB (directed from to ): , equal to the flow, so the flow is maximum
M1: (ii) reducing the minimum in AB to raises this cut to
A1: the next smallest cuts have capacity or more (for example has ), so the maximum flow rises to
B1: CT is not in this cut, so raising its maximum leaves the minimum cut, and the maximum flow, at
R1: reducing the minimum in AB is worthwhile (flow up by ); raising CT gives no benefitTotal for question 4: 12 marks
End of questions