| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Easy -1.2 This is a standard application of the maximum matching algorithm from D1, requiring mechanical execution of a well-defined procedure. While it has multiple parts and requires careful bookkeeping, it involves no problem-solving insight—students simply follow the alternating path algorithm they've been taught. The explanation in part (b) requires recognizing a standard impossibility condition (vertex with no available edges), which is routine for this topic. |
| Spec | 7.02r Graph modelling: model and solve problems using graphs |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| e.g. \(G - 3 = E - 2 = A - 4 = S - 6\)<br>Change status \(G = 3 - E = 2 - A = 4 - S = 6\)<br><br>Improved matching<br>\(A = 4\) (C unmatched) \(E = 2\) \(G = 3\) \(J = 5\) \(S = 6\) | M1 A1 A1 | M1: Path from G to 6 or 1<br>1A1: CAO including change status (stated or shown), chosen path clear.<br>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<br>Both 1 and 6 can only be done by S | B2, 1, 0 | 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.<br>2B1: Good, clear, correct answer. |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(C - 5 = J - 4 = A - 2 = E - 6 = S - 1\)<br>Change status \(C = 5 - J = 4 - A = 2 - E = 6 - S = 1\)<br><br>Complete matching<br>\(A = 2\) \(C = 5\) \(E = 6\) \(G = 3\) \(J = 4\) \(S = 1\) | M1 A1 A1 | M1: Path from C to 1 or 6 [whichever they didn't use before.]<br>1A1: CAO including change status (stated or shown), chosen path clear. (Don't penalise change status twice.)<br>2A1: CAO must ft from stated path, diagram ok |
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. $G - 3 = E - 2 = A - 4 = S - 6$<br>Change status $G = 3 - E = 2 - A = 4 - S = 6$<br><br>Improved matching<br>$A = 4$ (C unmatched) $E = 2$ $G = 3$ $J = 5$ $S = 6$ | M1 A1 A1 | M1: Path from G to 6 or 1<br>1A1: CAO including change status (stated or shown), chosen path clear.<br>2A1: CAO must ft from stated path, diagram ok |
**Total: 3 marks**
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. Both C and J can only be matched to 5<br>Both 1 and 6 can only be done by S | B2, 1, 0 | 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.<br>2B1: Good, clear, correct answer. |
**Total: 2 marks**
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $C - 5 = J - 4 = A - 2 = E - 6 = S - 1$<br>Change status $C = 5 - J = 4 - A = 2 - E = 6 - S = 1$<br><br>Complete matching<br>$A = 2$ $C = 5$ $E = 6$ $G = 3$ $J = 4$ $S = 1$ | M1 A1 A1 | M1: Path from C to 1 or 6 [whichever they didn't use before.]<br>1A1: CAO including change status (stated or shown), chosen path clear. (Don't penalise change status twice.)<br>2A1: CAO must ft from stated path, diagram ok |
**Total: 3 marks**
**Alternative solutions given in scheme for both (a) and (c).**
**Grand Total for Q5: 8 marks**
---\includegraphics{figure_3}
\includegraphics{figure_4}
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.
[3]
\item Explain why a complete matching is not possible.
[2]
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.
[3]
\end{enumerate}
(Total 8 marks)
\hfill \mbox{\textit{Edexcel D1 2010 Q5 [8]}}