| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | January |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Draw bipartite graph from adjacency matrix |
| Difficulty | Easy -1.8 This is a routine procedural question from Decision Maths requiring direct translation of an adjacency matrix into a bipartite graph diagram, followed by a simple observation about why complete matching fails (likely that tasks 3 and 4 have limited connections). It tests basic recall and diagram-drawing skills with minimal problem-solving or conceptual depth. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02f Bipartite test: colouring argument |
| \cline { 2 - 7 } \multicolumn{1}{c|}{} | \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) | \(\mathbf { 5 }\) | \(\mathbf { 6 }\) |
| \(\boldsymbol { A }\) | 1 | 1 | 0 | 0 | 1 | 1 |
| \(\boldsymbol { B }\) | 0 | 1 | 0 | 0 | 1 | 1 |
| \(\boldsymbol { C }\) | 1 | 0 | 0 | 0 | 1 | 1 |
| \(\boldsymbol { D }\) | 0 | 1 | 1 | 1 | 0 | 1 |
| \(\boldsymbol { E }\) | 0 | 0 | 0 | 0 | 1 | 1 |
| \(\boldsymbol { F }\) | 0 | 0 | 0 | 0 | 0 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct bipartite graph with vertices \(A,B,C,D,E,F\) on one side and \(1,2,3,4,5,6\) on the other | B1 | Correct two sets of vertices |
| All edges correctly drawn corresponding to 1s in the adjacency matrix | B1 | All edges correct, no extras |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Node \(F\) is only connected to task 6 | B1 | Identifying \(F\) connects only to 6 |
| Node \(E\) is only connected to tasks 5 and 6 | B1 | Identifying \(E\) connects only to 5 and 6 |
| Since \(F\) must take task 6, \(E\) can only take task 5. But then considering \(\{B, E, F\}\): these three people can only be assigned to tasks \(\{5, 6\}\) — only 2 tasks for 3 people, so by Hall's theorem a complete matching is impossible | B1 | Complete argument, e.g. using Hall's condition: \( |
# Question 2(a): Bipartite Graph
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct bipartite graph with vertices $A,B,C,D,E,F$ on one side and $1,2,3,4,5,6$ on the other | B1 | Correct two sets of vertices |
| All edges correctly drawn corresponding to 1s in the adjacency matrix | B1 | All edges correct, no extras |
---
# Question 2(b): Complete Matching Impossible
| Answer | Marks | Guidance |
|--------|-------|----------|
| Node $F$ is only connected to task 6 | B1 | Identifying $F$ connects only to 6 |
| Node $E$ is only connected to tasks 5 and 6 | B1 | Identifying $E$ connects only to 5 and 6 |
| Since $F$ must take task 6, $E$ can only take task 5. But then considering $\{B, E, F\}$: these three people can only be assigned to tasks $\{5, 6\}$ — only 2 tasks for 3 people, so by Hall's theorem a complete matching is impossible | B1 | Complete argument, e.g. using Hall's condition: $|N(\{B,E,F\})| = |\{5,6\}| = 2 < 3$ |
---2
\begin{enumerate}[label=(\alph*)]
\item Draw a bipartite graph representing the following adjacency matrix.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\cline { 2 - 7 }
\multicolumn{1}{c|}{} & $\mathbf { 1 }$ & $\mathbf { 2 }$ & $\mathbf { 3 }$ & $\mathbf { 4 }$ & $\mathbf { 5 }$ & $\mathbf { 6 }$ \\
\hline
$\boldsymbol { A }$ & 1 & 1 & 0 & 0 & 1 & 1 \\
\hline
$\boldsymbol { B }$ & 0 & 1 & 0 & 0 & 1 & 1 \\
\hline
$\boldsymbol { C }$ & 1 & 0 & 0 & 0 & 1 & 1 \\
\hline
$\boldsymbol { D }$ & 0 & 1 & 1 & 1 & 0 & 1 \\
\hline
$\boldsymbol { E }$ & 0 & 0 & 0 & 0 & 1 & 1 \\
\hline
$\boldsymbol { F }$ & 0 & 0 & 0 & 0 & 0 & 1 \\
\hline
\end{tabular}
\end{center}
\item Given that $A , B , C , D , E$ and $F$ represent six people and that 1, 2, 3, 4, 5 and 6 represent six tasks to which they may be assigned, explain why a complete matching is impossible.
\begin{verbatim}
QUESTION
PART
REFERENCE
\end{verbatim}
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2012 Q2 [5]}}