| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2005 |
| Session | June |
| Marks | 13 |
| 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 bipartite matching algorithms (drawing bipartite graphs, finding alternating paths, and Hungarian algorithm setup) with clear step-by-step instructions. The question requires only routine application of well-defined algorithms taught in D2, with no novel problem-solving or insight needed. While it has multiple parts, each part is straightforward algorithmic execution. |
| Spec | 7.02g Eulerian graphs: vertex degrees and traversability7.02h Hamiltonian paths: and cycles |
| \multirow{2}{*}{} | Character | ||||
| Fire Chief | Gardener | Handyman | Juggler | King | |
| Adam | 4 | 9 | 7 | 0 | 7 |
| Bex | 6 | 8 | 3 | 8 | 0 |
| Chris | 7 | 4 | 5 | 2 | 7 |
| Denny | 6 | 6 | 2 | 7 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct bipartite graph drawn | B1 | For a correct bipartite graph |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Denny cannot have a song that she has chosen | B1 | For this reasoning |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(5\ C\ 3\ D\) | M1 | Follow through their bipartite graph, if possible. For this path (or in reverse), not longer path |
| \(A\)-1, \(B\)-2, \(C\)-5, \(D\)-3, \(E\)-4 | A1 | If shown on diagram, path must be obvious. For this matching, not alternative |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(A\)-2, \(B\)-4, \(C\)-5, \(D\)-1, \(E\)-3 | B1 | For a different matching from their bipartite graph |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Hungarian algorithm finds minimum cost allocation, need to subtract each score from 10 to convert maximising into minimising | B1 | For a valid reference to maximising/minimising |
| Dummy row is needed to make a square matrix | B1 | For 'make it square' or equivalent |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Initial matrix set up with rows \(A,B,C,D,X\) and columns \(F,G,H,J,K\); dummy row \(X = 0,0,0,0,0\) | B1 | For setting up initial matrix as described |
| Reduce rows: correct reduced matrix | M1 | For reducing rows (to give a 0 in each row) |
| Correct reduced matrix | A1 | For correct reduced matrix (cao) |
| Cover 0's using four lines | M1 | For covering 0's using minimum number of lines |
| Correct augmented matrix | A1 | For correct augmented matrix (cao) |
| Complete matching: \(A\)-\(G\), \(B\)-\(J\), \(C\)-\(K\), \(D\)-\(F\) | B1 | For correct matching (listed) |
# Question 2:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct bipartite graph drawn | B1 | For a correct bipartite graph |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Denny cannot have a song that she has chosen | B1 | For this reasoning |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| $5\ C\ 3\ D$ | M1 | Follow through their bipartite graph, if possible. For this path (or in reverse), not longer path |
| $A$-1, $B$-2, $C$-5, $D$-3, $E$-4 | A1 | If shown on diagram, path must be obvious. For this matching, not alternative |
## Part (iv)
| Answer | Mark | Guidance |
|--------|------|----------|
| $A$-2, $B$-4, $C$-5, $D$-1, $E$-3 | B1 | For a different matching from their bipartite graph |
## Part (v)
| Answer | Mark | Guidance |
|--------|------|----------|
| Hungarian algorithm finds minimum cost allocation, need to subtract each score from 10 to convert maximising into minimising | B1 | For a valid reference to maximising/minimising |
| Dummy row is needed to make a square matrix | B1 | For 'make it square' or equivalent |
## Part (vi)
| Answer | Mark | Guidance |
|--------|------|----------|
| Initial matrix set up with rows $A,B,C,D,X$ and columns $F,G,H,J,K$; dummy row $X = 0,0,0,0,0$ | B1 | For setting up initial matrix as described |
| Reduce rows: correct reduced matrix | M1 | For reducing rows (to give a 0 in each row) |
| Correct reduced matrix | A1 | For correct reduced matrix (cao) |
| Cover 0's using four lines | M1 | For covering 0's using minimum number of lines |
| Correct augmented matrix | A1 | For correct augmented matrix (cao) |
| Complete matching: $A$-$G$, $B$-$J$, $C$-$K$, $D$-$F$ | B1 | For correct matching (listed) |
---2 A talent contest has five contestants. In the first round of the contest each contestant must sing a song chosen from a list. No two contestants may sing the same song.
Adam (A) chooses to sing either song 1 or song 2; Bex (B) chooses 2 or 4; Chris (C) chooses 3 or 5; Denny (D) chooses 1 or 3; Emma (E) chooses 3 or 4.
\begin{enumerate}[label=(\roman*)]
\item Draw a bipartite graph to show this information. Put the contestants (A, B, C, D and E) on the left hand side and the songs ( $1,2,3,4$ and 5 ) on the right hand side.
The contest organisers propose to give Adam song 1, Bex song 2 and Chris song 3.
\item Explain why this would not be a satisfactory way to allocate the songs.
\item Construct the shortest possible alternating path that starts from song 5 and brings Denny (D) into the allocation. Hence write down an allocation in which each of the five contestants is given a song that they chose.
\item Find a different allocation in which each of the five contestants is given a song that they chose.
Emma is knocked out of the contest after the first round. In the second round the four remaining contestants have to act in a short play. They will each act a different character in the play, chosen from a list of five characters.
The table below shows how suitable each contestant is for each character as a score out of 10 (where 0 means that the contestant is completely unsuitable and 10 means that they are perfect to play that character).
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
\multirow{2}{*}{} & \multicolumn{5}{|c|}{Character} \\
\hline
& Fire Chief & Gardener & Handyman & Juggler & King \\
\hline
Adam & 4 & 9 & 7 & 0 & 7 \\
\hline
Bex & 6 & 8 & 3 & 8 & 0 \\
\hline
Chris & 7 & 4 & 5 & 2 & 7 \\
\hline
Denny & 6 & 6 & 2 & 7 & 1 \\
\hline
\end{tabular}
\end{center}
The Hungarian Algorithm is to be used to find the matching with the greatest total score. Before the Hungarian Algorithm can be used, each score is subtracted from 10 and then a dummy row of zeroes is added at the bottom of the table.
\item Explain why the scores could not be used as given in the table and explain why a dummy row is needed.
\item Apply the Hungarian Algorithm, showing your working carefully, to match the contestants to characters.
\end{enumerate}
\hfill \mbox{\textit{OCR D2 2005 Q2 [13]}}