AQA A-Level Further Maths
Augmenting flows and refinements
Total 27 marks
Name
Class
Date
- 1A network has source , sink and nodes and . The directed arcs and their capacities are 6, 3, 5, 3 and 4. An initial flow of 4 units is sent along the route .(a)By how much can the flow be increased along the route ?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: C(b)The flow is increased to 6 by sending 2 more units along . Which route is now a flow-augmenting route?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: A(c)Show how the flow of 6 can be increased further, and prove that the resulting flow is a maximum.[2 marks]Show the mark scheme
Mark scheme
B1: augmenting route with used backwards, increasing the flow by 1 to 7
R1: the cut has capacity , so by the max-flow min-cut theorem 7 is maximal
Accept: any correct statement that and are both saturatedTotal for question 1: 4 marks
- 2Water flows from a source to a sink through junctions and . Each pipe has a lower and an upper limit on its flow, in litres per second, written : , , , and . Water flows in the direction of each arc.(a)Flows are given in the order . Which of these is a feasible flow?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: D(b)What is the maximum value of a feasible flow, in litres per second?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: B(c)Show that the value of every feasible flow is at least 7 litres per second.[2 marks]Show the mark scheme
Mark scheme
M1: the value of the flow equals the flow into , which is
A1: and , so the value is at least
AGTotal for question 2: 4 marks
- 3A sorting centre network has source , sink and nodes , and . The directed arcs and their capacities (parcels per hour, in thousands) are 8, 7, 4, 5, 6, 5 and 9. Node can handle at most 6 thousand parcels per hour in total.(a)Explain how the network can be modified to include the restriction on node .[3 marks]
Show the mark scheme
Mark scheme
B1: replace by two nodes and
B1: arcs and go into ; arcs and leave from
B1: add an arc with capacity 6(b)A flow of value 11 is found in the modified network. Without the restriction the maximum flow is 14. Prove that 11 is the maximum flow in the modified network and state the effect of the restriction.[4 marks]Show the mark scheme
Mark scheme
M1: a cut separating from , e.g.
A1: arcs and identified, capacity
R1: flow equals cut capacity, so by the max-flow min-cut theorem it is maximal
A1: the restriction reduces the maximum flow by thousand parcels per hourTotal for question 3: 7 marks
- 4A company moves goods from a factory to a depot through hubs. The directed arcs and their capacities (tonnes per hour) are 9, 7, 6, 3, 2, 5, 7 and 8. An initial flow of 11 tonnes per hour uses with 6 and with 5.(a)Use flow augmentation from the initial flow to find a maximum flow, and prove that it is maximal.[6 marks]
Show the mark scheme
Mark scheme
M1: a route using only arcs with spare capacity, e.g. (spare 3, 3, 3)
A1: flow increased by 3 to 14
M1: a second route, e.g. (spare 2, 2, 1)
A1: flow increased by 1 to 15
A1: maximum flow 15
R1: the cut , with arcs and , has capacity , so by the max-flow min-cut theorem the flow is maximal
Accept: the cut with arcs , , and capacity(b)Hub can in fact process at most 6 tonnes per hour. The company can either raise the capacity of arc by 2, or raise the hub's limit by 2. Evaluate the two options, using cuts.[6 marks]Show the mark scheme
Mark scheme
M1: hub modelled as with capacity 6, arcs into ending at and arcs out of leaving from
A1: minimum cut , capacity , so the maximum flow is now 13
M1: considers the cuts again after each change
A1: raising to 9 gives a minimum cut of capacity , so the maximum flow is only 14
A1: raising to 8 gives a maximum flow of 15
R1: raising the hub's limit increases the flow by 2 against 1, so it is the better option
Accept: the cut written asTotal for question 4: 12 marks
End of questions