Cuts, labelling procedure and max-flow min-cutEdexcel A-Level Further Maths: Mind map

Exam questions on Cuts, labelling procedure and max-flow min-cut

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