| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Easy -1.2 This is a straightforward application of the maximum matching algorithm with clear instructions. Students are given the initial matching and explicitly told to use an alternating path, making it a guided exercise in a standard D1 technique rather than requiring problem-solving insight. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02f Bipartite test: colouring argument |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Bipartite graph drawn with correct connections between \(\{A,B,C,D,E\}\) and \(\{7,8,9,10,11\}\) | M1, A2 | 3 \((-1\) EE\()\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Initial matching: \(A8, B10, C9, E11\) | M1 A1 | Starting from \(D7\) |
| Path: \(D \to 9 \to C \to 8 \to A \to 7\) | A1 | \(D \to 9 \to C\) or \(7 \to A \to 8\) |
| Match: \(A7, B10, C8, D9, E11\) | B1 | 4 |
| Total: 7 |
## Question 4(a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Bipartite graph drawn with correct connections between $\{A,B,C,D,E\}$ and $\{7,8,9,10,11\}$ | M1, A2 | **3** $(-1$ EE$)$ |
## Question 4(b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial matching: $A8, B10, C9, E11$ | M1 A1 | Starting from $D7$ |
| Path: $D \to 9 \to C \to 8 \to A \to 7$ | A1 | $D \to 9 \to C$ or $7 \to A \to 8$ |
| Match: $A7, B10, C8, D9, E11$ | B1 | **4** |
| **Total: 7** | | |
---4 The Head Teacher of a school is allocating five teachers, Amy ( $A$ ), Ben ( $B$ ), Celia ( $C$ ), Duncan ( $D$ ), and Erica ( $E$ ), to the five posts of Head of Year 7, 8, 9, 10 and 11. The five teachers are asked which year(s) they would be willing to take. This information is shown below.
Amy is willing to take Year 7 or Year 8 .
Ben is willing to take Year 7, Year 8 or Year 10.
Celia is willing to take Year 8, Year 9 or Year 11.
Duncan will take only Year 9.\\
Erica will take only Year 11.
\begin{enumerate}[label=(\alph*)]
\item Show this information on a bipartite graph.
\item Initially the Head Teacher assigns Amy to Year 8, Ben to Year 10, Celia to Year 9 and Erica to Year 11.
Demonstrate, by using an alternating path from this initial matching, how each teacher can be matched to a year that they are willing to take.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2005 Q4 [9]}}