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

Exam questions on Flows, cuts and the max-flow min-cut theorem

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.
   Explain why the flow from $S$ to $T$ cannot exceed 12.2 marks
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.
   Explain why arc $DT_2$ cannot be saturated in a maximum flow.2 marks
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.
   Find the capacity of the cut that separates $\{S,B\}$ from $\{A,C,T\}$.3 marks