| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Explain why complete matching impossible |
| Difficulty | Moderate -0.8 This is a straightforward application of bipartite graph matching with clear structure. Students need to draw simple bipartite graphs, identify an obvious bottleneck (three trainees want Edinburgh but only one office available), and apply a standard algorithm with an initial matching provided. The reasoning required is minimal and the algorithm is mechanical, making this easier than average A-level content. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02f Bipartite test: colouring argument |
| Trainee | Preferences |
| \(P\) | Dundee, London (either) |
| \(Q\) | Dundee, Edinburgh, Glasgow |
| \(R\) | Glasgow, London (Head Office only) |
| S | Edinburgh |
| \(T\) | Edinburgh |
| Answer | Marks |
|---|---|
| [Bipartite matching diagram with vertices P, Q, R, S, T on left connected to D, G, E, L(H), L on right] | A1 |
| Answer | Marks |
|---|---|
| Both S and T can only be linked with E, therefore not possible | B1 |
| Answer | Marks |
|---|---|
| [Bipartite matching diagram with complete connections shown] | A1 |
| Answer | Marks |
|---|---|
| Initial matching shown by \(\equiv\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Search for alternating path giving e.g. \(T - L\) (breakthrough) change status giving \(T = L\) | M1 A1 | |
| Alternating path e.g. \(Q - D - P - L(H)\) (breakthrough) change status giving \(Q - D = P - L(H)\) | M1 A1 | |
| Complete matching e.g. \(P - L(H), Q - D, R - G, S - E, T - L\) | A1 | (11) |
**Part (a)**
[Bipartite matching diagram with vertices P, Q, R, S, T on left connected to D, G, E, L(H), L on right] | A1 |
**Part (b)**
Both S and T can only be linked with E, therefore not possible | B1 |
**Part (c)**
[Bipartite matching diagram with complete connections shown] | A1 |
**Part (d)**
Initial matching shown by $\equiv$ | B1 |
**Part (e)**
Search for alternating path giving e.g. $T - L$ (breakthrough) change status giving $T = L$ | M1 A1 |
Alternating path e.g. $Q - D - P - L(H)$ (breakthrough) change status giving $Q - D = P - L(H)$ | M1 A1 |
Complete matching e.g. $P - L(H), Q - D, R - G, S - E, T - L$ | A1 | (11) |
---3. This question should be answered on the sheet provided.
A firm of auditors is to place one trainee accountant at each of its five offices. These are situated in Dundee, Edinburgh, Glasgow and London. There are two offices in London, one of which is the company's Head Office.
The table summarises the trainees' preferences.
\begin{center}
\begin{tabular}{|l|l|}
\hline
Trainee & Preferences \\
\hline
$P$ & Dundee, London (either) \\
\hline
$Q$ & Dundee, Edinburgh, Glasgow \\
\hline
$R$ & Glasgow, London (Head Office only) \\
\hline
S & Edinburgh \\
\hline
$T$ & Edinburgh \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Draw a bipartite graph to model this situation.
\item Explain why no complete matching is possible.
Trainee $T$ is persuaded that either office in London would be just as good for her personal development as the Edinburgh office.
\item Draw a second bipartite graph to model the changed situation.
In an initial matching, trainee $P$ is placed in the Dundee office, trainee $R$ in the Glasgow office, and trainee $S$ in the Edinburgh office.
\item Draw this initial matching.
\item Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You must indicate how the algorithm has been applied, stating clearly the alternating paths you use and the final matching.\\
(7 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q3 [11]}}