| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| 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 standard textbook application of the alternating path algorithm for bipartite matching. The initial matching and structure are given, requiring only mechanical execution of a well-defined algorithm with clear steps. No problem-solving insight or novel approach is needed—just recall and application of the standard D1 procedure. |
| Spec | 7.02r Graph modelling: model and solve problems using graphs |
| Person | Task |
| Andy | 1,3 |
| Bob | 1,4 |
| Colin | 2,3 |
| Dev | \(4,5,6\) |
| Eric | \(2,5,6\) |
| Faisal | 1,3 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Bipartite graph with People on left: Andy, Bob, Colin, Dev, Eric, Faisal and Tasks on right: 1,2,3,4,5,6 | B1 | Two distinct sets clearly labelled |
| Edges: Andy–1, Andy–3, Bob–1, Bob–4, Colin–2, Colin–3, Dev–4, Dev–5, Dev–6, Eric–2, Eric–5, Eric–6, Faisal–1, Faisal–3 | B1 | All edges correct, no extras |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Initial matching: Bob–1, Colin–3, Dev–5, Eric–2 | B1 | Stated or implied |
| Try to match Andy: Andy–1, but 1 is taken by Bob. Bob can take 4 (free). Alternating path: Andy–1–Bob–4 | M1 | Correct alternating path attempted from unmatched person |
| Change matching: Andy–1, Bob–4, Colin–3, Dev–5, Eric–2 | A1 | Correct updated matching |
| Try to match Faisal: Faisal–1, but 1 taken by Andy. Andy–3, but 3 taken by Colin. Colin–2, but 2 taken by Eric. Eric–5, but 5 taken by Dev. Dev–6 (free). Alternating path: Faisal–1–Andy–3–Colin–2–Eric–5–Dev–6 | M1 | Correct alternating path for Faisal |
| Complete matching: Andy–1, Bob–4, Colin–2 (or 3), Dev–6, Eric–5 (or 2), Faisal–3 (or 1). Final: Faisal–3, Andy–1, Colin–2, Eric–5, Dev–6, Bob–4 | A1 | All six correctly matched |
# Question 1:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Bipartite graph with People on left: Andy, Bob, Colin, Dev, Eric, Faisal and Tasks on right: 1,2,3,4,5,6 | B1 | Two distinct sets clearly labelled |
| Edges: Andy–1, Andy–3, Bob–1, Bob–4, Colin–2, Colin–3, Dev–4, Dev–5, Dev–6, Eric–2, Eric–5, Eric–6, Faisal–1, Faisal–3 | B1 | All edges correct, no extras |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial matching: Bob–1, Colin–3, Dev–5, Eric–2 | B1 | Stated or implied |
| Try to match Andy: Andy–1, but 1 is taken by Bob. Bob can take 4 (free). Alternating path: Andy–1–Bob–4 | M1 | Correct alternating path attempted from unmatched person |
| Change matching: Andy–1, Bob–4, Colin–3, Dev–5, Eric–2 | A1 | Correct updated matching |
| Try to match Faisal: Faisal–1, but 1 taken by Andy. Andy–3, but 3 taken by Colin. Colin–2, but 2 taken by Eric. Eric–5, but 5 taken by Dev. Dev–6 (free). Alternating path: Faisal–1–Andy–3–Colin–2–Eric–5–Dev–6 | M1 | Correct alternating path for Faisal |
| Complete matching: Andy–1, Bob–4, Colin–2 (or 3), Dev–6, Eric–5 (or 2), Faisal–3 (or 1). Final: Faisal–3, Andy–1, Colin–2, Eric–5, Dev–6, Bob–4 | A1 | All six correctly matched |
---1 Six people, Andy, Bob, Colin, Dev, Eric and Faisal, are to be allocated to six tasks, $1,2,3,4,5$ and 6 . The following table shows the tasks that each person is able to undertake.
\begin{center}
\begin{tabular}{ | l | l | }
\hline
\multicolumn{1}{|r|}{Person} & \multicolumn{1}{r|}{Task} \\
\hline
Andy & 1,3 \\
\hline
Bob & 1,4 \\
\hline
Colin & 2,3 \\
\hline
Dev & $4,5,6$ \\
\hline
Eric & $2,5,6$ \\
\hline
Faisal & 1,3 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Represent this information on a bipartite graph.
\item Initially, Bob is allocated to task 1, Colin to task 3, Dev to task 5 and Eric to task 2.
Demonstrate, by using an alternating path algorithm from this initial matching, how each person can be allocated to a different task.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2013 Q1 [7]}}