Augmenting flows and refinementsAQA A-Level Further Maths: Mind map

Exam questions on Augmenting flows and refinements

1. A network has source $S$, sink $T$ and nodes $A$ and $B$. The directed arcs and their capacities are $SA$ 6, $SB$ 3, $AB$ 5, $AT$ 3 and $BT$ 4. An initial flow of 4 units is sent along the route $S\to A\to B\to T$.
   Show how the flow of 6 can be increased further, and prove that the resulting flow is a maximum.2 marks
2. Water flows from a source $S$ to a sink $T$ through junctions $A$ and $B$. Each pipe has a lower and an upper limit on its flow, in litres per second, written $[\text{lower},\text{upper}]$: $SA$ $[3,8]$, $SB$ $[2,5]$, $AB$ $[1,4]$, $AT$ $[4,7]$ and $BT$ $[3,6]$. Water flows in the direction of each arc.
   Show that the value of every feasible flow is at least 7 litres per second.2 marks
3. A sorting centre network has source $S$, sink $T$ and nodes $A$, $B$ and $C$. The directed arcs and their capacities (parcels per hour, in thousands) are $SA$ 8, $SB$ 7, $AB$ 4, $AC$ 5, $BC$ 6, $BT$ 5 and $CT$ 9. Node $B$ can handle at most 6 thousand parcels per hour in total.
   Explain how the network can be modified to include the restriction on node $B$.3 marks