| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Moderate -0.8 This is a standard application of the maximum matching algorithm from D1, requiring students to follow a well-defined procedure (finding alternating paths) with minimal problem-solving. The algorithm is algorithmic rather than conceptual, and parts (a)-(c) are routine textbook exercises. Part (d) adds a small twist but still follows the same procedure. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| (a) \(G - 5 = W - 3\) change status to \(G = 5 - W = 3\) | M1 A1 | (2 marks) |
| (b) A – no match; E = 2; G = 5; R = 4; W = 3 | A1 | (1 mark) |
| (c) e.g. R is the only person who can do 1 and the only person who can do 4 | B2, 1, 0 | (2 marks) |
| (d) \(A - 2 = E - 3 = W - 4 = R - 1\) change status to \(A = 2 = E = 3 = W = 4 = R = 1\); A = 2; E = 3; G = 5; R = 1; W = 4 | M1 A1 A1 | (3 marks) |
**(a)** $G - 5 = W - 3$ change status to $G = 5 - W = 3$ | M1 A1 | (2 marks) |
**(b)** A – no match; E = 2; G = 5; R = 4; W = 3 | A1 | (1 mark) |
**(c)** e.g. R is the only person who can do 1 and the only person who can do 4 | B2, 1, 0 | (2 marks) |
**(d)** $A - 2 = E - 3 = W - 4 = R - 1$ change status to $A = 2 = E = 3 = W = 4 = R = 1$; A = 2; E = 3; G = 5; R = 1; W = 4 | M1 A1 A1 | (3 marks) |
**Guidance (a):** 1M1: Path from G to 3. 1A1: CAO including change status (stated or shown), chosen path clear.
**Guidance (b):** 2A1: CAO must fit from stated path
**Guidance (c):** 1B1: Correct answer, may be imprecise or muddled (bod gets B1) but all nodes referred to must be correct. 2B1: Good, clear, correct answer.
**Guidance (d):** 1M1: Path from A to 1. 1A1: CAO including change status (stated or shown) but don't penalise twice. Chosen path clear. 1A1: CAO must fit from stated path
**Misread note:** If $A - 2 = E - 3$ c.s. $A = 2 = E = 3$ Matching $A = 2, E = 3, R = 4, W = 5$. Then $G - 5 = W - 4 = R - 1$ c.s. $G = 5 - W = 4 - R = 1$ Matching $A = 2, E = 3, G = 5, R = 1, W = 4$
**Total for Q2: 8 marks**
---2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{be646775-535e-4105-86b4-ffc7eda4fa51-2_432_579_1206_395}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{be646775-535e-4105-86b4-ffc7eda4fa51-2_430_579_1208_1096}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Five tour guides, Alice, Emily, George, Rose and Weidi, need to be assigned to five coach trips, 1, 2, 3, 4 and 5 . A bipartite graph showing their preferences is given in Figure 1 and an initial matching is given in Figure 2.
\begin{enumerate}[label=(\alph*)]
\item Use the maximum matching algorithm, starting with vertex G , to increase the number of matchings. State the alternating path you used.
\item List the improved matching you found in (a).
\item Explain why a complete matching is not possible.
Weidi agrees to be assigned to coach trip 3, 4 or 5.
\item Starting with your current maximal matching, use the maximum matching algorithm to obtain a complete matching.\\
(3)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2008 Q2 [8]}}