| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2012 |
| Session | January |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Network Flows |
| Type | Explain capacity/flow constraints |
| Difficulty | Moderate -0.3 This is a standard network flows question testing basic cut capacity calculations, flow constraints, and max-flow min-cut theorem application. While multi-part with 6 sections, each part involves routine D2 techniques: calculating cut capacities by summing arc weights, recognizing valid cuts, interpreting double arcs (parallel edges), and applying capacity constraints. Part (vi) requires some case analysis but follows predictable patterns. Slightly easier than average due to being mostly procedural recall rather than problem-solving. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | −1 | 1 |
I appreciate you providing this content, but what you've shared appears to be incomplete or unclear:
```
Question 4:
4 | −1 | 1
```
This doesn't contain enough information for me to clean up a mark scheme. To help you effectively, I would need:
- The actual question text
- The marking points with their annotations (M1, A1, B1, etc.)
- Any guidance notes or criteria
- The expected solutions or marking guidance
Could you please provide the complete mark scheme content for Question 4?4 The diagram represents a system of roads through which traffic flows from a source, $S$, to a sink, $T$. The weights on the arcs show the capacities of the roads in cars per minute.\\
\includegraphics[max width=\textwidth, alt={}, center]{3a47bac8-0067-4acb-a3c7-7d8512403cca-5_414_1080_349_488}
\begin{enumerate}[label=(\roman*)]
\item (a) The cut $\alpha$ partitions the vertices into the sets $\{ S , A , B , C \} , \{ D , E , F , T \}$. Calculate the capacity of cut $\alpha$.\\
(b) The cut $\beta$ partitions the vertices into the sets $\{ S , A , B , D \} , \{ C , E , F , T \}$. Calculate the capacity of cut $\beta$.\\
(c) Using only the capacities of cuts $\alpha$ and $\beta$, what can you deduce about the maximum possible flow through the system?
\item Explain why partitioning the vertices into sets $\{ S , A , D , T \} , \{ B , C , E , F \}$ does not give a cut.
\item What do the double arcs between $D$ and $E$ and between $E$ and $F$ represent?
\item Explain why the maximum possible flow along $C F$ must be less than 45 cars per minute.
\item (a) Show how a flow of 60 cars per minute along $F T$ can be achieved.\\
(b) Show that 60 cars per minute is the maximum possible flow through the system.
An extra road is opened linking $S$ to $C$. Let the capacity of this road be $x$ cars per minute.
\item Find the maximum possible flow through the new system, in terms of $x$ where necessary, for the different possible values of $x$.
\end{enumerate}
\hfill \mbox{\textit{OCR D2 2012 Q4 [13]}}