| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2003 |
| Session | June |
| Marks | 5 |
| 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 matching improvement algorithm with a given initial matching. The question provides the bipartite graph structure and starting allocation, requiring only mechanical execution of the algorithm to find alternating paths. While it requires 5 marks worth of working, the procedure is algorithmic with no problem-solving insight needed, making it easier than average. |
| Spec | 7.02q Adjacency matrix: and weighted matrix representation |
| Worker | Tasks |
| A | 2, 3, 5 |
| B | 1, 3, 4, 5 |
| C | 2 |
| D | 3, 6 |
| E | 2, 4, 5 |
| F | 1 |
Six workers $A$, $B$, $C$, $D$, $E$ and $F$ are to be matched to six tasks 1, 2, 3, 4, 5 and 6.
The table below shows the tasks that each worker is able to do.
\begin{tabular}{|c|c|}
\hline Worker & Tasks \\
\hline A & 2, 3, 5 \\
\hline B & 1, 3, 4, 5 \\
\hline C & 2 \\
\hline D & 3, 6 \\
\hline E & 2, 4, 5 \\
\hline F & 1 \\
\hline
\end{tabular}
A bipartite graph showing this information is drawn in the answer booklet.
Initially, $A$, $B$, $D$ and $E$ are allocated to tasks 2, 1, 3 and 5 respectively.
Starting from the given initial matching, use the matching improvement algorithm to find a complete matching, showing your alternating paths clearly.
[5]
\hfill \mbox{\textit{Edexcel D1 2003 Q1 [5]}}