AQA D2 2012 June — Question 6

Exam BoardAQA
ModuleD2 (Decision Mathematics 2)
Year2012
SessionJune
TopicNetwork Flows
6
  1. The network shows a flow from \(S\) to \(T\) along a system of pipes, with the capacity in litres per second indicated on each edge.
    \includegraphics[max width=\textwidth, alt={}, center]{d0902228-7041-4449-9ccb-770352ce6bef-14_510_936_411_552}
    1. Show that the value of the cut shown on the diagram is 36 .
    2. The cut shown on the diagram can be represented as \(\{ S , B \} , \{ A , C , T \}\). Complete the table below to give the value of each of the 8 possible cuts.
      CutValue
      \(\{ S \}\)\(\{ A , B , C , T \}\)30
      \(\{ S , A \}\)\(\{ B , C , T \}\)29
      \(\{ S , B \}\)\(\{ A , C , T \}\)36
      \(\{ S , C \}\)\(\{ A , B , T \}\)33
      \(\{ S , A , B \}\)\(\{ C , T \}\)
      \(\{ S , A , C \}\)\(\{ B , T \}\)
      \(\{ S , B , C \}\)\(\{ A , T \}\)
      \(\{ S , A , B , C \}\)\(\{ T \}\)30
    3. State the value of the maximum flow through the network, giving a reason for your answer. Maximum flow is \(\_\_\_\_\) because \(\_\_\_\_\)
    4. Indicate on the diagram below a possible flow along each edge corresponding to this maximum flow.
      \includegraphics[max width=\textwidth, alt={}, center]{d0902228-7041-4449-9ccb-770352ce6bef-15_469_933_406_550}
  2. The capacities along \(S C\) and along \(A T\) are each increased by 4 litres per second.
    1. Using your values from part (a)(iv) as the initial flow, indicate potential increases and decreases on the diagram below and use the labelling procedure to find the new maximum flow through the network. You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the diagram.
      \includegraphics[max width=\textwidth, alt={}, center]{d0902228-7041-4449-9ccb-770352ce6bef-15_470_935_1315_260}
      Path
      Additional
      Flow
    2. Use your results from part (b)(i) to illustrate the flow along each edge that gives this new maximum flow, and state the value of the new maximum flow. New maximum flow is \(\_\_\_\_\)
      \includegraphics[max width=\textwidth, alt={}, center]{d0902228-7041-4449-9ccb-770352ce6bef-15_474_933_2078_550}
This paper (6 questions)
View full paper
Q1 Q2 Q3 Q4 Q5 Q6