| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2003 |
| Session | January |
| Marks | 6 |
| 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 matching algorithm from D1. Students follow a prescribed algorithm (finding alternating paths) with clear steps. The setup is straightforward with only 5 trainees and 5 departments, requiring minimal problem-solving beyond executing the taught procedure. Significantly easier than average A-level questions. |
| Spec | 7.02f Bipartite test: colouring argument |
| Trainee | Departments |
| \(H\) | \(D, F, P\) |
| \(J\) | \(G, D, F\) |
| \(M\) | \(S, P, G\) |
| \(T\) | \(F, S, G\) |
| \(Y\) | \(D\) |
At Tesafe supermarket there are 5 trainee staff, Homan $(H)$, Jenna $(J)$, Mary $(M)$, Tim $(T)$ and Yoshie $(Y)$. They each must spend one week in each of 5 departments, Delicatessen $(D)$, Frozen foods $(F)$, Groceries $(G)$, Pet foods $(P)$, Soft drinks $(S)$. Next week every department requires exactly one trainee. The table below shows the departments in which the trainees have yet to spend time.
\begin{center}
\begin{tabular}{|c|c|}
\hline
Trainee & Departments \\
\hline
$H$ & $D, F, P$ \\
$J$ & $G, D, F$ \\
$M$ & $S, P, G$ \\
$T$ & $F, S, G$ \\
$Y$ & $D$ \\
\hline
\end{tabular}
\end{center}
Initially $H$, $J$, $M$ and $T$ are allocated to the first department in their list.
\begin{enumerate}[label=(\alph*)]
\item Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way.
[2]
Starting from this matching,
\item use the maximum matching algorithm to find a complete matching. You must make clear your alternating path and your complete matching.
[4]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2003 Q2 [6]}}