| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | June |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Easy -1.2 This is a standard textbook application of the maximum matching algorithm (likely Hungarian or alternating path method) with an initial matching provided. Students follow a prescribed algorithm with clear steps—no novel problem-solving or insight required, just mechanical execution of a D1 technique they've practiced extensively. |
| Spec | 7.02r Graph modelling: model and solve problems using graphs |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct adjacency matrix with rows/columns labelled A–F and 1–6 | B1 | Must have correct labels |
| All entries correct (1s and 0s in correct positions) | B1 | Follow through from graph: A-{1,2}, B-{3,4}, C-{2,3}, D-{1,5}, E-{5,6}, F-{4,6} (or similar from graph) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct augmenting path identified, e.g. \(A = \) unmatched, try \(A \to 1\), \(D \to 1\) matched so \(D \to 5\), \(E \to 5\) matched so \(E \to 6\), \(F \to 6\) matched | M1 | Must show alternating path from unmatched person |
| Correct augmenting path stated, e.g. \(A - 1 - D - 5 - E - 6 - F\) (or equivalent) | A1 | Accept any valid augmenting path shown |
| Complete matching stated: e.g. \(A \to 2\), \(B \to 4\), \(C \to 3\), \(D \to 1\), \(E \to 5\), \(F \to 6\) | A1 | All six must be correctly matched |
# Question 1:
## Part (a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct adjacency matrix with rows/columns labelled A–F and 1–6 | B1 | Must have correct labels |
| All entries correct (1s and 0s in correct positions) | B1 | Follow through from graph: A-{1,2}, B-{3,4}, C-{2,3}, D-{1,5}, E-{5,6}, F-{4,6} (or similar from graph) |
## Part (b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct augmenting path identified, e.g. $A = $ unmatched, try $A \to 1$, $D \to 1$ matched so $D \to 5$, $E \to 5$ matched so $E \to 6$, $F \to 6$ matched | M1 | Must show alternating path from unmatched person |
| Correct augmenting path stated, e.g. $A - 1 - D - 5 - E - 6 - F$ (or equivalent) | A1 | Accept any valid augmenting path shown |
| Complete matching stated: e.g. $A \to 2$, $B \to 4$, $C \to 3$, $D \to 1$, $E \to 5$, $F \to 6$ | A1 | All six must be correctly matched |
---1 Six people, $A , B , C , D , E$ and $F$, are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following bipartite graph shows the tasks that each of the people is able to undertake.\\
\includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-02_1003_547_740_737}
\begin{enumerate}[label=(\alph*)]
\item Represent this information in an adjacency matrix.
\item Initially, $B$ is assigned to task 4, $C$ to task 3, $D$ to task 1, $E$ to task 5 and $F$ to task 6.
By using an algorithm from this initial matching, find a complete matching.\\
(3 marks)
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2012 Q1 [5]}}