OCR D2 2010 January — Question 6

Exam BoardOCR
ModuleD2 (Decision Mathematics 2)
Year2010
SessionJanuary
TopicNetwork Flows

6 The diagram represents a system of pipes through which fluid can flow from a source, \(S\), to a sink, \(T\). It also shows two cuts, \(\alpha\) and \(\beta\). The weights on the arcs show the lower and upper capacities of the pipes in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{1ceb5585-6d3f-4723-ad49-7addfb40ab66-6_818_1285_434_429}
  1. Calculate the capacities of the cuts \(\alpha\) and \(\beta\).
  2. Explain why the arcs \(A C\) and \(A F\) cannot both be at their lower capacities.
  3. Explain why the \(\operatorname { arcs } B C , B D , D E\) and \(D T\) must all be at their lower capacities.
  4. Show that a flow of 10 litres per second is impossible. Deduce the minimum and maximum feasible flows, showing your working. Vertex \(E\) becomes blocked so that no fluid can flow through it.
  5. Draw a copy of the network with this vertex restriction. You are advised to make your diagram quite large. Show a flow of 9 litres per second on your diagram.