| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Moderate -0.3 This is a standard application of the maximum matching algorithm from D1, requiring students to follow a well-defined procedure (finding alternating paths) with minimal problem-solving insight. The algorithm is algorithmic rather than conceptual, and part (b) requires only basic observation about why complete matching fails. Slightly easier than average due to the procedural nature and clear structure. |
| Spec | 7.02q Adjacency matrix: and weighted matrix representation |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Alternating path \(B-3=A-5\), change status \(B=3-A=5\) | M1 A1 | Path from B to 5; Correct path including change status |
| \(A=5 \quad B=3 \quad C=2 \quad D=1 \quad E=6 \quad F\) unmatched | A1 | CAO my matching, may be drawn but if so 5 lines only and clear |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| e.g. C is the only person able to do 2 and the only person able to do 4. Or D, E and F between them can only be allocated to 1 and 6 | B2, 1, 0 | Close, a correct relevant, productive statement bod generous; A good clear answer generous |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Alternating path \(F-6=E-1=D-2=C-4\), change status \(F=6-E=1-D=2-C=4\) | M1 A1 | Path from F to 4. No ft; Correct path, penalise lack of change status once only |
| \(A=5 \quad B=3 \quad C=4 \quad D=2 \quad E=1 \quad F=6\) | A1 | CAO may be drawn but if so 6 lines only and clear |
# Question 4:
## Part (a)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Alternating path $B-3=A-5$, change status $B=3-A=5$ | M1 A1 | Path from B to 5; Correct path including change status |
| $A=5 \quad B=3 \quad C=2 \quad D=1 \quad E=6 \quad F$ unmatched | A1 | CAO my matching, may be drawn but if so 5 lines only and clear |
## Part (b)
| Answer/Working | Marks | Guidance |
|---|---|---|
| e.g. C is the only person able to do 2 and the only person able to do 4. Or D, E and F between them can only be allocated to 1 and 6 | B2, 1, 0 | Close, a correct relevant, productive statement bod generous; A good clear answer generous |
## Part (c)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Alternating path $F-6=E-1=D-2=C-4$, change status $F=6-E=1-D=2-C=4$ | M1 A1 | Path from F to 4. No ft; Correct path, penalise lack of change status once only |
| $A=5 \quad B=3 \quad C=4 \quad D=2 \quad E=1 \quad F=6$ | A1 | CAO may be drawn but if so 6 lines only and clear |
---4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{ef029462-ffed-4cdf-87bc-56c8a13d671f-4_540_626_244_316}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{ef029462-ffed-4cdf-87bc-56c8a13d671f-4_531_613_246_1128}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Figure 1 shows the possible allocations of six people, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$ and F , to six tasks, 1, 2, 3, 4, 5 and 6.\\
Figure 2 shows an initial matching.
\begin{enumerate}[label=(\alph*)]
\item Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You must list the alternating path used, and your improved matching.
\item Explain why it is not possible to find a complete matching.
D now has task 2 added to their possible allocation.
\item Using the improved matching found in part (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. You must list the alternating path used and your complete matching.\\
(3)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2009 Q4 [8]}}