| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | June |
| Marks | 6 |
| 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 matching algorithm with clear instructions. Students are given the initial matching and simply need to draw a bipartite graph and find one alternating path to improve the matching - a routine D1 procedure requiring minimal problem-solving or insight. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02r Graph modelling: model and solve problems using graphs |
| Person | Tasks |
| \(A\) | \(1,3,5\) |
| \(B\) | 2,4 |
| \(C\) | 2 |
| \(D\) | 4,5 |
| \(E\) | 3,5 |
1 Five people, $A , B , C , D$ and $E$, are to be matched to five tasks, 1, 2, 3, 4 and 5. The table shows which tasks each person can do.
\begin{center}
\begin{tabular}{ | l | l | }
\hline
Person & Tasks \\
\hline
$A$ & $1,3,5$ \\
\hline
$B$ & 2,4 \\
\hline
$C$ & 2 \\
\hline
$D$ & 4,5 \\
\hline
$E$ & 3,5 \\
\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 .
Use an alternating path from this initial matching to find a complete matching.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2006 Q1 [6]}}