| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Moderate -0.5 This is a standard application of the maximum matching algorithm from D1, requiring students to follow a well-defined algorithmic procedure to find alternating paths and improve matchings. While it involves multiple parts and careful bookkeeping, it's a routine textbook exercise with no novel problem-solving or insight required—students simply execute the algorithm they've been taught. The question is slightly easier than average A-level maths because Decision Maths algorithms are typically more procedural than analytical. |
| 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 |
**Question 1 Notes:**
- a1M1: An alternating path from C to 6 or vice versa
- a1A1: CAO – a correct path including change status (stated or shown) with all symbols interchanged
- a2A1: CAO must follow from correct stated path. Accept on clear diagram (with five arcs only)
- b1B1: A good, clear, complete, correct answer (all relevant nodes must be referred to and must be correct)
- c1M1: An alternating path from A to 3 or vice versa
- c1A1: CAO including change status (stated or shown), chosen path clear
- c2A1: CAO must follow from two correct stated paths (so both previous M marks must have been awarded). Accept on clear diagram (with six arcs only)1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-02_533_551_365_402}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-02_529_545_365_1098}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Figure 1 shows the possible allocations of six people, $\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 the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path you used, and your improved matching.
\item Explain why it is not possible to find a complete matching.
After training, task 4 is added to F's possible allocation and task 6 is added to E's possible allocation.
\item Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You should list the alternating path you used and your complete matching.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2013 Q1 [7]}}