| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Moderate -0.8 This is a straightforward application of a standard D1 algorithm (alternating paths for maximum matching) with the initial matching already provided. Students simply need to draw a bipartite graph from a matrix (routine skill) and mechanically apply the alternating path algorithm following the prescribed method. No problem-solving insight or novel thinking required—pure algorithmic execution. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02q Adjacency matrix: and weighted matrix representation |
| \(\boldsymbol { U }\) | \(V\) | \(\boldsymbol { W }\) | \(\boldsymbol { X }\) | \(\boldsymbol { Y }\) | \(\boldsymbol { Z }\) | |
| \(\boldsymbol { A }\) | 1 | 0 | 1 | 0 | 1 | 0 |
| \(\boldsymbol { B }\) | 0 | 1 | 0 | 1 | 0 | 0 |
| \(\boldsymbol { C }\) | 0 | 1 | 0 | 0 | 0 | 1 |
| \(\boldsymbol { D }\) | 0 | 0 | 0 | 1 | 0 | 0 |
| \(\boldsymbol { E }\) | 0 | 0 | 1 | 0 | 1 | 1 |
| \(\boldsymbol { F }\) | 0 | 0 | 0 | 1 | 1 | 0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Bipartite graph drawn with correct crossings shown | M1 | Must be in part (a) |
| Fully correct diagram | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(D-X+B-V+C\) | M1 | Starting from D, F, Z, U |
| \(-Z\) | A1 | |
| \(F-Y+E-W+A-U\) | M1A1 | Same |
| Match: \(AU, BV, CZ, DX, EW, FY\) | B1 |
## Question 1:
### Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Bipartite graph drawn with correct crossings shown | M1 | Must be in part (a) |
| Fully correct diagram | A1 | |
**Total: 2 marks**
### Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $D-X+B-V+C$ | M1 | Starting from D, F, Z, U |
| $-Z$ | A1 | |
| $F-Y+E-W+A-U$ | M1A1 | Same |
| Match: $AU, BV, CZ, DX, EW, FY$ | B1 | |
**Total: 5 marks**
---1
\begin{enumerate}[label=(\alph*)]
\item Draw a bipartite graph representing the following adjacency matrix.\\
(2 marks)
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& $\boldsymbol { U }$ & $V$ & $\boldsymbol { W }$ & $\boldsymbol { X }$ & $\boldsymbol { Y }$ & $\boldsymbol { Z }$ \\
\hline
$\boldsymbol { A }$ & 1 & 0 & 1 & 0 & 1 & 0 \\
\hline
$\boldsymbol { 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
$\boldsymbol { E }$ & 0 & 0 & 1 & 0 & 1 & 1 \\
\hline
$\boldsymbol { F }$ & 0 & 0 & 0 & 1 & 1 & 0 \\
\hline
\end{tabular}
\end{center}
\item Given that initially $A$ is matched to $W , B$ is matched to $X , C$ is matched to $V$, and $E$ is matched to $Y$, use the alternating path algorithm, from this initial matching, to find a complete matching. List your complete matching.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2006 Q1 [7]}}