| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Moderate -0.8 This is a standard application of the maximum matching algorithm from D1, requiring students to follow a well-defined procedure: identify why complete matching fails, find alternating paths, and apply the algorithm step-by-step. While it has multiple parts, each step follows textbook methods with no novel problem-solving or insight required—easier than average A-level maths. |
| Spec | 7.02j Isomorphism: of graphs, degree sequences7.02r Graph modelling: model and solve problems using graphs7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| e.g. B can only do task 2 and F can only do task 6 therefore E will have no allocation as E can only do tasks 2 and 6 | B1 (1) | |
| C – 1 = A – 5 = D – 4 | B1 B1 (2) | |
| A = 3, B = 2, C = 1, D = 5, E = 6 (F unmatched) A = 5, B = 2, C =1, D = 4, E = 6 (F unmatched) | B1 B1 (2) | |
| Alternating path: F – 6 = E – 2 = B – 5 = D – 4 or F – 6 = E – 2 = B – 5 = A – 3 | M1 | |
| Change status: F = 6 – E = 2 – B = 5 – D = 4 or F = 6 – E = 2 – B = 5 – A = 3 | A1 (3) | |
| Complete matching: A = 3, B = 5, C = 1, D = 4, E = 2, F = 6 | A1 | |
| 8 marks |
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. B can only do task 2 and F can only do task 6 therefore E will have no allocation as E can only do tasks 2 and 6 | B1 (1) | |
| C – 1 = A – 5 = D – 4 | B1 B1 (2) | |
| A = 3, B = 2, C = 1, D = 5, E = 6 (F unmatched) A = 5, B = 2, C =1, D = 4, E = 6 (F unmatched) | B1 B1 (2) | |
| Alternating path: F – 6 = E – 2 = B – 5 = D – 4 or F – 6 = E – 2 = B – 5 = A – 3 | M1 | |
| Change status: F = 6 – E = 2 – B = 5 – D = 4 or F = 6 – E = 2 – B = 5 – A = 3 | A1 (3) | |
| Complete matching: A = 3, B = 5, C = 1, D = 4, E = 2, F = 6 | A1 | |
| | 8 marks | |
**Notes for Question 2:**
- a1B1: CAO – must be a completely correct statement.
- b1B1: CAO (C – 1 = A – 3).
- b2B1: CAO (C – 1 = A – 5 = D – 4).
- c1B1: CAO (A = 3, B = 2, C = 1, D = 5, E = 6).
- c2B1: CAO (A = 5, B = 2, C =1, D = 4, E = 6).
- d1M1: An alternating path from F to either 3 or 4 (or vice-versa).
- d1A1: CAO – a correct path including change status either stated (only accept 'change (of) status' or 'c.s.') or shown. Chosen path clear.
- d2A1: CAO must follow from the correct stated path. Accept on a clear diagram (with six arcs only).
---2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{00abfcc0-63b3-4784-a4b5-06aba234068c-3_616_561_278_356}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{00abfcc0-63b3-4784-a4b5-06aba234068c-3_606_552_285_1146}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Figure 1 shows the possible allocations of six workers, Amrit (A), Bernard (B), Cameron (C), David (D), Emily (E) and Francis (F), to six tasks, 1, 2, 3, 4, 5 and 6
\begin{enumerate}[label=(\alph*)]
\item Explain why it is not possible to find a complete matching.
Figure 2 shows an initial matching. Starting from this initial matching,
\item find the two alternating paths that start at C .
\item List the two improved matchings generated by using the two alternating paths found in (b).
After training, task 5 is added to Bernard's possible allocation.\\
Starting from either of the two improved matchings found in (c),
\item use the maximum matching algorithm to obtain a complete matching. You must list the additional alternating path that you use, and state the complete matching.\\
(3)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2015 Q2 [8]}}