| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| Marks | 6 |
| 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 taught in D1. Students need to draw a standard bipartite graph and apply the alternating path method with an initial matching already provided. The alternating path is short and relatively obvious (D is unmatched, can take V, forcing A to switch to R, forcing B to switch to T, forcing C to switch to... wait, this requires careful tracking but follows the standard algorithm). While it requires systematic application of the technique, it's a routine textbook-style question with no novel problem-solving required. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02q Adjacency matrix: and weighted matrix representation |
| Person | Tasks |
| \(A\) | \(R , V\) |
| \(B\) | \(R , T\) |
| \(C\) | \(T , V\) |
| \(D\) | \(U , V\) |
| \(E\) | \(S , U\) |
| Answer | Marks | Guidance |
|---|---|---|
| Bipartite graph with correct matching shown | M1, A1 | All correct (2 marks total) |
| Answer | Marks | Guidance |
|---|---|---|
| Start with \(D\) (or \(S\)): \(D - U + E - S\) or \(D - V + A - R + B - T + C - V + D - U + E - S\) | B1, M1, A1 | For attempt at any path |
| Match: \(AV, BR, CT, DU, ES\) or \(AR, BT, CY, DU, ES\) | B1 | Must be 5 pairs (4 marks total) |
**2(a)**
| Bipartite graph with correct matching shown | M1, A1 | All correct (2 marks total) |
**2(b)**
| Start with $D$ (or $S$): $D - U + E - S$ or $D - V + A - R + B - T + C - V + D - U + E - S$ | B1, M1, A1 | For attempt at any path |
| Match: $AV, BR, CT, DU, ES$ or $AR, BT, CY, DU, ES$ | B1 | Must be 5 pairs (4 marks total) |2 Five people $A , B , C , D$ and $E$ are to be matched to five tasks $R , S , T , U$ and $V$.\\
The table shows the tasks that each person is able to undertake.
\begin{center}
\begin{tabular}{ | c | c | }
\hline
Person & Tasks \\
\hline
$A$ & $R , V$ \\
\hline
$B$ & $R , T$ \\
\hline
$C$ & $T , V$ \\
\hline
$D$ & $U , V$ \\
\hline
$E$ & $S , U$ \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Show this information on a bipartite graph.
\item Initially, $A$ is matched to task $V , B$ to task $R , C$ to task $T$, and $E$ to task $U$.
Demonstrate, by using an alternating path from this initial matching, how each person can be matched to a task.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2007 Q2 [6]}}