Find minimum cut

A question is this type if and only if it asks to identify which cut has minimum capacity and state its value, often requiring comparison of multiple cuts.

1 questions · Standard +0.3

Sort by: Default | Easiest first | Hardest first
OCR D2 Q5
22 marks Standard +0.3
The following matrix gives the capacities of the pipes in a system. \begin{array}{c|c|c|c|c|c|c|c} To & & S & T & A & B & C & D
From & & & & & & &
\hline S & & -- & -- & 16 & 26 & -- & --
T & & -- & -- & -- & -- & -- & --
A & & -- & -- & -- & -- & 13 & 5
B & & -- & 16 & -- & -- & -- & 11
C & & -- & 11 & -- & -- & -- & --
D & & -- & 11 & -- & -- & -- & --
\end{array}
  1. Represent this information as a digraph. [3 marks]
  2. Find the minimum cut, expressing it in the form \(\{\) \(\}|\{\) \(\}\), and state its value. [2 marks]
  3. Starting from having no flow in the system, use the labelling procedure to find a maximal flow through the system. You should list each flow-augmenting route you use, together with its flow. [5 marks]
  4. Explain how you know that this flow is maximal. [1 mark]
[11 marks]