| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | June |
| Marks | 4 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Draw bipartite graph from adjacency matrix |
| Difficulty | Easy -1.2 This is a straightforward D1 question requiring basic graph drawing from a matrix (routine skill) and simple observation that three people (A, D, E) can only do two tasks (1, 5), violating Hall's marriage condition. No complex algorithm or proof needed, just direct reading of the matrix. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02r Graph modelling: model and solve problems using graphs |
\begin{enumerate}[label=(\alph*)]
\item Draw a bipartite graph representing the following adjacency matrix. [2 marks]
$$\begin{array}{c|ccccc}
& 1 & 2 & 3 & 4 & 5 \\
\hline
A & 1 & 0 & 0 & 0 & 1 \\
B & 0 & 1 & 1 & 1 & 0 \\
C & 0 & 1 & 1 & 1 & 0 \\
D & 1 & 0 & 0 & 0 & 1 \\
E & 1 & 0 & 0 & 0 & 1 \\
\end{array}$$
\item If $A$, $B$, $C$, $D$ and $E$ represent five people and 1, 2, 3, 4 and 5 represent five tasks to which they are to be assigned, explain why a complete matching is impossible. [2 marks]
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2010 Q1 [4]}}