| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | January |
| Marks | 9 |
| 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 clear instructions. Part (a) requires simple recall of definitions, and part (b) involves mechanically applying the maximum matching algorithm twice to a small bipartite graph with an initial matching provided. No problem-solving insight or novel reasoning is required—just following the taught procedure. |
| Spec | 7.02q Adjacency matrix: and weighted matrix representation |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| A path from an unmatched vertex in one set to an unmatched vertex in the other set... | B1 | |
| ...which alternately uses arcs not in / in the matching | B1(z) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| A one-to-one pairing of | B1 | |
| some elements of one set with the other set | B1(z) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 'Path' starting at D or E, finishing at 1 or 5 – or vice versa | M1 A1 | |
| A correct path including change of status | M1 A1 | e.g. \(D-3=C-5\), change status \(D=3-C=5\); \(E-2=A-1\), change status \(E=2-A=1\) |
| \(A=1,\ B=4,\ C=5,\ D=3,\ E=2\) | A1(s) | Complete matching, must follow through from two correct paths |
# Question 1:
## Part (a)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| A path from an unmatched vertex in one set to an unmatched vertex in the other set... | B1 | |
| ...which alternately uses arcs not in / in the matching | B1(z) | |
## Part (a)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| A one-to-one pairing of | B1 | |
| some elements of one set with the other set | B1(z) | |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| 'Path' starting at D or E, finishing at 1 or 5 – or vice versa | M1 A1 | |
| A correct path including change of status | M1 A1 | e.g. $D-3=C-5$, change status $D=3-C=5$; $E-2=A-1$, change status $E=2-A=1$ |
| $A=1,\ B=4,\ C=5,\ D=3,\ E=2$ | A1(s) | Complete matching, must follow through from two correct paths |
**Total: [9]**
---\begin{enumerate}
\item (a) Define the terms\\
(i) alternating path,\\
(ii) matching.
\end{enumerate}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{7396d930-0143-4876-b019-a4d73e09b172-2_568_621_689_344}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{7396d930-0143-4876-b019-a4d73e09b172-2_554_540_701_1171}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
At a school fair, five teachers, $A , B , C , D$ and $E$, are to supervise five stalls, $1,2,3,4$ and 5 .\\
A bipartite graph showing their possible allocations is given in Figure 1. An initial matching is given in Figure 2.\\
(b) Use the maximum matching algorithm twice to obtain a complete matching. List clearly the alternating paths you use.\\
\hfill \mbox{\textit{Edexcel D1 2008 Q1 [9]}}