| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| Session | January |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Adjacency matrix from bipartite graph |
| Difficulty | Easy -1.2 This is a standard D1 bipartite matching question requiring routine application of the Hungarian algorithm or alternating path method. Part (a) is straightforward matrix construction from a graph, and part (b) follows a prescribed algorithmic procedure with no novel problem-solving required—significantly easier than average A-level maths questions. |
| Spec | 7.02p Networks: weighted graphs, modelling connections7.02q Adjacency matrix: and weighted matrix representation |
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{figure_1}
\begin{enumerate}[label=(\alph*)]
\item Represent this information in an adjacency matrix. [2]
\item Initially, $B$ is assigned to task 5, $D$ to task 2, $E$ to task 4 and $F$ to task 3.
Demonstrate, by using an algorithm from this initial matching, how each person can be allocated to a task. [5]
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2011 Q1 [7]}}