| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| 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 a standard D1 algorithm with minimal problem-solving required. Part (a) is pure recall of a definition (2 marks), and part (b) is a routine execution of the maximum matching algorithm following prescribed steps. The question explicitly tells students to use the algorithm twice and state alternating paths, making it a mechanical procedure rather than requiring insight or novel reasoning. |
| Spec | 7.02l Planar graphs: planarity, subdivision, contraction7.02n Kuratowski's theorem: K_5 and K_{3,3} subdivisions |
| Answer | Marks |
|---|---|
| (b)(i) \(R - B = A - P\); \(S - F = M - C = D - K\) | A1 A1 |
| (ii) \(R - B = A - F = M - C = D - K\); \(S - F = A - P\) | A1 A1 |
| (iii) \(S - F = M - C = D - K\); \(R - B = A - P\) | A1 A1 |
| (iv) \(S - F = M - Y = H - B = A - P\); \(R - B = H - Y = M - C = D - K\) | A1 A1 |
(b)(i) $R - B = A - P$; $S - F = M - C = D - K$ | A1 A1
(ii) $R - B = A - F = M - C = D - K$; $S - F = A - P$ | A1 A1
(iii) $S - F = M - C = D - K$; $R - B = A - P$ | A1 A1
(iv) $S - F = M - Y = H - B = A - P$; $R - B = H - Y = M - C = D - K$ | A1 A1
---\begin{enumerate}[label=(\alph*)]
\item Define the term 'alternating path'. [2]
\item \includegraphics{figure_1}
The bipartite graph in Figure 1 shows the films that six customers wish to hire this Saturday evening. The shop has only one copy of each film. The bold lines indicate an initial matching.
Starting from this initial matching use the maximum matching algorithm twice to obtain a complete matching. You should clearly state the alternating paths you use. [5]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2006 Q2 [7]}}