Decision Mathematics 2: Flows in networksEdexcel A-Level Further Maths: Topic test

1. 1
   A water network has source S, sink T and intermediate vertices A, B and C. The directed pipes and their capacities, in litres per second, are: SA 10, SB 9, BA 4, AC 7, BT 5 and CT 8.

   (a)

   What is the capacity of the cut with $X=\{S,A\}$ and $Y=\{B,C,T\}$?

   [1 mark]

   • A$20$
   • B$16$
   • C$26$
   • D$9$

   (b)

   A cut has capacity 12. What does this tell you about every flow from S to T?

   [1 mark]

   • AIt is exactly 12
   • BIt is at least 12
   • CIt is more than 12 for some flows
   • DIt is at most 12

   (c)

   Find a flow of value 12, and use the cut with $X=\{S,A,B\}$ and $Y=\{C,T\}$ to show that it is a maximum flow.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A pipe network has source S, sink T and intermediate vertices A and B. Each pipe's capacity and current flow, in litres per second, are: SA capacity 9, flow 6; SB capacity 6, flow 3; AB capacity 3, flow 1; AT capacity 5, flow 5; BT capacity 8, flow 4. The labelling procedure is used to increase the flow.

   (a)

   In the labelling procedure, what is the label on arc AB in the direction opposite to the arc, showing how much the flow can be reduced?

   [1 mark]

   • A$1$
   • B$2$
   • C$3$
   • D$0$

   (b)

   The labelling procedure finds the path S, A, B, T. By how much can the flow be increased along this path?

   [1 mark]

   • A$4$
   • B$3$
   • C$2$
   • D$1$

   (c)

   The flow is increased by the greatest possible amount along S, A, B, T. State the new flow in each of the three pipes SA, AB and BT, and the new value of the flow.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A network has source S, sink T and intermediate vertices A, B, C and D. The capacities, in units per minute, are: SA 9, SB 7, AC 4, AD 5, BC 3, BD 2, CT 8 and DT 7. A flow has SA 6, SB 4, AC 4, AD 2, BC 3, BD 1, CT 7 and DT 3, with value 10.

   (a)

   Use the labelling procedure to find two flow-augmenting paths, stating the extra flow along each, and find the new value of the flow.

   [3 marks]

   (b)

   Show that the flow of value 14 found in part (a) is a maximum flow.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A network has source S, sink T and intermediate vertices A, B, C and D. The capacities, in units per minute, are: SA 4, SB 11, AB 10, AC 7, AD 11, BD 11, CD 5, CT 8 and DT 8. A flow has SA 4, SB 4, AB 4, BD 8 and DT 8, with no flow in any other pipe. Its value is 8.

   (a)

   Use the labelling procedure to find a flow-augmenting path, and state the amount by which the flow can be increased. Give the new flow in each pipe that changes, and the new value of the flow.

   [6 marks]

   (b)

   Use the new flow from part (a) and the cut $X=\{S,B,D\}$, $Y=\{A,C,T\}$ to prove that the flow of value 12 is a maximum flow.

   [6 marks]

   Total for question 4: 12 marks

5. 5
   Two farms, F1 and F2, can send at most 12 and 9 tonnes of produce a day. Two markets, X and Y, can take at most 10 and 8 tonnes a day. The roads, with capacities in tonnes a day, are F1X 7, F1Y 6, F2X 5 and F2Y 4. A super source SS and a super sink TT are added so that the maximum flow can be found.

   (a)

   What is the capacity of the arc from SS to F2?

   [1 mark]

   • A$12$
   • B$21$
   • C$9$
   • D$5$

   (b)

   How many arcs have to be added to the network?

   [1 mark]

   • A$4$
   • B$2$
   • C$6$
   • D$8$

   (c)

   Find the maximum flow, and prove that it is a maximum.

   [2 marks]

   Total for question 5: 4 marks

6. 6
   A pipeline network has source S, sink T and junctions A and B. The pipes and their capacities, in units per minute, are: SA 8, SB 6, AB 3, AT 5 and BT 7. Junction A can handle at most 4 units per minute in total. To model this, A is replaced by two vertices, $A_{in}$ and $A_{out}$, joined by an arc $A_{in}A_{out}$. Pipes into A now go into $A_{in}$ and pipes out of A leave $A_{out}$.

   (a)

   What is the capacity of the arc $A_{in}A_{out}$?

   [1 mark]

   • A$8$
   • B$5$
   • C$3$
   • D$4$

   (b)

   What is the capacity of the cut with $X=\{S,A_{in}\}$ and $Y=\{A_{out},B,T\}$?

   [1 mark]

   • A$14$
   • B$10$
   • C$4$
   • D$13$

   (c)

   Find a flow of value 10, and state the maximum flow through the network.

   [2 marks]

   Total for question 6: 4 marks

7. 7
   A canal network has source S, sink T and junctions A and B. Each channel has a lower and an upper limit on its flow, written [lower, upper], in cubic metres per second: SA [3, 10], SB [2, 6], AB [2, 5], AT [2, 10] and BT [3, 7]. The capacity of a cut is the sum of the upper limits of the channels from X to Y minus the sum of the lower limits of the channels from Y to X.

   (a)

   Find the capacity of the cut with $X=\{S,B\}$ and $Y=\{A,T\}$.

   [3 marks]

   (b)

   Show that the maximum flow through the network is 15, by finding a feasible flow of value 15.

   [4 marks]

   Total for question 7: 7 marks

8. 8
   A canal network has source S, sink T and junctions A, B and C. Each channel has a lower and an upper limit on its flow, written [lower, upper], in thousands of litres per hour: SA [0, 9], SB [2, 9], AB [0, 5], AC [1, 9], BC [3, 9], CT [0, 9] and AT [3, 11]. A feasible flow is SA 9, SB 3, AB 5, AC 1, BC 8, CT 9 and AT 3, with value 12. The capacity of a cut is the sum of the upper limits of the channels from X to Y minus the sum of the lower limits of the channels from Y to X.

   (a)

   Use the labelling procedure to find a flow-augmenting path from the given flow. State the amount by which the flow can be increased, the new flows in the channels that change, and the new value of the flow.

   [6 marks]

   (b)

   Use the cut with $X=\{S,B,C\}$ and $Y=\{A,T\}$ to prove that the new flow of value 17 is a maximum flow.

   [6 marks]

   Total for question 8: 12 marks

End of questions