Multiple sources and sinks, restricted capacities and optimal flowEdexcel A-Level Further Maths: Mind map

Exam questions on Multiple sources and sinks, restricted capacities and optimal flow

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 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
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.
   The restriction at junction C is removed. Find the new maximum flow and justify your answer.2 marks
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].
   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