| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | January |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Moderate -0.8 This is a standard D1 algorithm application question requiring recall of definitions and mechanical application of the maximum matching algorithm with given starting points. The question provides the initial matching and guides students through each step, making it easier than average A-level maths questions which typically require more independent problem-solving. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| A bipartite graph consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set. | B2,1,0 | 2 sets of vertices; arcs must go from one set into the other |
| 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| A Matching is the pairing of some or all of the elements of one set, X, with elements of a second set, Y. | B2,1,0 | Pairing or one to one; element(s) from 1 set with element(s) of the other |
| 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Alternating path: \(J - 4 = E - 2 = C - 3\) | M1 | Path from J to 3 or vice versa |
| Change status: \(J = 4 - E = 2 - C = 3\) | A1 | CAO including change status (stated or shown), chosen path clear |
| \(C = 3,\ E = 2,\ G = 1,\ H = 6,\ J = 4\), (S unmatched) | A1 | CAO unambiguous. Must ft from stated path, diagram ok |
| 3 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Alternating path: \(S - 6 = H - 3 = C - 2 = E - 5\) | M1 | Path from S to 5 (or vice versa) |
| Change status: \(S = 6 - H = 3 - C = 2 - E = 5\) | A1 | CAO including change status (stated or shown), only penalise once per question, chosen path clear |
| \(C = 2,\ E = 5,\ G = 1,\ H = 3,\ J = 4,\ S = 6\) | A1 | CAO unambiguous. Must ft from stated paths, diagram ok. Must have both M's |
| 3 |
# Question 3:
## Part (a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| A bipartite graph consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set. | B2,1,0 | 2 sets of vertices; arcs must go from one set into the other |
| | **2** | |
## Part (b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| A Matching is the pairing of some or all of the elements of one set, X, with elements of a second set, Y. | B2,1,0 | Pairing or one to one; element(s) from 1 set with element(s) of the other |
| | **2** | |
## Part (c):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Alternating path: $J - 4 = E - 2 = C - 3$ | M1 | Path from J to 3 or vice versa |
| Change status: $J = 4 - E = 2 - C = 3$ | A1 | CAO including change status (stated or shown), chosen path clear |
| $C = 3,\ E = 2,\ G = 1,\ H = 6,\ J = 4$, (S unmatched) | A1 | CAO unambiguous. Must ft from stated path, diagram ok |
| | **3** | |
## Part (d):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Alternating path: $S - 6 = H - 3 = C - 2 = E - 5$ | M1 | Path from S to 5 (or vice versa) |
| Change status: $S = 6 - H = 3 - C = 2 - E = 5$ | A1 | CAO including change status (stated or shown), only penalise once per question, chosen path clear |
| $C = 2,\ E = 5,\ G = 1,\ H = 3,\ J = 4,\ S = 6$ | A1 | CAO unambiguous. Must ft from stated paths, diagram ok. Must have both M's |
| | **3** | |
---3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e02c4a9a-d2ab-489f-b838-9b4d902c4457-4_743_457_237_434}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e02c4a9a-d2ab-489f-b838-9b4d902c4457-4_743_455_237_1165}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
Define the terms
\begin{enumerate}[label=(\alph*)]
\item bipartite graph,
\item matching.
Figure 3 shows the possible allocations of six people, Charles (C), Emily (E), George (G), Harriet (H), Jack (J) and Shen (S), to six tasks, 1, 2, 3, 4, 5 and 6.
Figure 4 shows an initial matching.
\item Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path you use and state your improved matching.
Emily has task 5 added to her possible allocations and Harriet has task 3 added to her possible allocations.
\item Starting from the improved matching found in part (c), use the maximum matching algorithm to find a complete matching. You should list the alternating path you use and state your improved matching.\\
(3)\\
(Total 10 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2012 Q3 [10]}}