| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2012 |
| Session | January |
| Marks | 6 |
| 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 the maximum matching algorithm with clear step-by-step guidance. The question explicitly tells students what to do at each stage (draw bipartite graph, find alternating paths, improve matching), making it more of a procedural exercise than a problem-solving challenge. While it requires understanding of the alternating path method, the small size (5 students, 5 films) and structured parts make it significantly easier than average A-level questions. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02e Bipartite graphs: K_{m,n} notation |
I appreciate you sharing this, but the content you've provided appears to be a table or data structure rather than a mark scheme with marking annotations and guidance notes.
To clean this up properly, I would need:
- Actual mark scheme content with M1, A1, B1, DM1 annotations
- Mathematical notation that needs converting (θ, Σ, ≥, etc.)
- Marking points with descriptions of what earns each mark
Could you please provide the actual extracted mark scheme text? For example:
```
M1: Correct use of formula
A1: Correct value of θ = 45°
B1: Identifies symmetry
```
Once you share the real content, I'll clean it up and convert unicode symbols to LaTeX notation.1 Five film studies students need to review five different films for an assignment, but only have one evening left before the assignment is due in. They decide that they will share the work out so that each of them reviews just one film.
Jack $( J )$ wants to review a horror movie; Karen $( K )$ wants to review an animated film; Lee $( L )$ wants to review a film that is suitable for family viewing; Mark ( $M$ ) wants to review an action adventure film and Nikki ( $N$ ) wants to review anything that is in 3D.
The film "Somewhere" ( $S$ ) has been classified as a horror movie and is being shown in 3D; "Tornado Terror" ( $T$ ) has been classified as an action adventure film that is suitable for family viewing; "Underwater" $( U )$ is an animated action adventure film; "Vampires" ( $V$ ) is an animated horror movie that is suitable for family viewing and "World" ( $W$ ) is an animated film.\\
(i) Draw a bipartite graph to show which student ( $J , K , L , M , N$ ) wants to review which films ( $S , T , U$, $V , W$ ).
Initially Jack says that he will review "Somewhere", Karen then chooses "Underwater" and Lee chooses "Tornado Terror", but this would leave both Mark and Nikki with films that they do not want.\\
(ii) Write down the shortest possible alternating path starting from Nikki, and hence write down an improved, but still incomplete, matching.\\
(iii) From this incomplete matching, write down the shortest possible alternating path starting from "World", and hence write down a complete matching between the students and the films.\\
(iv) Show that this is the only possible complete matching between the students and the films.
\hfill \mbox{\textit{OCR D2 2012 Q1 [6]}}