| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2004 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Easy -1.2 This is a standard textbook application of the bipartite matching algorithm with straightforward setup. The question guides students through each step (draw graph, apply algorithm, explain impossibility), and the impossibility is immediately visible from the constraints (Sam and Nicola each have only one option, both needed elsewhere). Requires only mechanical application of a learned algorithm with minimal problem-solving. |
| Spec | 7.02l Planar graphs: planarity, subdivision, contraction7.02n Kuratowski's theorem: K_5 and K_{3,3} subdivisions |
| Name | Checkpoints |
| Alan | 1 or 3 |
| Geoff | 1 or 5 |
| Laura | 2, 1 or 4 |
| Nicola | 5 |
| Philip | 2 or 5 |
| Sam | 2 |
The organiser of a sponsored walk wishes to allocate each of six volunteers, Alan, Geoff, Laura, Nicola, Philip and Sam to one of the checkpoints along the route. Two volunteers are needed at checkpoint 1 (the start) and one volunteer at each of checkpoint 2, 3, 4 and 5 (the finish). Each volunteer will be assigned to just one checkpoint. The table shows the checkpoints each volunteer is prepared to supervise.
\begin{center}
\begin{tabular}{|c|c|}
\hline
Name & Checkpoints \\
\hline
Alan & 1 or 3 \\
Geoff & 1 or 5 \\
Laura & 2, 1 or 4 \\
Nicola & 5 \\
Philip & 2 or 5 \\
Sam & 2 \\
\hline
\end{tabular}
\end{center}
Initially Alan, Geoff, Laura and Nicola are assigned to the first checkpoint in their individual list.
\begin{enumerate}[label=(\alph*)]
\item Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way. [2]
\item Starting from this initial matching, use the maximum matching algorithm to find an improved matching. Clearly list any alternating paths you use. [3]
\item Explain why it is not possible to find a complete matching. [2]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2004 Q1 [7]}}