| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| 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 on a bipartite graph. Part (a) requires simple observation that 4 taxis are matched leaving 2 unmatched, so the algorithm must run twice. Part (b) is mechanical execution of a learned algorithm with no problem-solving insight required—students follow the alternating path procedure they've been taught. While worth 7 marks total, it's routine recall and application, making it easier than average A-level questions. |
| Spec | 7.02q Adjacency matrix: and weighted matrix representation |
\includegraphics{figure_1}
A taxi firm has six taxis $A$, $B$, $C$, $D$, $E$ and $F$, available for six journeys, 1, 2, 3, 4, 5 and 6, which are booked for 9 a.m. tomorrow.
The bipartite graph shown in Figure 1 shows the possible matchings.
Initially $A$, $B$, $C$ and $D$ are matched to 5, 2, 3 and 6 respectively, as indicated in Figure 2.
\begin{enumerate}[label=(\alph*)]
\item Explain why it is necessary to perform the maximum matching algorithm twice in order to try to obtain a complete matching. [1]
\item Use the maximum matching algorithm twice to obtain a complete matching. List clearly the alternating paths you use. [6]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2006 Q1 [7]}}