Cuts, labelling procedure and max-flow min-cutEdexcel A-Level Further Maths: Subtopic test

1. 1
   A network has source S, sink T and intermediate vertices A and B. The directed arcs and their capacities are: SA 7, SB 5, AB 3, AT 4 and BT 6 (for example, arc SA goes from S to A and has capacity 7).

   (a)

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

   [1 mark]

   • A$8$
   • B$19$
   • C$25$
   • D$12$

   (b)

   A flow has SA 5, SB 3, AB 1, AT 4 and BT 4. What is the value of this flow?

   [1 mark]

   • A$5$
   • B$10$
   • C$8$
   • D$12$

   (c)

   A flow of value $10$ is found: SA 7, SB 3, AB 3, AT 4 and BT 6. Use a cut to prove that this flow is a maximum flow.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A network has source S, sink T and intermediate vertices A, B and C. The directed arcs and their capacities are: SA 9, SB 7, AB 4, AC 5, BC 6, BT 4 and CT 8. A flow is already in the network: SA 5, SB 3, AB 2, AC 3, BC 3, BT 2 and CT 6, so the flow value is 8.

   (a)

   By how much can the flow along arc AC be increased?

   [1 mark]

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

   (b)

   In the labelling procedure, which pair of labels is written on arc SB?

   [1 mark]

   • A$4$ in the direction S to B and $3$ in the direction B to S
   • B$3$ in the direction S to B and $4$ in the direction B to S
   • C$7$ in the direction S to B and $3$ in the direction B to S
   • D$4$ in the direction S to B and $4$ in the direction B to S

   (c)

   Find the amount by which the flow can be increased along the route S, A, C, T, and state the new flow value.

   [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 directed arcs and their capacities are: SA 10, SB 8, AC 7, BA 3, BD 6, CT 9, DC 4 and DT 5.

   (a)

   Find the capacity of the cut that separates $\{S,A,C\}$ from $\{B,D,T\}$, and of the cut that separates $\{S,A,B\}$ from $\{C,D,T\}$. What do these tell you about the maximum flow?

   [3 marks]

   (b)

   A flow has SA 7, SB 5, AC 7, BD 5, CT 7 and DT 5, and zero flow on BA and DC. Use the labelling procedure to find a flow-augmenting route, increase the flow, and prove that the new flow is a maximum.

   [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 directed arcs and their capacities are: SA 9, SB 8, AB 3, AD 3, BC 4, BD 3, BT 8, CT 11 and DT 5. A flow of value 3 is already in the network, with a flow of 3 along each of SA, AB, BD and DT, and zero flow elsewhere.

   (a)

   Use the labelling procedure to find the maximum flow, stating each flow-augmenting route and the amount by which the flow increases.

   [6 marks]

   (b)

   (i) Prove that the flow in (a) is a maximum flow. (ii) The owner can pay to increase the capacity of either CT from $11$ to $15$, or SB from $8$ to $10$. Evaluate which, if either, is worth doing.

   [6 marks]

   Total for question 4: 12 marks

End of questions