| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | June |
| 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 small bipartite graph (5 vertices each side). Part (a) is routine matrix construction, part (b)(i) follows a prescribed algorithm with an initial matching given, and part (b)(ii) requires finding an alternative solution. The question is algorithmic rather than requiring problem-solving insight, and the small size makes it computationally straightforward—easier than average A-level maths. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02r Graph modelling: model and solve problems using graphs |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Matrix with rows/columns labelled \(A,B,C,D,E\) and tasks \(1,2,3,4,5\) | B1 | Correct labels |
| Correct entries: \(A\): tasks 1,2,3; \(B\): tasks 2,3,4; \(C\): tasks 3,4; \(D\): tasks 2,3,4; \(E\): tasks 4,5 (using 0s and 1s or equivalent) | B1 | All entries correct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Initial matching: \(A=3, B=2, C=4\) | — | Given |
| Alternating path found from unmatched person, e.g. \(D \to 3 - A \to 1\) or \(E \to 4 - C \to 3 - A \to 1\) | M1 | Must show a valid alternating path from unmatched vertex |
| Path correctly identified showing change of status | A1 | Correct path stated |
| Complete matching shown: e.g. \(A=1, B=2, C=4, D=3, E=5\) | A1 | All five people allocated |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| A different complete matching stated, e.g. \(A=2, B=3, C=4, D=?, E=5\) or another valid complete allocation | B1 | Must be a valid complete matching different from the one found in (b)(i) |
# Question 1:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Matrix with rows/columns labelled $A,B,C,D,E$ and tasks $1,2,3,4,5$ | B1 | Correct labels |
| Correct entries: $A$: tasks 1,2,3; $B$: tasks 2,3,4; $C$: tasks 3,4; $D$: tasks 2,3,4; $E$: tasks 4,5 (using 0s and 1s or equivalent) | B1 | All entries correct |
## Part (b)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial matching: $A=3, B=2, C=4$ | — | Given |
| Alternating path found from unmatched person, e.g. $D \to 3 - A \to 1$ or $E \to 4 - C \to 3 - A \to 1$ | M1 | Must show a valid alternating path from unmatched vertex |
| Path correctly identified showing change of status | A1 | Correct path stated |
| Complete matching shown: e.g. $A=1, B=2, C=4, D=3, E=5$ | A1 | All five people allocated |
## Part (b)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| A different complete matching stated, e.g. $A=2, B=3, C=4, D=?, E=5$ or another valid complete allocation | B1 | Must be a valid complete matching different from the one found in (b)(i) |
---1 Five people, $A , B , C , D$ and $E$, are to be allocated to five tasks, 1, 2, 3, 4 and 5 . The following bipartite graph shows the tasks that each person is able to undertake.\\
\includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-02_441_437_699_797}
\begin{enumerate}[label=(\alph*)]
\item Represent this information in an adjacency matrix.
\item Initially, $A$ is allocated to task 3, $B$ to task 2 and $C$ to task 4.
\begin{enumerate}[label=(\roman*)]
\item Demonstrate, by using an alternating-path algorithm from this initial matching, how each person can be allocated to a different task.
\item Find a different allocation of people to tasks.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2014 Q1 [6]}}