| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Session | Specimen |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Moderate -0.8 This is a standard textbook application of maximum matching in bipartite graphs with explicit step-by-step instructions. Students are guided through drawing the graph, identifying an incomplete matching, and using alternating paths—all routine procedures in D2. The Hungarian algorithm part only requires filling in a table structure, not performing the algorithm. This is easier than average A-level maths as it tests algorithmic execution rather than mathematical reasoning or problem-solving. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02c Graph terminology: walk, trail, path, cycle, route7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | 0 | 0 |
| Answer | Marks |
|---|---|
| 1 | 1 |
| Answer | Marks |
|---|---|
| 2 | 0 |
I'm ready to clean up mark scheme content, but the text you've provided appears to be incomplete or corrupted. It shows only:
```
Question 1:
1 | 0 | 0
1
1 | 1
2
2 | 0
2
```
This doesn't contain:
- Marking annotations (M1, A1, B1, etc.)
- Clear marking points or criteria
- Unicode symbols to convert to LaTeX
Could you please provide the complete, original extracted mark scheme content? Once you share the full text, I'll clean it up according to your specifications.1 [Answer this question on the insert provided.]\\
Six neighbours have decided to paint their houses in bright colours. They will each use a different colour.
\begin{itemize}
\item Arthur wants to use lavender, orange or tangerine.
\item Bridget wants to use lavender, mauve or pink.
\item Carlos wants to use pink or scarlet.
\item Davinder wants to use mauve or pink.
\item Eric wants to use lavender or orange.
\item Ffion wants to use mauve.
\end{itemize}
Arthur chooses lavender, Bridget chooses mauve, Carlos chooses pink and Eric chooses orange. This leaves Davinder and Ffion with colours that they do not want.\\
(i) Draw a bipartite graph on the insert, showing which neighbours ( $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }$ ) want which colours (L, M, O, P, S, T). On a separate diagram on the insert, show the incomplete matching described above.\\
(ii) By constructing alternating paths obtain the complete matching between the neighbours and the colours. Give your paths and show your matching on the insert.\\
(iii) Fill in the table on the insert to show how the Hungarian algorithm could have been used to find the complete matching. (You do not need to carry out the Hungarian algorithm.)
\hfill \mbox{\textit{OCR D2 Q1 [9]}}