| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Easy -1.2 This is a straightforward application of the bipartite matching algorithm from D1 with minimal problem-solving required. Part (a) tests basic understanding of why task 1 needs two vertices, part (b) is a routine algorithmic procedure to find an alternating path, and part (c) requires simple observation about why matching fails. The question is entirely procedural with no novel insight needed, making it easier than average A-level maths questions. |
| Spec | 7.02l Planar graphs: planarity, subdivision, contraction7.02n Kuratowski's theorem: K_5 and K_{3,3} subdivisions |
| Answer | Marks |
|---|---|
| B2, 1, 0 (a) |
| Answer | Marks |
|---|---|
| m1 A1 |
| Answer | Marks |
|---|---|
| A1 (3) |
| Answer | Marks |
|---|---|
| B2, 1, 0 (a) [2] |
## (a)
To obtain a complete matching the number of vertices on each side must be equal.
| B2, 1, 0 (a) |
## (b)
e.g. $L = 3$, $H = 5$, $\tilde{z} = 3$, $la = A - 4$
c.s. $L = 3$, $H = 5$, $\tilde{z} = 3$, $la = A \pm 4$
| m1 A1 |
$A = 4$, $H = 5$, $L = 3$, $E = 16$, $J = la$, $m = 2$
| A1 (3) |
## (c)
Hand $L$ can now both only do 3. So a complete matching is not possible (other routes possible)
| B2, 1, 0 (a) [2] |
---\includegraphics{figure_1}
\includegraphics{figure_2}
Six workers, Annie, Emma, Hannah, Jerry, Louis and Morand, are to be assigned to five tasks, 1,2,3,4 and 5.
For safety reasons, task 1 must be done by two people working together.
A bipartite graph showing the possible allocations of the workers is given in Figure 1 and an initial matching is given in Figure 2.
The maximum matching algorithm will be used to obtain a complete matching.
\begin{enumerate}[label=(\alph*)]
\item Although there are five tasks, six vertices have been created on the right hand side of each bipartite graph. Explain why this is necessary when applying this algorithm. [2]
\item Find an alternating path and the complete matching it gives. [3]
\end{enumerate}
Hannah is now unable to do task 5 due to health reasons.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item Explain why a complete matching is no longer possible. [2]
\end{enumerate}
(Total 7 marks)
\hfill \mbox{\textit{Edexcel D1 2007 Q2 [7]}}