| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| 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. While it has multiple parts, each step is algorithmic and routine for students who have practiced this topic. The reasoning in parts (b) and (c) requires understanding of matching theory but is straightforward once the algorithm is applied. |
| Spec | 7.02j Isomorphism: of graphs, degree sequences7.02r Graph modelling: model and solve problems using graphs |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | Alternating path: \(D - 1 = C - 6\) or \(D = 1 - C = 6\). Improved matching: \(A=4, (B \text{ unmatched}), C=6, D=1, E=3, F=2\) | M1 A1 |
| (b) | Tasks 4 and 5 can only be done by A. B can only do 2, E can only do 3, and F can only do 2 or 3. So there are three workers to match to just two tasks. | B1 |
| (c) | E to 4 should be chosen. e.g. If E to 4 would release A to 5. e.g. If A is retained then tasks 4 and 5 can still only be done by A | M1 A1 |
| (d) | Alternating path: \(B - 2 = F - 3 = E - 4 = A - 5\). Change status: \(B = 2, F = 3, E = 4, A = 5\). Complete matching: \(A=5, B=2, C=6, D=1, E=4, F=3\) | M1 A1 A1 |
(a) | Alternating path: $D - 1 = C - 6$ or $D = 1 - C = 6$. Improved matching: $A=4, (B \text{ unmatched}), C=6, D=1, E=3, F=2$ | M1 A1 | (2) |
(b) | Tasks 4 and 5 can only be done by A. B can only do 2, E can only do 3, and F can only do 2 or 3. So there are three workers to match to just two tasks. | B1 | (1) |
(c) | E to 4 should be chosen. e.g. If E to 4 would release A to 5. e.g. If A is retained then tasks 4 and 5 can still only be done by A | M1 A1 | (2) |
(d) | Alternating path: $B - 2 = F - 3 = E - 4 = A - 5$. Change status: $B = 2, F = 3, E = 4, A = 5$. Complete matching: $A=5, B=2, C=6, D=1, E=4, F=3$ | M1 A1 A1 | (3) |
**Total: 8 marks**
---1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{a3ca2743-2311-4225-8b78-dcd5eb592704-2_741_558_370_372}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{a3ca2743-2311-4225-8b78-dcd5eb592704-2_734_561_374_1114}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Figure 1 shows the possible allocations of six workers, $\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 state your improved matching.
\item Explain why it is not possible to find a complete matching.
Now, exactly one worker may be trained so that a complete matching becomes possible.\\
Either worker A can be trained to do task 1 or worker E can be trained to do task 4.
\item Decide which worker, A or E , should be trained. Give a reason for your answer.
You may now assume that the worker you identified in (c) has been trained.
\item Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You must list the alternating path used and state your complete matching.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2016 Q1 [8]}}