| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| 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 a given initial matching. Students need to identify alternating paths and update the matching iteratively—a routine procedure in D1 with no novel problem-solving required. Part (a) is pure recall (bipartite graph). The algorithm is mechanical and well-practiced, making this easier than average. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02c Graph terminology: walk, trail, path, cycle, route |
| Answer | Marks | Guidance |
|---|---|---|
| Bipartite (graph) | B1 (1) | |
| e.g. (see below for alternatives) First alternating path: \(B - 4 = L - 3 = H - 2\) Change status to give \(B = 4 - L = 3 - H = 2\) Improved matching: \(A = 1, B = 4, H = 2, (I \text{ unmatched}), L = 3 R = 5\) | M1 A1 A1 | |
| Second alternating path: \(I - 1 = A - 3 = L - 5 = R - 6\) Changing status to give: \(I = 1 - A = 3 - L = 5 - R = 6\) Complete matching: \(A = 3, B = 4, H = 2, I = 1, L = 5, R = 6\) | M1 A1 A1 | (6) |
| 7 marks |
| Bipartite (graph) | B1 (1) | |
| e.g. (see below for alternatives) First alternating path: $B - 4 = L - 3 = H - 2$ Change status to give $B = 4 - L = 3 - H = 2$ Improved matching: $A = 1, B = 4, H = 2, (I \text{ unmatched}), L = 3 R = 5$ | M1 A1 A1 | |
| Second alternating path: $I - 1 = A - 3 = L - 5 = R - 6$ Changing status to give: $I = 1 - A = 3 - L = 5 - R = 6$ Complete matching: $A = 3, B = 4, H = 2, I = 1, L = 5, R = 6$ | M1 A1 A1 | (6) |
| | | 7 marks |
**Notes:**
- a1B1: CAO but be charitable on spelling, award if phonetically close
- b1M1: An alternating path (e.g. letter – number – letter – ...) from either B to 2 or 6 or from I to 2 – or vice versa
- b1A1: CAO – a correct path including change status either stated (only accept 'change (of) status' or 'c.s.') or shown (all symbols e.g. $(... = ... = ...)$ interchanged $(... = ... = ...)$). Chosen path clear.
- b2A1: CAO must follow from the correct stated path. Accept on a clear diagram (with five arcs only).
- b2A1: A second alternating path from the remaining (unused) I or B to the remaining (unused) 6 or 2 - or vice versa.
- b3A1: CAO including change status (stated or shown), chosen path clear
- b4A1: 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).
---1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5b32eb57-c9cd-46ec-a328-12050148bdf7-2_766_570_324_342}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5b32eb57-c9cd-46ec-a328-12050148bdf7-2_755_570_331_1146}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Figure 1 shows the possible allocations of six people, Alex (A), Ben (B), Harriet (H), Izzy (I), Leo (L) and Rowan (R), to six tasks, $1,2,3,4,5$ and 6.
\begin{enumerate}[label=(\alph*)]
\item Write down the technical name given to the type of diagram shown in Figure 1.
Figure 2 shows an initial matching.
\item Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating paths you use, and state your improved matching after each iteration.\\
(6)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2013 Q1 [7]}}