AQA A-Level Further Maths
Flows, cuts and the max-flow min-cut theorem
Total 27 marks
Name
Class
Date
- 1A network has source , sink and intermediate nodes and . The directed arcs and their capacities are 7, 6, 2, 4 and 8.(a)Find the capacity of the cut that separates from .[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: B(b)What is the value of the maximum flow from to ?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: D(c)Explain why the flow from to cannot exceed 12.[2 marks]Show the mark scheme
Mark scheme
B1: identifies the cut , whose arcs are and with capacity
R1: all flow from to must cross the cut, so it cannot exceed its capacity
Accept: the cut , with arcs , , and capacityTotal for question 1: 4 marks
- 2Two factories and can make at most 10 and 8 tonnes of a product per hour. They send it through a depot to two shops and , which can receive at most 8 and 6 tonnes per hour. The directed arcs and their capacities (tonnes per hour) are 9, 6, 3, 5 and 7.(a)A supersource is added so the network has a single source. Which arcs should be added?[1 mark]
- AOne arc from to with capacity 18
- BArcs from and to with capacities 8 and 6
- CArcs from to and from to with capacities 10 and 8
- DArcs from to and from to with capacities 8 and 6
Show the mark scheme
Mark scheme
Answer: C(b)A supersink is also added, using the shops' limits. What is the value of the maximum flow, in tonnes per hour?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: A(c)Explain why arc cannot be saturated in a maximum flow.[2 marks]Show the mark scheme
Mark scheme
B1: can receive at most 6 tonnes per hour, so the flow along is at most 6
R1: the capacity of is 7, so at least 1 tonne per hour of its capacity is always unused
Accept: the arc from to the supersink has capacity 6Total for question 2: 4 marks
- 3A network has source , sink and nodes , and . The directed arcs and their capacities are 10, 6, 3, 5, 4, 2 and 9.(a)Find the capacity of the cut that separates from .[3 marks]
Show the mark scheme
Mark scheme
B1: arcs from to identified as , and
M1: adds the capacities of arcs directed out of only
A1:
Do not accept: 19, from including , which is directed into(b)A flow of value 11 is found. Prove that it is a maximum flow.[4 marks]Show the mark scheme
Mark scheme
M1: chooses a cut separating from , e.g.
A1: arcs , , identified
A1: capacity
R1: flow value equals the capacity of a cut, so by the max-flow min-cut theorem the flow is maximal
Accept: the cut with arcs , , capacityTotal for question 3: 7 marks
- 4A distributor has two warehouses and that can dispatch at most 14 and 10 pallets per day. Goods go through a hub to two stores and , which can take at most 11 and 9 pallets per day. The directed arcs and their capacities (pallets per day) are 8, 7, 5, 6, 9 and 3.(a)A flow of 20 pallets per day is found. (i) Describe how to turn the network into one with a single source and a single sink, giving all capacities. (ii) Show that 20 is the maximum flow.[6 marks]
Show the mark scheme
Mark scheme
B1: (i) supersource with arcs (14) and (10)
B1: (i) supersink with arcs (11) and (9)
M1: (ii) a cut separating from the rest, using arcs and
A1: capacity
R1: every unit of flow from to crosses this cut, so the flow cannot exceed 20
R1: the flow equals the cut capacity, so by the max-flow min-cut theorem it is a maximum
Accept: the cut with arcs , , and capacity(b)The distributor can raise the capacity of exactly one arc of the original network (including the arcs to the supersink) by 3. Using cuts, decide which arc to raise, and find the new maximum flow.[6 marks]Show the mark scheme
Mark scheme
M1: finds the minimum cuts of the network with the supersource and supersink
A1: and , both of capacity 20
R1: the maximum flow rises only if the arc lies in every minimum cut
A1: is the only arc in both, so raise to 12
M1: checks the next smallest cut, e.g. , capacity
A1: new maximum flow 23, an increase of 3
Accept: raising any other arc leaves one minimum cut unchanged, so the flow stays at 20Total for question 4: 12 marks
End of questions