| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | June |
| 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 standard textbook application of the maximum matching algorithm with clear step-by-step instructions. Students follow a prescribed procedure (finding alternating paths, improving matchings) with the bipartite graph provided. The reasoning required is algorithmic rather than creative, making it easier than average A-level questions. |
| Spec | 7.02q Adjacency matrix: and weighted matrix representation |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: \(H - 2 = M - 5 = R - 4\) change status to give | M1 A1 | (3) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: \(C = 3\) (E unmatched) \(H = 2\) \(M = 5\) \(R = 4\) \(S = 1\) | A1 | (3) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: e.g. C is the only person who can do 3 and the only person who can do 6; e.g \(E - 5 = M - 2 = H - 1 = S - 3 = C - 6\) change status to give | M1 A1 | (3) |
**Part (a)**
Answer: $H - 2 = M - 5 = R - 4$ change status to give | M1 A1 | (3) | Path from H to 4. 1A1: correct path and change status. 2A1: CAO must follow from correct path.
**Part (b)**
Answer: $C = 3$ (E unmatched) $H = 2$ $M = 5$ $R = 4$ $S = 1$ | A1 | (3) | 1B1: CAO or e.g reference to E 5 M 2 H 1 S.
**Part (c)**
Answer: e.g. C is the only person who can do 3 and the only person who can do 6; e.g $E - 5 = M - 2 = H - 1 = S - 3 = C - 6$ change status to give | M1 A1 | (3) | Path from E to 6. 1A1: CAO do not penalise lack of change status a second time. 2A1: CAO must follow from a correct path. Answer: $C = 6$ $E = 5$ $H = 1$ $M = 2$ $R = 4$ $S = 3$
---3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-3_755_624_283_283}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-3_750_620_285_1146}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Figure 1 shows the possible allocations of six workers, Charlotte (C), Eleanor (E), Harry (H), Matt (M), Rachel (R) and Simon (S) to six tasks, 1, 2, 3, 4, 5 and 6.
Figure 2 shows an initial matching.
\begin{enumerate}[label=(\alph*)]
\item List an alternating path, starting at H and ending at 4 . Use your path to find an improved matching. List your improved matching.
\item Explain why it is not possible to find a complete matching.
Simon (S) now has task 3 added to his possible allocation.
\item Taking the improved matching found in (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating path you use and your complete matching.\\
(3)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2009 Q3 [7]}}