Augmenting flows and refinementsAQA A-Level Further Maths: Subtopic test

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

   (a)

   By how much can the flow be increased along the route $S\to A\to T$?

   [1 mark]

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

   (b)

   The flow is increased to 6 by sending 2 more units along $S\to A\to T$. Which route is now a flow-augmenting route?

   [1 mark]

   • A$S\to B\to A\to T$
   • B$S\to B\to T$
   • C$S\to A\to B\to T$
   • D$S\to A\to T$

   (c)

   Show how the flow of 6 can be increased further, and prove that the resulting flow is a maximum.

   [2 marks]

   Total for question 1: 4 marks

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

   (a)

   Flows are given in the order $SA,SB,AB,AT,BT$. Which of these is a feasible flow?

   [1 mark]

   • A$(5,2,0,5,2)$
   • B$(7,3,2,4,5)$
   • C$(9,4,2,7,6)$
   • D$(6,4,2,4,6)$

   (b)

   What is the maximum value of a feasible flow, in litres per second?

   [1 mark]

   • A$16$
   • B$13$
   • C$7$
   • D$11$

   (c)

   Show that the value of every feasible flow is at least 7 litres per second.

   [2 marks]

   Total for question 2: 4 marks

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

   (a)

   Explain how the network can be modified to include the restriction on node $B$.

   [3 marks]

   (b)

   A flow of value 11 is found in the modified network. Without the restriction the maximum flow is 14. Prove that 11 is the maximum flow in the modified network and state the effect of the restriction.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A company moves goods from a factory $S$ to a depot $T$ through hubs. The directed arcs and their capacities (tonnes per hour) are $SA$ 9, $SB$ 7, $AC$ 6, $AD$ 3, $BC$ 2, $BD$ 5, $CT$ 7 and $DT$ 8. An initial flow of 11 tonnes per hour uses $S\to A\to C\to T$ with 6 and $S\to B\to D\to T$ with 5.

   (a)

   Use flow augmentation from the initial flow to find a maximum flow, and prove that it is maximal.

   [6 marks]

   (b)

   Hub $D$ can in fact process at most 6 tonnes per hour. The company can either raise the capacity of arc $CT$ by 2, or raise the hub's limit by 2. Evaluate the two options, using cuts.

   [6 marks]

   Total for question 4: 12 marks

End of questions