| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 7 |
| 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 clear step-by-step instructions. The bipartite graph is straightforward to draw, and the algorithm is applied mechanically following the given initial matching. While it requires careful bookkeeping across multiple parts, it involves no novel problem-solving or insight—just routine execution of a prescribed algorithm. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation |
| Critic | Preference |
| B | \(2,3,6\) |
| G | 1 |
| J | \(2,5,6\) |
| M | 1,5 |
| R | \(2,4,6\) |
| S | 3,5 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| [Diagram showing bipartite graph with B, G, J, M, R, S on left; 1, 2, 3, 4, 5, 6 on right] | B1 | (1) |
| Alternating path: \(G - 1 = M - 5 = J - 2 = B - 3\) or \(G - 1 = M - 5 = J - 6 = R - 2 = B - 3\) Change status: \(G = 1 - M = 5 - J = 2 - B = 3\) or \(G = 1 - M = 5 - J = 6 - R = 2 - B = 3\) Improved matching: 1. \(B = 3, G = 1, J = 2, M = 5, R = 6, (S \text{ unmatched})\) or 2. \(B = 3, G = 1, J = 6, M = 5, R = 2, (S \text{ unmatched})\) | M1 A1 A1 | (3) |
| Alternating path from IM 1: \(S - 3 = B - 6 = R - 4\) or \(S - 3 = B - 2 = J - 6 = R - 4\) With change status leading to Complete matching: \(B = 6, G = 1, J = 2, M = 5, R = 4, S = 3\) or \(B = 2, G = 1, J = 6, M = 5, R = 4, S = 3\) Alternating path from IM 2: \(S - 3 = B - 2 = R - 4\) or \(S - 3 = B - 6 = J - 2 = R - 4\) With change status leading to Complete matching: \(B = 2, G = 1, J = 6, M = 5, R = 4, S = 3\) or \(B = 6, G = 1, J = 2, M = 5, R = 4, S = 3\) | M1 A1 A1 | (3) |
| 7 marks |
| Answer/Working | Marks | Guidance |
|---|---|---|
| [Diagram showing bipartite graph with B, G, J, M, R, S on left; 1, 2, 3, 4, 5, 6 on right] | B1 | (1) |
| **Alternating path:** $G - 1 = M - 5 = J - 2 = B - 3$ or $G - 1 = M - 5 = J - 6 = R - 2 = B - 3$ **Change status:** $G = 1 - M = 5 - J = 2 - B = 3$ or $G = 1 - M = 5 - J = 6 - R = 2 - B = 3$ **Improved matching:** 1. $B = 3, G = 1, J = 2, M = 5, R = 6, (S \text{ unmatched})$ or 2. $B = 3, G = 1, J = 6, M = 5, R = 2, (S \text{ unmatched})$ | M1 A1 A1 | (3) |
| **Alternating path from IM 1:** $S - 3 = B - 6 = R - 4$ or $S - 3 = B - 2 = J - 6 = R - 4$ **With change status leading to Complete matching:** $B = 6, G = 1, J = 2, M = 5, R = 4, S = 3$ or $B = 2, G = 1, J = 6, M = 5, R = 4, S = 3$ **Alternating path from IM 2:** $S - 3 = B - 2 = R - 4$ or $S - 3 = B - 6 = J - 2 = R - 4$ **With change status leading to Complete matching:** $B = 2, G = 1, J = 6, M = 5, R = 4, S = 3$ or $B = 6, G = 1, J = 2, M = 5, R = 4, S = 3$ | M1 A1 A1 | (3) |
| | | **7 marks** |
**Notes for Question 2:**
- a1B1: CAO
- b1M1: An alternating path from G to 3 (or vice versa)
- b1A1: CAO – a correct path including change status **either stated or shown**. Chosen path clear
- b2A1: CAO – must follow from the correct stated path. Accept on a **clear diagram** (with five arcs only)
- c1M1: An alternating path from S to 4 (or vice versa)
- c1A1: CAO – a correct path including change status **either stated or shown**. Chosen path clear.
- c2A1: CAO – must follow from **two correct stated paths** (so both previous M marks must have been awarded). Accept on a **clear diagram** (with six arcs only)
---2. Six film critics, Bronwen (B), Greg (G), Jean (J), Mick (M), Renee (R) and Susan (S), must see six films, $1,2,3,4,5$ and 6 . Each critic must attend a different film and each critic needs to be allocated to exactly one film. The critics are asked which films they would prefer and their preferences are given in the table below.
\begin{center}
\begin{tabular}{ | l | l | }
\hline
Critic & Preference \\
\hline
B & $2,3,6$ \\
\hline
G & 1 \\
\hline
J & $2,5,6$ \\
\hline
M & 1,5 \\
\hline
R & $2,4,6$ \\
\hline
S & 3,5 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Using Diagram 1 in the answer book, draw a bipartite graph to show the possible allocations of critics to their preferred films.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-03_616_524_1114_767}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Figure 2 shows an initial matching.
\item Starting from the given initial matching, apply the maximum matching algorithm to find an alternating path from G to 3 . Hence find an improved matching. You should list the alternating path that you use, and state your improved matching.\\
(3)
\item Starting with the improved matching found in (b), apply the maximum matching algorithm to obtain a complete matching. You should list the alternating path that you use, and state your complete matching.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2016 Q2 [7]}}