| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | January |
| Marks | 7 |
| 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 clear step-by-step instructions. Students simply need to draw a standard bipartite graph, identify an alternating path (which is explicitly guided), and apply the algorithm mechanically. The context is simple, the alternating path is short (3 arcs), and part (iv) requires minimal adjustment. This is easier than average as it's highly structured with no problem-solving insight required. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation |
| Answer | Marks | Guidance |
|---|---|---|
| For \(A1\) or \(A2\) or both joined to \(G, P\) and \(R\); \(B1\) or \(B2\) or both joined to \(G, T, W\) and \(Y\); and \(C1\) or \(C2\) or both joined to \(P, W\) and \(Y\) | M1 | For completing the matching requirements |
| For both \(A1\) and \(A2\) joined to \(G, P\) and \(R\); both \(B1\) and \(B2\) joined to \(G, T, W\) and \(Y\); and both \(C1\) and \(C2\) joined to \(P, W\) and \(Y\) | A1 | For a correct complete matching |
| Answer | Marks | Guidance |
|---|---|---|
| \(A1\) paired with \(G\) and \(A2\) with \(P\), or vice versa; \(B1\) paired with \(T\) and \(B2\) with \(W\), or vice versa; one of \(C1, C2\) paired with \(Y\) and the other left unpaired | B1 | For this matching (may use \(G, R\), etc.) |
| Answer | Marks | Guidance |
|---|---|---|
| \(R - A2 - P - C2\) or in reverse; Accept \(R - A - P - C\) or in reverse | M1 | For a valid alternating path for their diagram (need not be minimum) |
| A1 | For this alternating path | |
| Amanda gets green and red; Ben gets turquoise and white; Carrie gets yellow and pink | B1 | For this matching (may use \(G, R\), etc.) |
| Answer | Marks | Guidance |
|---|---|---|
| Amanda gets pink and red; Ben gets green and turquoise; Carrie gets white and yellow | B1 | For this matching (may use \(G, R\), etc.) |
**(i)**
For $A1$ or $A2$ or both joined to $G, P$ and $R$; $B1$ or $B2$ or both joined to $G, T, W$ and $Y$; and $C1$ or $C2$ or both joined to $P, W$ and $Y$ | M1 | For completing the matching requirements
For both $A1$ and $A2$ joined to $G, P$ and $R$; both $B1$ and $B2$ joined to $G, T, W$ and $Y$; and both $C1$ and $C2$ joined to $P, W$ and $Y$ | A1 | For a correct complete matching
**(ii)**
$A1$ paired with $G$ and $A2$ with $P$, or vice versa; $B1$ paired with $T$ and $B2$ with $W$, or vice versa; one of $C1, C2$ paired with $Y$ and the other left unpaired | B1 | For this matching (may use $G, R$, etc.)
**(iii)**
$R - A2 - P - C2$ or in reverse; Accept $R - A - P - C$ or in reverse | M1 | For a valid alternating path for their diagram (need not be minimum)
| A1 | For this alternating path
Amanda gets green and red; Ben gets turquoise and white; Carrie gets yellow and pink | B1 | For this matching (may use $G, R$, etc.)
**(iv)**
Amanda gets pink and red; Ben gets green and turquoise; Carrie gets white and yellow | B1 | For this matching (may use $G, R$, etc.)
---1 Answer this question on the insert provided.
Mrs Price has bought six T shirts for her children. Each child is to have two shirts.\\
Amanda would like the green shirt, the pink shirt or the red shirt.\\
Ben would like the green shirt, the turquoise shirt, the white shirt or the yellow shirt.\\
Carrie would like the pink shirt, the white shirt or the yellow shirt.\\
(i) On the first diagram in the insert, draw a bipartite graph to show which child would like which shirt. The children are represented as $A 1 , A 2 , B 1 , B 2 , C 1$ and $C 2$ and the shirts as $G , P , R , T , W$ and $Y$.
Initially, Mrs Price puts aside the green shirt and the pink shirt for Amanda, the turquoise shirt and the white shirt for Ben and the yellow shirt for Carrie.\\
(ii) Show this incomplete matching on the second diagram in the insert.\\
(iii) Write down an alternating path consisting of three arcs to enable the matching to be improved. Use your alternating path to match the children to the shirts.\\
(iv) Amanda decides that she does not like the green shirt after all. Which shirts should each child have now?
\hfill \mbox{\textit{OCR D2 2006 Q1 [7]}}