OCR D2 2008 January — Question 4 14 marks

Exam BoardOCR
ModuleD2 (Decision Mathematics 2)
Year2008
SessionJanuary
Marks14
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicNetwork Flows
TypeState maximum flow along specific routes
DifficultyModerate -0.5 This is a standard max-flow problem from Decision Mathematics requiring application of the labelling algorithm (Ford-Fulkerson). While it involves multiple parts and careful bookkeeping, it follows a well-defined algorithmic procedure taught directly in D2 with no novel problem-solving required. Slightly easier than average due to its purely procedural nature.
Spec7.04f Network problems: choosing appropriate algorithm
4
  1. \includegraphics[max width=\textwidth, alt={}, center]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_677_725_276_751}
  2. \(\_\_\_\_\)
  3. \(\_\_\_\_\) = \(\_\_\_\_\) gallons per hour
  4. \(\_\_\_\_\) = \(\_\_\_\_\) gallons per hour \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{(v)} \includegraphics[alt={},max width=\textwidth]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_671_729_1822_315}
    \end{figure} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{(vi)} \includegraphics[alt={},max width=\textwidth]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_677_735_1816_1171}
    \end{figure} Maximum flow = \(\_\_\_\_\) gallons per hour
Question 4:
Part (i):
AnswerMarks Guidance
Answer/WorkingMark Guidance
Single source joining to \(S_1\) and \(S_2\) with directed arcs of weights at least 90 and 110 respectively; \(T_1\) and \(T_2\) joined to single sink with directed arcs of weights at least 100 and 200 respectivelyB1 Condone no directions shown
B1Condone no directions shown
Part (ii):
AnswerMarks Guidance
Answer/WorkingMark Guidance
If \(AE\) and \(BE\) both full to capacity, 50 gallons per hour flowing into \(E\), but most that can flow out of \(E\) is 40 gallons per hourM1 Considering what happens at \(E\) (50 into \(E\))
At most 40 outA1
Part (iii):
AnswerMarks Guidance
Answer/WorkingMark Guidance
\(40 + 60 + 60 + 140 = 300\) gallons per hourB1 300
Part (iv):
AnswerMarks Guidance
Answer/WorkingMark Guidance
\(30+20+30+20+40+40+20+40 = 240\) gallons per hourM1 Evidence of using correct cut
A1240
Part (v):
AnswerMarks Guidance
Answer/WorkingMark Guidance
A feasible flow through network; Flow \(= 200\) gallons per hourM1
A1
Cut through arcs \(S_1A,\ S_1B,\ S_1C,\ S_2B,\ S_2C,\ S_2D\) or cut \(X=\{S_1, S_2\},\ Y=\{A,B,C,D,E,F,G,T_1,T_2\}\)B1 Cut indicated in any way (may be on diagram for part (i))
Part (vi):
AnswerMarks Guidance
Answer/WorkingMark Guidance
Flows into \(C\) go to \(C_\text{IN}\); arc of capacity 20 from \(C_\text{IN}\) to \(C_\text{OUT}\); flows out of \(C\) go from \(C_\text{OUT}\)B1 Into \(C\) (\(S_1=40,\ S_2=40,\ D=20\))
B1Through \(C\)
B1Out of \(C\) (\(F=60,\ G=60\))
Cut \(X=\{S_1, S_2, C_\text{IN}\}\) or \(X=\{S_1, S_2, C_\text{IN}, D\}\) shows max flow \(= 140\) gallons per hourB1 140 (cut not necessary) 
# Question 4:

## Part (i):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Single source joining to $S_1$ and $S_2$ with directed arcs of weights at least 90 and 110 respectively; $T_1$ and $T_2$ joined to single sink with directed arcs of weights at least 100 and 200 respectively | B1 | Condone no directions shown |
| | B1 | Condone no directions shown |

## Part (ii):
| Answer/Working | Mark | Guidance |
|---|---|---|
| If $AE$ and $BE$ both full to capacity, 50 gallons per hour flowing into $E$, but most that can flow out of $E$ is 40 gallons per hour | M1 | Considering what happens at $E$ (50 into $E$) |
| At most 40 out | A1 | |

## Part (iii):
| Answer/Working | Mark | Guidance |
|---|---|---|
| $40 + 60 + 60 + 140 = 300$ gallons per hour | B1 | 300 |

## Part (iv):
| Answer/Working | Mark | Guidance |
|---|---|---|
| $30+20+30+20+40+40+20+40 = 240$ gallons per hour | M1 | Evidence of using correct cut |
| | A1 | 240 |

## Part (v):
| Answer/Working | Mark | Guidance |
|---|---|---|
| A feasible flow through network; Flow $= 200$ gallons per hour | M1 | |
| | A1 | |
| Cut through arcs $S_1A,\ S_1B,\ S_1C,\ S_2B,\ S_2C,\ S_2D$ or cut $X=\{S_1, S_2\},\ Y=\{A,B,C,D,E,F,G,T_1,T_2\}$ | B1 | Cut indicated in any way (may be on diagram for part (i)) |

## Part (vi):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Flows into $C$ go to $C_\text{IN}$; arc of capacity 20 from $C_\text{IN}$ to $C_\text{OUT}$; flows out of $C$ go from $C_\text{OUT}$ | B1 | Into $C$ ($S_1=40,\ S_2=40,\ D=20$) |
| | B1 | Through $C$ |
| | B1 | Out of $C$ ($F=60,\ G=60$) |
| Cut $X=\{S_1, S_2, C_\text{IN}\}$ or $X=\{S_1, S_2, C_\text{IN}, D\}$ shows max flow $= 140$ gallons per hour | B1 | 140 (cut not necessary) |

---
4 (i)\\
\includegraphics[max width=\textwidth, alt={}, center]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_677_725_276_751}\\
(ii) $\_\_\_\_$\\

(iii) $\_\_\_\_$ = $\_\_\_\_$ gallons per hour\\
(iv) $\_\_\_\_$ = $\_\_\_\_$ gallons per hour

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{(v)}
  \includegraphics[alt={},max width=\textwidth]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_671_729_1822_315}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{(vi)}
  \includegraphics[alt={},max width=\textwidth]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_677_735_1816_1171}
\end{center}
\end{figure}

Maximum flow = $\_\_\_\_$ gallons per hour

\hfill \mbox{\textit{OCR D2 2008 Q4 [14]}}
This paper (5 questions)
View full paper
Q1 14 Q2 17 Q3 12 Q4 14 Q5 15