| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2011 |
| Session | January |
| Marks | 4 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Moderate -0.8 This is a straightforward application of the bipartite matching algorithm with small numbers (4 people, 5 birds). Part (i) is just drawing a graph from given information, part (ii) guides students through finding an alternating path with the starting vertex given, and part (iii) asks for a complete matching excluding one option. All parts are routine algorithmic exercises with no problem-solving insight required. |
| 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 |
| Answer | Marks | Guidance |
|---|---|---|
| Bipartite graph correct (A connected to K, B connected to L/M/N, C connected to K/L/M/N/O, D connected to N/O as shown) | B1 | Graph must be bipartite structure |
| Answer | Marks | Guidance |
|---|---|---|
| Alternating path: \(N = A - K = C - O = D\) | B1 | This alternating path written down, not just read off from labels on graph |
| Matching: Amir sponsors nightjar, Bex sponsors lark, Ceris sponsors kite, Duncan sponsors owl | B1 | This matching written down in words or letters |
| Answer | Marks | Guidance |
|---|---|---|
| Amir sponsors nightjar, Bex sponsors moorhen, Ceris sponsors kite, Duncan sponsors lark | B1 | This matching written down in words or symbols |
# Question 1:
## Part (i)
| Bipartite graph correct (A connected to K, B connected to L/M/N, C connected to K/L/M/N/O, D connected to N/O as shown) | B1 | Graph must be bipartite structure |
## Part (ii)
| Alternating path: $N = A - K = C - O = D$ | B1 | This alternating path written down, not just read off from labels on graph |
| Matching: Amir sponsors nightjar, Bex sponsors lark, Ceris sponsors kite, Duncan sponsors owl | B1 | This matching written down in words or letters |
## Part (iii)
| Amir sponsors nightjar, Bex sponsors moorhen, Ceris sponsors kite, Duncan sponsors lark | B1 | This matching written down in words or symbols |
---1 Four friends, Amir (A), Bex (B), Cerys (C) and Duncan (D), are visiting a bird sanctuary. They have decided that they each will sponsor a different bird. The sanctuary is looking for sponsors for a kite $( K )$, a lark $( L )$, a moorhen $( M )$, a nightjar $( N )$, and an owl $( O )$.
Amir wants to sponsor the kite, the nightjar or the owl; Bex wants to sponsor the lark, the moorhen or the owl; Cerys wants to sponsor the kite, the lark or the owl; and Duncan wants to sponsor either the lark or the owl.
\begin{enumerate}[label=(\roman*)]
\item Draw a bipartite graph to show which friend wants to sponsor which birds.
Amir chooses to sponsor the kite and Bex chooses the lark. Cerys then chooses the owl and Duncan is left with no bird that he wants.
\item Write down the shortest possible alternating path starting from the nightjar, and hence write down one way in which all four friends could have chosen birds that they wanted to sponsor.
\item List a way in which all four friends could have chosen birds they wanted to sponsor, with the owl not being chosen.
\end{enumerate}
\hfill \mbox{\textit{OCR D2 2011 Q1 [4]}}