| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | January |
| Marks | 6 |
| 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. Students are given the initial matching and simply need to follow the algorithmic procedure to find alternating paths, which is a routine mechanical process covered extensively in D1. The question requires no problem-solving insight, just careful execution of a learned algorithm. |
| Spec | 7.02f Bipartite test: colouring argument |
\includegraphics{figure_1}
The bipartite graph in Figure 1 shows a mapping between six people, Andy ($A$), David ($D$), Joan ($J$), Preety ($P$), Sally ($S$) and Trevor ($T$), and six tasks 1, 2, 3, 4, 5 and 6.
The initial matching is $A$ to 2, $D$ to 1, $J$ to 3 and $P$ to 4.
\begin{enumerate}[label=(\alph*)]
\item Indicate this initial matching in a distinctive way on the bipartite graph drawn in the answer book. [1]
\item Starting from this initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating paths you use. [5]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2005 Q1 [6]}}