| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2017 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Moderate -0.8 This is a standard textbook application of the maximum matching algorithm in bipartite graphs. Part (a) is simple recall (bipartite graph), part (b) follows a routine algorithmic procedure taught in D1, and parts (c)-(d) require minimal insight once the algorithm is applied. The question is structured with clear guidance and requires no novel problem-solving beyond executing a well-practiced algorithm. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Scheme | Marks | Guidance |
| (a) Bipartite (graph) | B1 | (1) |
| (b) Alternating path: \(B – 5 – C – 4 – E – 1 – D – 3 – A – 2\) or \(B – 5 – C – 6 – F – 4 – E – 1 – D – 3 – A – 2\); Change status: \(B = 5 – C = 4 – E = 1 – D = 3 – A = 2\) or \(B = 5 – C = 6 – F = 4 – E = 1 – D = 3 – A = 2\) | M1 | An alternating path (e.g. letter 1st set – number 2nd set – letter 1st set – …) from B to 2 (or viceversa) |
| (c) Complete matching: \(A = 2, B = 5, C = 4, D = 3, E = 1, F = 6\) or \(A = 2, B = 5, C = 6, D = 3, E = 1, F = 4\) | A1 | (3) |
| (c) Either \(A = 2, B = 5, C = 4, D = 3, E = 1, F = 6\) or \(A = 2, B = 5, C = 6, D = 3, E = 1, F = 4\) | B1 | (1) |
| (d) Worker A must do task 2 so D must do task 3. Hence E must do task 1 and therefore B must do task 5. Workers C and F can both be allocated to either tasks 4 or 6. Therefore there are two, and only two, possible complete matchings. | B1 B1 | (2) |
| 7 marks |
| Answer/Scheme | Marks | Guidance |
|---|---|---|
| (a) Bipartite (graph) | B1 | (1) |
| (b) Alternating path: $B – 5 – C – 4 – E – 1 – D – 3 – A – 2$ or $B – 5 – C – 6 – F – 4 – E – 1 – D – 3 – A – 2$; Change status: $B = 5 – C = 4 – E = 1 – D = 3 – A = 2$ or $B = 5 – C = 6 – F = 4 – E = 1 – D = 3 – A = 2$ | M1 | An alternating path (e.g. letter 1st set – number 2nd set – letter 1st set – …) from B to 2 (or viceversa) |
| (c) Complete matching: $A = 2, B = 5, C = 4, D = 3, E = 1, F = 6$ or $A = 2, B = 5, C = 6, D = 3, E = 1, F = 4$ | A1 | (3) |
| (c) Either $A = 2, B = 5, C = 4, D = 3, E = 1, F = 6$ or $A = 2, B = 5, C = 6, D = 3, E = 1, F = 4$ | B1 | (1) |
| (d) Worker A must do task 2 so D must do task 3. Hence E must do task 1 and therefore B must do task 5. Workers C and F can both be allocated to either tasks 4 or 6. Therefore there are two, and only two, possible complete matchings. | B1 B1 | (2) |
| | **7 marks** | |
**Notes for Question 3:**
a1B1: CAO – but be charitable on spelling, award if phonetically close
b1M1: An alternating path (e.g. letter 1st set – number 2nd set – letter 1st set – …) from B to 2 (or viceversa)
b1A1: CAO – a correct path including change status either stated (only accept 'change (of) status' or 'c.s' but not, e.g. 'change state') or shown (all symbols e.g. (…- … = … - …) interchanged (… = …- … - …))
b2A1: CAO (complete matching) must follow from the correct stated path. Accept on a clear diagram (with six arcs only)
c1b1: CAO – different from the one given in (b) – if an incorrect matching is given in (b) then award this mark for either correct matching
d1B1: CAO – explicitly stating that workers A, B, D and E can only do activities 2, 5, 3 and 1 respectively
d2B1: CAO – explicitly stating that workers C and F can both be allocated to the two tasks of 4 and 6
---3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{39bbf9e2-efa7-4f3e-a22d-227f83184abd-04_604_506_239_406}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{39bbf9e2-efa7-4f3e-a22d-227f83184abd-04_608_511_242_1146}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Figure 1 shows the possible allocations of six workers, Andrea (A), Baasim (B), Charlie (C), Deirdre (D), Ean (E) and Fen-Fang (F), to six tasks, 1, 2, 3, 4, 5 and 6.
\begin{enumerate}[label=(\alph*)]
\item Write down the technical name given to the type of graph shown in Figure 1.\\
(1)
Figure 2 shows an initial matching.
\item Starting from the initial matching, use the maximum matching algorithm to find a complete matching. You must list the alternating path you used and state your complete matching.
\item State a different complete matching from the one found in (b).
\item By considering the workers who must be allocated to particular tasks, explain why there are exactly two different complete matchings.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2017 Q3 [7]}}