| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| 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 straightforward application of the maximum matching algorithm (likely Hungarian or alternating path method) taught in D1. Part (a) is routine graph drawing from a matrix, and part (b) provides an initial matching and asks students to apply the standard algorithm they've learned. It requires careful execution but no problem-solving insight or novel thinking—purely algorithmic application of a taught procedure. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02q Adjacency matrix: and weighted matrix representation |
| Task 1 | Task 2 | Task 3 | Task 4 | Task 5 | Task 6 | |
| \(\boldsymbol { A }\) | 0 | 0 | 1 | 0 | 1 | 1 |
| B | 0 | 1 | 0 | 1 | 0 | 0 |
| \(\boldsymbol { C }\) | 0 | 1 | 0 | 0 | 0 | 1 |
| \(\boldsymbol { D }\) | 0 | 0 | 0 | 1 | 0 | 0 |
| \(E\) | 1 | 0 | 1 | 0 | 1 | 0 |
| \(\boldsymbol { F }\) | 0 | 0 | 0 | 1 | 1 | 0 |
| Answer | Marks | Guidance |
|---|---|---|
| Bipartite graph: 2 sets of vertices with at least one edge | M1 | |
| All correct | A1 | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| A3, B4, C2, E5. Start from D, F or 1, 6 | M1 | Initial match |
| 1st path must go beyond 2nd letter/number | M1 | |
| 2nd path must go beyond 2nd letter/number | M1 | e.g. \(D - 4 (+) B / F\) |
| If working is only on diagram, the path(s) must be clear, and only 1 path per diagram can be credited. If 2 paths shown on one diagram, max mark M1A1 | ||
| Accept paths in reverse order: \(D - 4 (+) B - 2 (+) C - 6\) or \(F - 5 (+) E - 1\) or \(F - 4(+) B - 2(+) C - 6\) and \(D - 4(+) F - 5(+) E - 1\) | A1 | 1st correct path |
| A1 | 2nd correct path | |
| Match: A3, B2, C6, D4, E1, F5 | B1 | 5 |
| Must be clearly stated or indicated | ||
| Total | 7 |
## 1(a)
| Bipartite graph: 2 sets of vertices with at least one edge | M1 | |
| All correct | A1 | 2 |
## 1(b)
| A3, B4, C2, E5. Start from D, F or 1, 6 | M1 | Initial match |
| 1st path must go beyond 2nd letter/number | M1 | |
| 2nd path must go beyond 2nd letter/number | M1 | e.g. $D - 4 (+) B / F$ |
| If working is only on diagram, the path(s) must be clear, and only 1 path per diagram can be credited. If 2 paths shown on one diagram, max mark M1A1 | | |
| Accept paths in reverse order: $D - 4 (+) B - 2 (+) C - 6$ or $F - 5 (+) E - 1$ or $F - 4(+) B - 2(+) C - 6$ and $D - 4(+) F - 5(+) E - 1$ | A1 | 1st correct path |
| | A1 | 2nd correct path |
| Match: A3, B2, C6, D4, E1, F5 | B1 | 5 |
| | | Must be clearly stated or indicated |
| Total | | 7 |1 Six people, $A , B , C , D , E$ and $F$, are to be matched to six tasks, $1,2,3,4,5$ and 6 .\\
The following adjacency matrix shows the possible matching of people to tasks.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& Task 1 & Task 2 & Task 3 & Task 4 & Task 5 & Task 6 \\
\hline
$\boldsymbol { A }$ & 0 & 0 & 1 & 0 & 1 & 1 \\
\hline
B & 0 & 1 & 0 & 1 & 0 & 0 \\
\hline
$\boldsymbol { C }$ & 0 & 1 & 0 & 0 & 0 & 1 \\
\hline
$\boldsymbol { D }$ & 0 & 0 & 0 & 1 & 0 & 0 \\
\hline
$E$ & 1 & 0 & 1 & 0 & 1 & 0 \\
\hline
$\boldsymbol { F }$ & 0 & 0 & 0 & 1 & 1 & 0 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Show this information on a bipartite graph.
\item Initially, $A$ is matched to task 3, $B$ to task 4, $C$ to task 2 and $E$ to task 5. From this initial matching, use the maximum matching algorithm to obtain a complete matching. List your complete matching.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2008 Q1 [7]}}