| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Moderate -0.8 This is a standard textbook application of the maximum matching algorithm with clear step-by-step instructions. The bipartite graph drawing is routine, part (b) requires simple observation that D can only do task 4, and part (c) applies a well-practiced algorithm with an initial matching provided. No novel problem-solving or insight required beyond following the taught procedure. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02r Graph modelling: model and solve problems using graphs |
| Task 1 | Task 2 | Task 3 | Task 4 | Task 5 | Task 6 | |
| A | 0 | 1 | 0 | 1 | 0 | 0 |
| B | 1 | 0 | 1 | 0 | 1 | 0 |
| \(\boldsymbol { C }\) | 0 | 0 | 1 | 0 | 1 | 1 |
| D | 0 | 0 | 0 | 1 | 0 | 0 |
| E | 0 | 1 | 0 | 0 | 0 | 1 |
| \(\boldsymbol { F }\) | 0 | 0 | 0 | 1 | 1 | 0 |
1 Six people, $A , B , C , D , E$ and $F$, are to be matched to six tasks, $1,2,3,4,5$ and 6 . The following adjacency matrix shows the possible matching of people to tasks.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& Task 1 & Task 2 & Task 3 & Task 4 & Task 5 & Task 6 \\
\hline
A & 0 & 1 & 0 & 1 & 0 & 0 \\
\hline
B & 1 & 0 & 1 & 0 & 1 & 0 \\
\hline
$\boldsymbol { C }$ & 0 & 0 & 1 & 0 & 1 & 1 \\
\hline
D & 0 & 0 & 0 & 1 & 0 & 0 \\
\hline
E & 0 & 1 & 0 & 0 & 0 & 1 \\
\hline
$\boldsymbol { F }$ & 0 & 0 & 0 & 1 & 1 & 0 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Show this information on a bipartite graph.
\item At first $F$ insists on being matched to task 4. Explain why, in this case, a complete matching is impossible.
\item To find a complete matching $F$ agrees to be assigned to either task 4 or task 5.
Initially $B$ is matched to task 3, $C$ to task 6, $E$ to task 2 and $F$ to task 4.\\
From this initial matching, use the maximum matching algorithm to obtain a complete matching. List your complete matching.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2007 Q1 [9]}}