| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| 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. Part (a) is pure recall of a definition, part (b) requires reading an alternating path (minimal problem-solving), and part (c) applies the algorithm mechanically to find one more alternating path. The question guides students through each stage and requires no novel insight—significantly easier than average A-level maths questions. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02g Eulerian graphs: vertex degrees and traversability |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| A path from an unmatched vertex in one set to an unmatched vertex in the other set... | B1 | "Unmatched" to "unmatched" (vertex/node may be implied but do not accept arc) |
| ...which alternately uses arcs not in/in the matching | B1 | Arcs not in/in (arc(s) must be explicitly mentioned, not vertices/nodes) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Initial matching: \(A=3, B=2, D=4\) (C and E unmatched) | B1 | CAO |
| Improved matching: \(A=4, B=3, D=1, E=2\) (C unmatched) | B1 | CAO; ignore candidates' labelling of initial/improved |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Alternating path: \(C-3=B-2=E-5\) | M1 | An alternating path from C to 5 (or vice versa) |
| Change status to give: \(C=3-B=2-E=5\) | A1 | CAO – correct path including change status either stated or shown |
| Complete matching: \(A=4, B=2, C=3, D=1, E=5\) | A1 | CAO – must follow from correct stated path. Accept on clear diagram (five arcs only) |
# Question 4:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| A path from an unmatched vertex in one set to an unmatched vertex in the other set... | B1 | "Unmatched" to "unmatched" (vertex/node may be implied but do not accept arc) |
| ...which alternately uses arcs not in/in the matching | B1 | Arcs not in/in (arc(s) must be explicitly mentioned, **not** vertices/nodes) |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial matching: $A=3, B=2, D=4$ (C and E unmatched) | B1 | CAO |
| Improved matching: $A=4, B=3, D=1, E=2$ (C unmatched) | B1 | CAO; ignore candidates' labelling of initial/improved |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Alternating path: $C-3=B-2=E-5$ | M1 | An alternating path from C to 5 (or vice versa) |
| Change status to give: $C=3-B=2-E=5$ | A1 | CAO – correct path including change status either stated or shown |
| Complete matching: $A=4, B=2, C=3, D=1, E=5$ | A1 | CAO – must follow from correct stated path. Accept on clear diagram (five arcs only) |
---4. (a) Define the term 'alternating path'.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{6417303d-c42a-4da4-b0fa-fb7718959417-6_469_647_315_708}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
Figure 4 shows the possible allocations of five people, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }$ and E , to five tasks, $1,2,3,4$ and 5
An initial matching has three people allocated to three of the tasks.\\
Starting from this initial matching, one possible alternating path that starts at E is
$$E - 2 = B - 3 = A - 4 = D - 1$$
(b) Use this information to
\begin{enumerate}[label=(\roman*)]
\item deduce this initial matching,
\item list the improved matching generated by the given alternating path.\\
(c) Starting from the improved matching found in (b), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path you use and the final matching.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2015 Q4 [7]}}