Flows, cuts and the max-flow min-cut theoremAQA A-Level Further Maths: Subtopic test

1. 1
   A network has source $S$, sink $T$ and intermediate nodes $A$ and $B$. The directed arcs and their capacities are $SA$ 7, $SB$ 6, $AB$ 2, $AT$ 4 and $BT$ 8.

   (a)

   Find the capacity of the cut that separates $\{S,B\}$ from $\{A,T\}$.

   [1 mark]

   • A$13$
   • B$15$
   • C$17$
   • D$27$

   (b)

   What is the value of the maximum flow from $S$ to $T$?

   [1 mark]

   • A$13$
   • B$15$
   • C$8$
   • D$12$

   (c)

   Explain why the flow from $S$ to $T$ cannot exceed 12.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   Two factories $F_1$ and $F_2$ can make at most 10 and 8 tonnes of a product per hour. They send it through a depot $D$ to two shops $T_1$ and $T_2$, which can receive at most 8 and 6 tonnes per hour. The directed arcs and their capacities (tonnes per hour) are $F_1D$ 9, $F_2D$ 6, $F_1T_1$ 3, $DT_1$ 5 and $DT_2$ 7.

   (a)

   A supersource $S$ is added so the network has a single source. Which arcs should be added?

   [1 mark]

   • AOne arc from $S$ to $F_1$ with capacity 18
   • BArcs from $T_1$ and $T_2$ to $S$ with capacities 8 and 6
   • CArcs from $S$ to $F_1$ and from $S$ to $F_2$ with capacities 10 and 8
   • DArcs from $S$ to $T_1$ and from $S$ to $T_2$ with capacities 8 and 6

   (b)

   A supersink is also added, using the shops' limits. What is the value of the maximum flow, in tonnes per hour?

   [1 mark]

   • A$14$
   • B$12$
   • C$15$
   • D$18$

   (c)

   Explain why arc $DT_2$ cannot be saturated in a maximum flow.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A network has source $S$, sink $T$ and nodes $A$, $B$ and $C$. The directed arcs and their capacities are $SA$ 10, $SB$ 6, $AB$ 3, $AC$ 5, $BC$ 4, $BT$ 2 and $CT$ 9.

   (a)

   Find the capacity of the cut that separates $\{S,B\}$ from $\{A,C,T\}$.

   [3 marks]

   (b)

   A flow of value 11 is found. Prove that it is a maximum flow.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A distributor has two warehouses $W_1$ and $W_2$ that can dispatch at most 14 and 10 pallets per day. Goods go through a hub $H$ to two stores $M_1$ and $M_2$, which can take at most 11 and 9 pallets per day. The directed arcs and their capacities (pallets per day) are $W_1H$ 8, $W_2H$ 7, $W_1M_1$ 5, $HM_1$ 6, $HM_2$ 9 and $W_2M_2$ 3.

   (a)

   A flow of 20 pallets per day is found. (i) Describe how to turn the network into one with a single source and a single sink, giving all capacities. (ii) Show that 20 is the maximum flow.

   [6 marks]

   (b)

   The distributor can raise the capacity of exactly one arc of the original network (including the arcs to the supersink) by 3. Using cuts, decide which arc to raise, and find the new maximum flow.

   [6 marks]

   Total for question 4: 12 marks

End of questions