Multiple sources and sinks, restricted capacities and optimal flowEdexcel A-Level Further Maths: Subtopic test

1. 1
   Two 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

   (b)

   What is the capacity of the cut that separates $\{S,P,Q,A\}$ from $\{B,U,V,T\}$?

   [1 mark]

   • A$22$
   • B$16$
   • C$11$
   • D$7$

   (c)

   A flow of value $14$ is found in which depot P supplies $9$ units. Show that this flow is a maximum flow, and find how much of the supply at depot Q is not used.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A 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, $C_{\text{in}}$ and $C_{\text{out}}$, with arcs into C ending at $C_{\text{in}}$, arcs out of C starting at $C_{\text{out}}$, and an arc $C_{\text{in}}C_{\text{out}}$ of capacity 7
   • DAdd a super sink with capacity 7

   (b)

   What is the maximum flow through the network, in units per hour?

   [1 mark]

   • A$13$
   • B$15$
   • C$7$
   • D$10$

   (c)

   The restriction at junction C is removed. Find the new maximum flow and justify your answer.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A 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 $X=\{S,B\}$ and $Y=\{A,C,T\}$, and of the cut with $X=\{S,A,B,C\}$ and $Y=\{T\}$. What can you deduce about the maximum flow?

   [3 marks]

   (b)

   A feasible flow is SA 5, SB 4, AB 1, AC 4, BC 3, BT 2 and CT 7, with value $9$. 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]

   Total for question 3: 7 marks

4. 4
   A 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]

   (b)

   (i) Prove that the flow in (a) is a maximum. (ii) The operator can either reduce the minimum flow in AB from $3$ to $1$, or raise the maximum flow in CT from $5$ to $9$. Evaluate which is worth doing.

   [6 marks]

   Total for question 4: 12 marks

End of questions