| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | Specimen |
| 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 to find alternating paths and improve matchings. While it involves multiple parts and careful bookkeeping, it's a routine algorithmic question with no novel problem-solving required—students who have practiced this algorithm will find it straightforward and methodical. |
| Spec | 7.02q Adjacency matrix: and weighted matrix representation |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| e.g. \(G-3=E-2=A-4=S-6\); Change status \(G=3-E=2-A=4-S=6\) | M1, A1 | 1M1: Path from G to 6 or 1; 1A1: CAO including change status (stated or shown), chosen path clear |
| Improved matching: \(A=4\), (C unmatched), \(E=2\), \(G=3\), \(J=5\), \(S=6\) | A1 | 3 marks; 2A1: CAO must ft from stated path, diagram ok |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| e.g. Both C and J can only be matched to 5; Both 1 and 6 can only be done by S | B2, 1, 0 | 2 marks; 1B1: Correct answer, may be imprecise or muddled (bod gets B1) — all relevant nodes should be referred to and must be correct, but condone one (genuine) slip; 2B1: Good, clear, correct answer |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(C-5=J-4=A-2=E-6=S-1\); Change status \(C=5-J=4-A=2-E=6-S=1\) | M1, A1 | 1M1: Path from C to 1 or 6 (whichever not used before); 1A1: CAO including change status (stated or shown), chosen path clear (don't penalise change status twice) |
| Complete matching: \(A=2\), \(C=5\), \(E=6\), \(G=3\), \(J=4\), \(S=1\) | A1 | 3 marks; 2A1: CAO must ft from stated path, diagram ok |
# Question 5:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. $G-3=E-2=A-4=S-6$; Change status $G=3-E=2-A=4-S=6$ | M1, A1 | 1M1: Path from G to 6 or 1; 1A1: CAO including change status (stated or shown), chosen path clear |
| Improved matching: $A=4$, (C unmatched), $E=2$, $G=3$, $J=5$, $S=6$ | A1 | **3 marks**; 2A1: CAO must ft from stated path, diagram ok |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. Both C and J can only be matched to 5; Both 1 and 6 can only be done by S | B2, 1, 0 | **2 marks**; 1B1: Correct answer, may be imprecise or muddled (bod gets B1) — all relevant nodes should be referred to and must be correct, but condone one (genuine) slip; 2B1: Good, clear, correct answer |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $C-5=J-4=A-2=E-6=S-1$; Change status $C=5-J=4-A=2-E=6-S=1$ | M1, A1 | 1M1: Path from C to 1 or 6 (whichever not used before); 1A1: CAO including change status (stated or shown), chosen path clear (don't penalise change status twice) |
| Complete matching: $A=2$, $C=5$, $E=6$, $G=3$, $J=4$, $S=1$ | A1 | **3 marks**; 2A1: CAO must ft from stated path, diagram ok |
**Alt (a):** $G-3=E-2=A-4=S-1$ c.s. $G=3-E=2-A=4-S=1$; $A=4$, (C unmatched), $E=2$, $G=3$, $J=5$, $S=1$
**Alt (c):** $C-5=J-4=A-2=E-6$ c.s. $C=5-J=4-A=2-E=6$; $A=2$, $C=5$, $E=6$, $G=3$, $J=4$, $S=1$
**Total: 8 marks**5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5fa867a2-0a3d-4f0b-9f9c-15584f2be5c0-06_730_597_269_315}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5fa867a2-0a3d-4f0b-9f9c-15584f2be5c0-06_722_583_274_1160}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
Figure 3 shows the possible allocations of six people, Amelia, Charlie, Ellie, Gemma, Jimmy and Saskia, to six tasks, 1, 2, 3, 4, 5 and 6.\\
Figure 4 shows an initial matching.
\begin{enumerate}[label=(\alph*)]
\item Use the maximum matching algorithm once to find an improved matching. You must state the alternating path used and your improved matching.
\item Explain why a complete matching is not possible.
After training, Jimmy can be assigned to tasks 4 or 5 and Ellie to tasks 2, 3, 5 or 6.
\item Starting with your current maximal matching, use the maximum matching algorithm to obtain a complete matching. You must state the alternating path used and your final matching.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2013 Q5 [8]}}