| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | January |
| Marks | 4 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Explain why complete matching impossible |
| Difficulty | Moderate -0.8 This is a straightforward application of Hall's Marriage Theorem requiring students to identify that vertices 1, 2, 3 are only connected to subset {A, E} (2 people), violating the matching condition. The bipartite graph is given via adjacency matrix, and the explanation requires only basic observation rather than algorithmic work or proof. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02q Adjacency matrix: and weighted matrix representation |
| 1 | 2 | 3 | 4 | 5 | |
| A | 0 | 0 | 0 | 0 | 1 |
| \(\boldsymbol { B }\) | 0 | 0 | 0 | 1 | 1 |
| \(\boldsymbol { C }\) | 0 | 1 | 0 | 1 | 1 |
| \(\boldsymbol { D }\) | 0 | 0 | 0 | 1 | 1 |
| \(\boldsymbol { E }\) | 1 | 1 | 1 | 0 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Bipartite graph with nodes \(A, B, C, D, E\) on one side and \(1, 2, 3, 4, 5\) on the other side | B1 | Correct two sets of vertices |
| Edges: \(A-5\); \(B-4, B-5\); \(C-2, C-4, C-5\); \(D-4, D-5\); \(E-1, E-2, E-3, E-5\) | B1 | All edges correct and no extras |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(\{A, B, D\}\) are only connected to tasks \(\{4, 5\}\) — three people but only two tasks available to them | M1 | Identifying a subset of people whose neighbourhood is smaller |
| By Hall's theorem, since \( | \{A,B,D\} | = 3 > 2 = |
# Question 1:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Bipartite graph with nodes $A, B, C, D, E$ on one side and $1, 2, 3, 4, 5$ on the other side | B1 | Correct two sets of vertices |
| Edges: $A-5$; $B-4, B-5$; $C-2, C-4, C-5$; $D-4, D-5$; $E-1, E-2, E-3, E-5$ | B1 | All edges correct and no extras |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $\{A, B, D\}$ are only connected to tasks $\{4, 5\}$ — three people but only two tasks available to them | M1 | Identifying a subset of people whose neighbourhood is smaller |
| By Hall's theorem, since $|\{A,B,D\}| = 3 > 2 = |\{4,5\}|$, a complete matching is impossible | A1 | Correct application of Hall's condition with correct sets cited |
---1
\begin{enumerate}[label=(\alph*)]
\item Draw a bipartite graph to represent the following adjacency matrix.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& 1 & 2 & 3 & 4 & 5 \\
\hline
A & 0 & 0 & 0 & 0 & 1 \\
\hline
$\boldsymbol { B }$ & 0 & 0 & 0 & 1 & 1 \\
\hline
$\boldsymbol { C }$ & 0 & 1 & 0 & 1 & 1 \\
\hline
$\boldsymbol { D }$ & 0 & 0 & 0 & 1 & 1 \\
\hline
$\boldsymbol { E }$ & 1 & 1 & 1 & 0 & 1 \\
\hline
\end{tabular}
\end{center}
\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 2013 Q1 [4]}}