| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| 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 with clear instructions. Students follow a mechanical procedure to find alternating paths from the given initial matching. The algorithm is algorithmic rather than requiring problem-solving insight, and finding a second solution involves simply choosing a different alternating path. This is routine D1 content, easier than average A-level questions. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02c Graph terminology: walk, trail, path, cycle, route |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Path from G to 4 identified, e.g. \(G-3=C-2=F-1=D-4\) or \(G-5=E-4\) or \(G-5=E-1=D-4\) | M1, 1A1 | Path from G to 4 or vice versa; chosen path clear |
| Change status step shown/stated, giving matchings: (i) C=2, D=4, E=5, F=1, G=3; (ii) C=3, D=1, E=4, F=2, G=5; (iii) C=3, D=4, E=1, F=2, G=5 | 2A1 | Only accept 'change status', 'c.s.', or sight of connectives being swapped |
| Correct matching table shown for chosen path | 3A1 (4) | CAO must ft from stated path, diagram ok |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| A second path from G to 4 (or vice versa) given with change status and correct resulting matching | M1, 1A1, 2A1 (3) | CAO including change status stated or shown; chosen path clear; CAO must ft from stated paths |
## Question 2:
### Part (a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Path from G to 4 identified, e.g. $G-3=C-2=F-1=D-4$ or $G-5=E-4$ or $G-5=E-1=D-4$ | M1, 1A1 | Path from G to 4 or vice versa; chosen path clear |
| Change status step shown/stated, giving matchings: (i) C=2, D=4, E=5, F=1, G=3; (ii) C=3, D=1, E=4, F=2, G=5; (iii) C=3, D=4, E=1, F=2, G=5 | 2A1 | Only accept 'change status', 'c.s.', or sight of connectives being swapped |
| Correct matching table shown for chosen path | 3A1 **(4)** | CAO must ft from stated path, diagram ok |
### Part (b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| A second path from G to 4 (or vice versa) given with change status and correct resulting matching | M1, 1A1, 2A1 **(3)** | CAO including change status stated or shown; chosen path clear; CAO must ft from stated paths |
---2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-3_474_593_264_372}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-3_474_588_267_1096}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Figure 1 shows the possible allocations of five workers, Charles (C), David (D), Ellie (E), Freya (F) and Georgi (G), to five tasks, 1, 2, 3, 4 and 5.
Figure 2 shows an initial matching.
\begin{enumerate}[label=(\alph*)]
\item Starting from this initial matching, use the maximum matching algorithm to find a complete matching. State clearly the alternating path that you use and list your final matching.\\
(4)
\item Find another solution starting from the given initial matching. You should state the alternating path and list the complete matching it gives.\\
(3)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2012 Q2 [7]}}