| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Moderate -0.5 This is a standard application of the maximum matching algorithm with a given initial matching. Part (a) requires only reading an adjacency matrix and drawing edges (routine skill), while part (b) applies a bookwork algorithm (finding alternating paths) with no novel problem-solving. It's slightly easier than average because the algorithm is mechanical and the graph is small (6×6). |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02q Adjacency matrix: and weighted matrix representation |
| 1 | 2 | 3 | 4 | 5 | 6 | |
| \(\boldsymbol { A }\) | 1 | 0 | 1 | 0 | 1 | 0 |
| B | 0 | 1 | 0 | 1 | 0 | 0 |
| \(\boldsymbol { C }\) | 0 | 1 | 0 | 0 | 0 | 1 |
| \(\boldsymbol { D }\) | 0 | 0 | 0 | 1 | 0 | 0 |
| E | 0 | 0 | 1 | 0 | 1 | 1 |
| \(\boldsymbol { F }\) | 0 | 0 | 0 | 1 | 1 | 0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct bipartite graph with vertices A,B,C,D,E,F on left and 1,2,3,4,5,6 on right | B1 | Edges: A-1, A-3, A-5; B-2, B-4; C-2, C-6; D-4; E-3, E-5, E-6; F-4, F-5 |
| All edges correct with no extras | B1 | Both marks require fully correct graph |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Identify unmatched vertices: B (or D or F) | M1 | Must attempt augmenting path from an unmatched vertex |
| Augmenting path e.g. \(D - 4 = B - 2\) | A1 | Correct alternating path shown |
| Change status along path | M1 | Apply the augmenting path correctly |
| Second augmenting path e.g. \(F - 5 = E - 6\) or \(F - 4 = D\) | M1 | Attempt second augmenting path |
| Complete matching: A-3, B-2 (or B-4), C-6, D-4 (or D-4), E-5, F-4 (or similar valid complete matching) | A1 | All 6 vertices matched correctly |
# Question 1:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct bipartite graph with vertices A,B,C,D,E,F on left and 1,2,3,4,5,6 on right | B1 | Edges: A-1, A-3, A-5; B-2, B-4; C-2, C-6; D-4; E-3, E-5, E-6; F-4, F-5 |
| All edges correct with no extras | B1 | Both marks require fully correct graph |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Identify unmatched vertices: B (or D or F) | M1 | Must attempt augmenting path from an unmatched vertex |
| Augmenting path e.g. $D - 4 = B - 2$ | A1 | Correct alternating path shown |
| Change status along path | M1 | Apply the augmenting path correctly |
| Second augmenting path e.g. $F - 5 = E - 6$ or $F - 4 = D$ | M1 | Attempt second augmenting path |
| Complete matching: A-3, B-2 (or B-4), C-6, D-4 (or D-4), E-5, F-4 (or similar valid complete matching) | A1 | All 6 vertices matched correctly |
---1
\begin{enumerate}[label=(\alph*)]
\item Draw a bipartite graph representing the following adjacency matrix.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& 1 & 2 & 3 & 4 & 5 & 6 \\
\hline
$\boldsymbol { A }$ & 1 & 0 & 1 & 0 & 1 & 0 \\
\hline
B & 0 & 1 & 0 & 1 & 0 & 0 \\
\hline
$\boldsymbol { C }$ & 0 & 1 & 0 & 0 & 0 & 1 \\
\hline
$\boldsymbol { D }$ & 0 & 0 & 0 & 1 & 0 & 0 \\
\hline
E & 0 & 0 & 1 & 0 & 1 & 1 \\
\hline
$\boldsymbol { F }$ & 0 & 0 & 0 & 1 & 1 & 0 \\
\hline
\end{tabular}
\end{center}
\item Initially, $A$ is matched to $3 , B$ is matched to $4 , C$ is matched to 2 , and $E$ is matched to 5 . Use the maximum matching algorithm, from this initial matching, to find a complete matching. List your complete matching.\\
\begin{center}
\begin{tabular}{|l|l|}
\hline
\begin{tabular}{l}
\end{tabular} & \\
\hline
\end{tabular}
\end{center}
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2009 Q1 [7]}}