Discrete Mathematics 3: Network flowsAQA A-Level Further Maths: Topic test

1. 1
   A network has source $S$, sink $T$ and intermediate nodes $P$, $Q$ and $R$. The directed arcs and their capacities are $SP$ 12, $SQ$ 9, $PQ$ 4, $PR$ 8, $QR$ 6, $QT$ 7 and $RT$ 11.

   (a)

   What is the value of the cut that separates $\{S,\ P,\ Q\}$ from $\{R,\ T\}$?

   [1 mark]

   • A$14$
   • B$33$
   • C$21$
   • D$18$

   (b)

   The cut that separates $\{S,\ P,\ Q,\ R\}$ from $\{T\}$ has value $18$. Which conclusion follows?

   [1 mark]

   • AThe maximum flow is $21$
   • BEvery flow through the network has value exactly $18$
   • CThe maximum flow is less than $18$
   • DNo flow through the network can have a value greater than $18$

   (c)

   A student claims to have found a flow of value $19$. Explain why this must be wrong.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A network has source $S$, sink $T$ and intermediate nodes $A$, $B$, $C$ and $D$. The directed arcs and their capacities are $SA$ 10, $SB$ 8, $AB$ 3, $AC$ 7, $BC$ 4, $BD$ 6, $CD$ 2, $CT$ 9 and $DT$ 8. A flow has $SA$ 7, $SB$ 6, $AC$ 7, $BD$ 6, $CT$ 7 and $DT$ 6, and all other arcs carry no flow.

   (a)

   Which of these routes from $S$ to $T$ cannot be used to increase the flow?

   [1 mark]

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

   (b)

   By how much can the flow be increased along $S,\ A,\ B,\ C,\ T$?

   [1 mark]

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

   (c)

   The flow is increased by $2$ along $S,\ A,\ B,\ C,\ T$ and then by a further $2$ along $S,\ B,\ C,\ D,\ T$. State the new flow value and use a cut to show that it is maximal.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A water company has two reservoirs $U$ and $V$ that can supply at most $15$ and $11$ megalitres per day. Water goes through pipes to two towns $Z$ and $W$, which can take at most $13$ and $12$ megalitres per day. The pipes, with capacities in megalitres per day, are $UX$ 9, $UY$ 8, $VX$ 7, $VY$ 6, $XZ$ 7, $XW$ 4, $YZ$ 4 and $YW$ 6, where $X$ and $Y$ are junctions.

   (a)

   Describe how to convert this network into one with a single source and a single sink, giving the capacities of any arcs that you add.

   [3 marks]

   (b)

   Find the maximum flow through the network and prove that it is maximal.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A network has source $S$, sink $T$ and intermediate nodes $A$, $B$, $C$ and $D$. The directed arcs and their capacities, in units per hour, are $SA$ 14, $SB$ 11, $AC$ 9, $AD$ 6, $BC$ 5, $BD$ 8, $CD$ 3, $CT$ 10 and $DT$ 12.

   (a)

   Starting from zero flow, use flow-augmenting routes to find a maximum flow. List each route used and the flow added, and prove that your flow is maximal.

   [6 marks]

   (b)

   Because of repair work, no more than $8$ units per hour can pass through node $C$. Show how to model this restriction, and find the new maximum flow, proving that it is maximal.

   [6 marks]

   Total for question 4: 12 marks

5. 5
   A network has source $S$, sink $T$ and intermediate nodes $J$, $K$ and $L$. The directed arcs and their capacities are $SJ$ 9, $SK$ 6, $JK$ 2, $JL$ 5, $KT$ 6 and $LT$ 7. A flow has $SJ$ 7, $SK$ 3, $JK$ 2, $JL$ 5, $KT$ 5 and $LT$ 5.

   (a)

   What is the value of the cut that separates $\{S,\ J,\ K\}$ from $\{L,\ T\}$?

   [1 mark]

   • A$13$
   • B$11$
   • C$15$
   • D$18$

   (b)

   The maximum flow is $11$. Which pair of arcs must both carry their full capacity in every maximum flow?

   [1 mark]

   • A$JL$ and $KT$
   • B$SJ$ and $SK$
   • C$JK$ and $JL$
   • D$KT$ and $LT$

   (c)

   Show that the given flow is not a maximum flow by finding a route along which the flow can be increased, and state the new flow value.

   [2 marks]

   Total for question 5: 4 marks

6. 6
   A pipeline network has source $S$ and sink $T$ and nodes $A$ and $B$. Each arc has a lower and an upper capacity, in litres per second. $SA$ has lower $2$ and upper $7$. $SB$ has lower $1$ and upper $5$. $AB$ has lower $0$ and upper $3$. $AT$ has lower $3$ and upper $6$. $BT$ has lower $2$ and upper $8$.

   (a)

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

   [1 mark]

   • A$5,\ 2,\ 3,\ 2,\ 5$
   • B$4,\ 3,\ 1,\ 3,\ 5$
   • C$3,\ 6,\ 0,\ 3,\ 6$
   • D$4,\ 3,\ 1,\ 3,\ 4$

   (b)

   What is the greatest possible value of a flow through the network?

   [1 mark]

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

   (c)

   Find the least possible value of a flow through the network, giving a feasible flow that achieves it.

   [2 marks]

   Total for question 6: 4 marks

7. 7
   A recycling company's network has source $S$ and sink $T$. The directed arcs and their capacities, in tonnes per hour, are $SA$ 8, $SB$ 7, $SC$ 5, $AH$ 6, $BH$ 7, $CT$ 4 and $HT$ 15, where $H$ is a sorting hub. The hub $H$ can handle at most $9$ tonnes per hour.

   (a)

   Explain how the restriction on the hub $H$ can be included in the network.

   [3 marks]

   (b)

   Find the maximum flow when the hub restriction applies and prove that it is maximal.

   [4 marks]

   Total for question 7: 7 marks

8. 8
   Two depots $G$ and $H$ can send out at most $12$ and $9$ pallets per hour. They send goods through sorting centres $M$ and $N$ to a single lorry park $T$. The links and their capacities, in pallets per hour, are $GM$ 8, $GN$ 5, $HM$ 4, $HN$ 7, $MT$ 10 and $NT$ 9.

   (a)

   Introduce a supersource and find the maximum flow, proving that it is maximal.

   [6 marks]

   (b)

   Sorting centre $M$ can now handle at most $7$ pallets per hour. Explain how to model this and find the new maximum flow, proving that it is maximal.

   [6 marks]

   Total for question 8: 12 marks

End of questions