| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | January |
| 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 straightforward application of the maximum matching algorithm with an alternating path already started for the student. Drawing a bipartite graph is routine, and completing the given alternating path D-M-E-K requires only following the mechanical procedure with minimal problem-solving. Significantly easier than average A-level questions. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02q Adjacency matrix: and weighted matrix representation |
| Person | Task |
| \(A\) | \(J , N\) |
| \(B\) | \(J , L\) |
| \(C\) | \(L , N\) |
| \(D\) | \(M , N\) |
| \(E\) | \(K , M\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Bipartite graph drawn with correct edges | M1 | Bipartite graph |
| All connections correct | A1 | All correct |
| Total: 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Path \(D-M(+)E-K\) identified | M1, A1 | Attempt at path \(D-M+\) |
| Match: \(AN, BJ, CL, DM, EK\) | B1 | SC: \(K-E+M-D\) B1 |
| Total: 3 |
## Question 1:
### Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Bipartite graph drawn with correct edges | M1 | Bipartite graph |
| All connections correct | A1 | All correct |
| **Total: 2** | | |
### Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Path $D-M(+)E-K$ identified | M1, A1 | Attempt at path $D-M+$ |
| Match: $AN, BJ, CL, DM, EK$ | B1 | SC: $K-E+M-D$ B1 |
| **Total: 3** | | |
---1 Five people, $A , B , C , D$ and $E$, are to be matched to five tasks, $J , K , L , M$ and $N$. The table shows the tasks that each person is able to undertake.
\begin{center}
\begin{tabular}{ | c | l | }
\hline
Person & Task \\
\hline
$A$ & $J , N$ \\
\hline
$B$ & $J , L$ \\
\hline
$C$ & $L , N$ \\
\hline
$D$ & $M , N$ \\
\hline
$E$ & $K , M$ \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Show this information on a bipartite graph.
\item Initially, $A$ is matched to task $N , B$ to task $J , C$ to task $L$, and $E$ to task $M$.
Complete the alternating path $D - M \ldots$, from this initial matching, to demonstrate how each person can be matched to a task.\\
(3 marks)
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2008 Q1 [5]}}