| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| 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 exercise on the matching algorithm from D1, requiring mechanical application of alternating paths with no novel insight. The question explicitly guides students through each step (find this path, explain why no complete matching, add an edge, find another path), making it easier than average A-level questions which typically require more independent problem-solving. |
| Spec | 7.02q Adjacency matrix: and weighted matrix representation |
| Answer | Marks |
|---|---|
| \(G - 3 = J - 4 = L - 5\) change stateu: \(G = 3 = J + 4 = L - 5\) | M1, A1 |
| Improved matching: \(E = 2, G = 3, J = 4, L = 5\) | B1 (3) |
| Answer | Marks |
|---|---|
| e.g. George and Y: when may both only be assigned to 3 | B1 (1) |
| Answer | Marks |
|---|---|
| \(Y - 3 = G - 2 = E - 4 = J - 1\) change stateu: \(Y = 3 - G = 2 - E = 4 - J = 1\) | M1, A1 |
| Complete matching: \(E = 4, G = 2, J = 1, L = 5, Y = 3\) | A1 (3) |
## 2(a)
| $G - 3 = J - 4 = L - 5$ change stateu: $G = 3 = J + 4 = L - 5$ | M1, A1 |
| Improved matching: $E = 2, G = 3, J = 4, L = 5$ | B1 (3) |
## 2(b)
| e.g. George and Y: when may both only be assigned to 3 | B1 (1) |
## 2(c)
| $Y - 3 = G - 2 = E - 4 = J - 1$ change stateu: $Y = 3 - G = 2 - E = 4 - J = 1$ | M1, A1 |
| Complete matching: $E = 4, G = 2, J = 1, L = 5, Y = 3$ | A1 (3) |\includegraphics{figure_1} \includegraphics{figure_2}
Figure 1 shows the possible allocations of five people, Ellen, George, Jo, Lydia and Yi Wen to five tasks, 1, 2, 3, 4 and 5.
Figure 2 shows an initial matching.
\begin{enumerate}[label=(\alph*)]
\item Find an alternating path linking George with 5. List the resulting improved matching this gives. (3)
\item Explain why it is not possible to find a complete matching. (1)
\end{enumerate}
George now has task 2 added to his possible allocation.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item Using the improved matching found in part (a) as the new initial matching, find an alternating path linking Yi Wen with task 1 to find a complete matching. List the complete matching. (3)
\end{enumerate}
(Total 7 marks)
\hfill \mbox{\textit{Edexcel D1 2007 Q2}}