| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| 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 textbook application of the maximum matching algorithm (likely Hungarian or alternating path method) with a small bipartite graph. The question provides the initial matching and requires systematic application of a learned algorithm with clear documentation of alternating paths. While it requires careful execution across multiple steps, it involves direct application of a prescribed method rather than problem-solving insight or novel reasoning. |
| 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 | 0 | 0 |
| \(\boldsymbol { B }\) | 1 | 1 | 0 | 0 | 0 | 1 |
| C | 0 | 1 | 0 | 1 | 0 | 0 |
| \(\boldsymbol { D }\) | 0 | 1 | 0 | 0 | 1 | 0 |
| E | 0 | 0 | 1 | 0 | 1 | 0 |
| F | 0 | 0 | 0 | 0 | 1 | 0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Bipartite graph with people \(A, B, C, D, E, F\) on one side and tasks \(1, 2, 3, 4, 5, 6\) on other side | B1 | Two distinct sets clearly shown |
| Correct edges: \(A\)-1, \(A\)-3; \(B\)-1, \(B\)-2, \(B\)-6; \(C\)-2, \(C\)-4; \(D\)-2, \(D\)-5; \(E\)-3, \(E\)-5; \(F\)-5 | B1 | All edges correct, no extras |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Initial matching: \(A\)=3, \(B\)=2, \(C\)=4, \(D\)=5 | — | Stated in question |
| Unmatched people: \(E\) and \(F\) | B1 | Identifying unmatched persons |
| Try \(E\): alternating path \(E\)-3-\(A\)-1 | M1 | Valid alternating path from unmatched person |
| Augment: \(E\)=3, \(A\)=1; updated matching: \(A\)=1, \(B\)=2, \(C\)=4, \(D\)=5, \(E\)=3 | A1 | Correct augmentation |
| Try \(F\): \(F\)-5-\(D\)-2-\(B\)-6 | M1 | Valid alternating path from \(F\) |
| Augment: \(F\)=5, \(D\)=2, \(B\)=6; maximum matching: \(A\)=1, \(B\)=6, \(C\)=4, \(D\)=2, \(E\)=3, \(F\)=5 | A1 | Correct complete maximum matching |
# Question 1:
## Part (a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Bipartite graph with people $A, B, C, D, E, F$ on one side and tasks $1, 2, 3, 4, 5, 6$ on other side | B1 | Two distinct sets clearly shown |
| Correct edges: $A$-1, $A$-3; $B$-1, $B$-2, $B$-6; $C$-2, $C$-4; $D$-2, $D$-5; $E$-3, $E$-5; $F$-5 | B1 | All edges correct, no extras |
## Part (b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial matching: $A$=3, $B$=2, $C$=4, $D$=5 | — | Stated in question |
| Unmatched people: $E$ and $F$ | B1 | Identifying unmatched persons |
| Try $E$: alternating path $E$-3-$A$-1 | M1 | Valid alternating path from unmatched person |
| Augment: $E$=3, $A$=1; updated matching: $A$=1, $B$=2, $C$=4, $D$=5, $E$=3 | A1 | Correct augmentation |
| Try $F$: $F$-5-$D$-2-$B$-6 | M1 | Valid alternating path from $F$ |
| Augment: $F$=5, $D$=2, $B$=6; maximum matching: $A$=1, $B$=6, $C$=4, $D$=2, $E$=3, $F$=5 | A1 | Correct complete maximum matching |
---1 Six people, $A , B , C , D , E$ and $F$, are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following adjacency matrix shows the tasks that each of the people is able to undertake.
\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 & 0 & 0 \\
\hline
$\boldsymbol { B }$ & 1 & 1 & 0 & 0 & 0 & 1 \\
\hline
C & 0 & 1 & 0 & 1 & 0 & 0 \\
\hline
$\boldsymbol { D }$ & 0 & 1 & 0 & 0 & 1 & 0 \\
\hline
E & 0 & 0 & 1 & 0 & 1 & 0 \\
\hline
F & 0 & 0 & 0 & 0 & 1 & 0 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Represent this information in a bipartite graph.
\item Initially, $A$ is assigned to task 3, $B$ to task 2, $C$ to task 4 and $D$ to task 5 .
Use an algorithm from this initial matching to find a maximum matching, listing your alternating paths.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2011 Q1 [7]}}