| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 8 |
| 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 follow a prescribed algorithm with clear initial conditions, requiring only mechanical execution of the alternating path method. The small size (5 people, 5 activities) makes it straightforward, and similar questions appear regularly in D1 past papers. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02r Graph modelling: model and solve problems using graphs |
| Name | Activities |
| Fatima | Windsurfing, Sailing |
| Gavin | Climbing, Orienteering |
| Hassan | Windsurfing, Climbing |
| Iain | Sailing, Diving |
| Jane | Diving, Sailing, Orienteering |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | M1 A1 | |
| (b) Initial matching shown by \(\equiv\); search for alternating path giving e.g. \(H - C = G - O\) (breakthrough); change status giving \(H \equiv C = G = O\); complete matching e.g. \(F - W, G - O, H - C, I - S, J - D\) | B1, M1 A1, M1, M1 A1 | (8) |
**(a)** | M1 A1 |
**(b)** Initial matching shown by $\equiv$; search for alternating path giving e.g. $H - C = G - O$ (breakthrough); change status giving $H \equiv C = G = O$; complete matching e.g. $F - W, G - O, H - C, I - S, J - D$ | B1, M1 A1, M1, M1 A1 | (8)
---4. This question should be answered on the sheet provided.
The manager of an outdoor centre must staff each activity offered by the centre with an appropriately qualified instructor. The table below shows the sports for which each member of staff is qualified to supervise.
\begin{center}
\begin{tabular}{|l|l|}
\hline
Name & Activities \\
\hline
Fatima & Windsurfing, Sailing \\
\hline
Gavin & Climbing, Orienteering \\
\hline
Hassan & Windsurfing, Climbing \\
\hline
Iain & Sailing, Diving \\
\hline
Jane & Diving, Sailing, Orienteering \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Draw a bipartite graph to model this situation.
Initially the manager allocates Fatima, Gavin, Iain and Jane to supervise the first sport listed against their names in the table.
\item Starting from this matching, use the maximum matching algorithm to find a complete matching. Indicate clearly how you have applied the algorithm.\\
(6 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q4 [8]}}