| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | January |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Moderate -0.8 This is a standard textbook application of the maximum matching algorithm (Hungarian algorithm or alternating path method) in bipartite graphs. Part (a) is routine matrix construction, and part (b) follows a prescribed algorithmic procedure with an initial matching provided. The question requires careful execution but no problem-solving insight or novel approach—it's testing whether students can apply a learned algorithm mechanically. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02r Graph modelling: model and solve problems using graphs |
2 Six people, $A , B , C , D , E$ and $F$, are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following bipartite graph shows the tasks that each of the people is able to undertake.\\
\includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-3_401_517_429_751}\\
\includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-3_408_520_943_751}
\begin{enumerate}[label=(\alph*)]
\item Represent this information in an adjacency matrix.
\item Initially, $B$ is assigned to task $1 , C$ to task $2 , D$ to task 4, and $E$ to task 5 .
Demonstrate, by using an algorithm from this initial matching, how each person can be allocated to a task.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2009 Q2 [7]}}