| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 11 |
| 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 with a straightforward bipartite graph setup. The question guides students through each step (draw graph, show initial matching, apply algorithm, explain impossibility), requiring only routine execution of a memorized algorithm rather than problem-solving insight. The alternating path is easy to identify, and part (d) requires only basic observation about Hall's marriage condition. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02f Bipartite test: colouring argument |
| Minister | Government Position |
| \(P\) | Chancellor ( \(C\) ) |
| \(Q\) | Foreign Secretary ( \(F\) ), Minister for Education ( \(E\) ) |
| \(R\) | Minister for Defence ( \(D\) ), Minister for Industry ( \(I\) ) |
| S | Minister for Defence ( \(D\) ), Home Secretary ( \(H\) ) |
| \(T\) | Home Secretary (H) |
| \(U\) | Chancellor ( \(C\) ), Foreign Secretary ( \(F\) ) |
| Answer | Marks | Guidance |
|---|---|---|
| (a) [Bipartite graph diagram showing matching between two sets] | A1 | |
| (b) initial matching shown by \(\equiv\) | B1 | |
| (c) Search for alternating path giving e.g. \(S - D - R - I\) (breakthrough). Change status giving \(S = D = R = I\). Search for alternating path giving e.g. \(U - F - Q - E\) (breakthrough). Change status giving \(U = F = Q = E\). Complete matching e.g. \(P - C, Q - E, R - I, S - D, T - H, U - F\) | M1 A1; M1; M1 A1; M1; A1 | |
| (d) \(P\) and \(U\) both now only interested in \(C\) which only one can have | B2 | (11) |
**(a)** [Bipartite graph diagram showing matching between two sets] | A1 |
**(b)** initial matching shown by $\equiv$ | B1 |
**(c)** Search for alternating path giving e.g. $S - D - R - I$ (breakthrough). Change status giving $S = D = R = I$. Search for alternating path giving e.g. $U - F - Q - E$ (breakthrough). Change status giving $U = F = Q = E$. Complete matching e.g. $P - C, Q - E, R - I, S - D, T - H, U - F$ | M1 A1; M1; M1 A1; M1; A1 |
**(d)** $P$ and $U$ both now only interested in $C$ which only one can have | B2 | (11) |
---4. This question should be answered on the sheet provided.
The Prime Minister is planning a reshuffle and the table indicates which posts each of the six ministers involved would be willing to accept.
\begin{center}
\begin{tabular}{|l|l|}
\hline
Minister & Government Position \\
\hline
$P$ & Chancellor ( $C$ ) \\
\hline
$Q$ & Foreign Secretary ( $F$ ), Minister for Education ( $E$ ) \\
\hline
$R$ & Minister for Defence ( $D$ ), Minister for Industry ( $I$ ) \\
\hline
S & Minister for Defence ( $D$ ), Home Secretary ( $H$ ) \\
\hline
$T$ & Home Secretary (H) \\
\hline
$U$ & Chancellor ( $C$ ), Foreign Secretary ( $F$ ) \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Draw a bipartite graph to model this situation.
Initially the Prime Minister matches Minister $P$ to the post of Chancellor, $Q$ to Foreign Secretary, $R$ to Defence and $T$ to Home Secretary.
\item Draw this initial matching.
\item Starting from this initial matching use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied, listing any alternating paths used.
Minister $U$, on reflection, now expresses no interest in becoming Foreign Secretary.
\item Explain why no complete matching is now possible.\\
(2 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q4 [11]}}