| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2002 |
| Session | January |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Easy -1.3 This is a standard textbook application of the matching improvement algorithm with a small, straightforward bipartite graph. The question provides the initial allocation and simply requires students to follow a well-practiced algorithmic procedure with minimal problem-solving or insight required. |
| Spec | 7.02b Graph terminology: tree, simple, connected, simply connected7.02g Eulerian graphs: vertex degrees and traversability |
| Ann | 1 or 2 |
| Bryn | 3 or 1 |
| Daljit | 2 or 4 |
| Gareth | 5 or 3 |
| Nickos | 1 or 2 |
Ann, Bryn, Daljit, Gareth and Nickos have all joined a new committee. Each of them is to be allocated to one of five jobs 1, 2, 3, 4 or 5. The table shows each member's preferences for the jobs.
\begin{center}
\begin{tabular}{|c|c|}
\hline
Ann & 1 or 2 \\
\hline
Bryn & 3 or 1 \\
\hline
Daljit & 2 or 4 \\
\hline
Gareth & 5 or 3 \\
\hline
Nickos & 1 or 2 \\
\hline
\end{tabular}
\end{center}
Initially Ann, Bryn, Daljit and Gareth are allocated the first job in their lists shown in the table.
\begin{enumerate}[label=(\alph*)]
\item Draw a bipartite graph to model the preferences shown in the table and indicate, in a distinctive way, the initial allocation of jobs. [2]
\item Use the matching improvement algorithm to find a complete matching, showing clearly your alternating path. [3]
\item Find a second alternating path from the initial allocation. [1]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2002 Q1 [6]}}