| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Standard +0.3 This is a standard D1 bipartite matching question requiring mechanical application of the maximum matching algorithm from an initial incomplete matching. The algorithm is algorithmic rather than requiring insight, and with only 5 computers and 5 applications, the problem size is small. Part (c) asks for an alternative matching after a simple modification, which is straightforward once part (b) is complete. This is slightly easier than average because it's a textbook application of a prescribed algorithm with no novel problem-solving required. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation |
| Computer | Applications |
| \(E\) | Animation |
| \(F\) | Office, Data |
| \(G\) | Simulation |
| \(H\) | Animation, Office |
| \(I\) | Data, CAD, Simulation |
| Answer | Marks | Guidance |
|---|---|---|
| (a) [Bipartite matching diagram with vertices E, F, G, H, I on left matched to O, D, C, A, S on right] | A1 | |
| (b) initial matching shown by \(\equiv\) | B1 | M1 A1 |
| search for alternating path giving e.g. \(G - S\) (breakthrough) change status giving \(G = S\) | M1 | |
| alternating path e.g. \(E - A, H - O, F - D, I - C\) (breakthrough) change status giving \(E = A, H = O, F = D, I = C\) | M1 A1 | |
| complete matching e.g. \(E – A, F – D, G – S, H – O, I – C\) | M1 A1 | |
| (c) e.g. there is now a cycle: \(H - C - I - D - F - O - H\) change status giving \(H = C, I = D, F = O, H\) alternating matching \(E – A, F – O, G – S, H – C, I – D\) | M2 A1 | (13) |
**(a)** [Bipartite matching diagram with vertices E, F, G, H, I on left matched to O, D, C, A, S on right] | A1 |
**(b)** initial matching shown by $\equiv$ | B1 | M1 A1 |
| search for alternating path giving e.g. $G - S$ (breakthrough) change status giving $G = S$ | M1 |
| alternating path e.g. $E - A, H - O, F - D, I - C$ (breakthrough) change status giving $E = A, H = O, F = D, I = C$ | M1 A1 |
| complete matching e.g. $E – A, F – D, G – S, H – O, I – C$ | M1 A1 |
**(c)** e.g. there is now a cycle: $H - C - I - D - F - O - H$ change status giving $H = C, I = D, F = O, H$ alternating matching $E – A, F – O, G – S, H – C, I – D$ | M2 A1 | (13) |
---\textit{This question should be answered on the sheet provided.}
There are 5 computers in an office, each of which must be dedicated to a single application. The computers have different specifications and the following table shows which applications each computer is capable of running.
\begin{center}
\begin{tabular}{|c|l|}
\hline
Computer & Applications \\
\hline
$E$ & Animation \\
$F$ & Office, Data \\
$G$ & Simulation \\
$H$ & Animation, Office \\
$I$ & Data, CAD, Simulation \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Draw a bipartite graph to model this situation. [1 mark]
\end{enumerate}
Initially it is decided to run the Office application on computer $F$, Animation on computer $H$, and Data on computer $I$.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\item Starting from this matching, use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied. [9 marks]
\item Computer $H$ is upgraded to allow it to run CAD. Find an alternative matching to that found in part (b). [3 marks]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q6 [13]}}