| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | January |
| Marks | 6 |
| 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 follow a mechanical procedure to find alternating paths and improve the matching. The algorithm is algorithmic rather than requiring problem-solving insight, and this is a routine D1 question with clear structure and moderate step count. |
| Spec | 7.02q Adjacency matrix: and weighted matrix representation |
| Answer | Marks | Guidance |
|---|---|---|
| Initial matching: A-1, C-3, D-4, E-5 (4 lines shown, B and F unmatched) | B1 | Accept if unambiguous; preferably just 4 lines |
| Answer | Marks | Guidance |
|---|---|---|
| Path 1: F-4-D-5-E-2 | M1 A1 | M1 for attempt at path from B or F to 2 or 6; A1 for correct path including change status |
| Path 2: B-3-C-6 | M1 A1 | M1 for attempt at second path from F or B to 6 or 2; A1 for correct path (do not penalise change status twice) |
| Final matching: A:1, B:3, C:6, D:5, E:2, F:4 | A1 | Must follow from 2 correct paths |
# Question 1:
## Part (a)
| Initial matching: A-1, C-3, D-4, E-5 (4 lines shown, B and F unmatched) | B1 | Accept if unambiguous; preferably just 4 lines |
## Part (b)
| Path 1: F-4-D-5-E-2 | M1 A1 | M1 for attempt at path from B or F to 2 or 6; A1 for correct path including change status |
| Path 2: B-3-C-6 | M1 A1 | M1 for attempt at second path from F or B to 6 or 2; A1 for correct path (do not penalise change status twice) |
| Final matching: A:1, B:3, C:6, D:5, E:2, F:4 | A1 | Must follow from 2 correct paths |
---1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{17bc9fb2-13bf-4ffa-93ac-bef170467570-2_611_629_360_717}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 shows the possible allocation of six people, Alice (A), Brian (B), Christine (C), David (D), Elizabeth (E) and Freddy (F), to six tasks, 1, 2, 3, 4, 5 and 6.
An initial matching is Alice to task 1, Christine to task 3, David to task 4 and Elizabeth to task 5.
\begin{enumerate}[label=(\alph*)]
\item Show this initial matching on Diagram 1 in the answer book.\\
(1)
\item Starting from this initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating paths that you use, and give your final matching.\\
(5)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2010 Q1 [6]}}