| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| 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 standard textbook application of the maximum matching algorithm (alternating path method) on a small bipartite graph with clear structure. The question provides the initial matching and students simply need to follow the algorithmic procedure they've learned. Drawing the bipartite graph is routine, and finding the alternating path requires minimal problem-solving since the graph is small (6 vertices each side) and the initial matching is given. This is easier than average A-level content as it's pure algorithmic application with no novel insight required. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02r Graph modelling: model and solve problems using graphs |
| Girl | Pizza |
| Alfonsa (A) | Margherita (M), Pepperoni (P), Stagioni (S) |
| Bianca (B) | Neapolitana (N), Romana (R) |
| Claudia (C) | Neapolitana (N), Viennese (V) |
| Desiree (D) | Romana (R), Stagioni (S) |
| Erika (E) | Pepperoni (P), Stagioni (S), Viennese (V) |
| Flavia (F) | Romana (R) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Bipartite graph with two sets of vertices (A,B,C,D,E,F and M,N,P,R,S,V), labelled, with 6+ edges correctly drawn | M1 | Bipartite graph, 2 sets of (some) vertices, labelled, 6+ edges |
| Fully correct graph | A1 | Total: 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Initial matching: AP, BR, CN, ES | — | — |
| First path e.g. \(D-R \not- B \;V-C \not- N \; M-A \not- P\) | M1 | 1 correct path |
| Second path e.g. \(F-R \not- B \; D-S \not- E \; V-E \not- S\) | M1 | 2nd path started correctly, must be different start point from 1st path (allow \(F-R \not- D\) for 2nd M1 if \(D-R \not- B\) first) |
| \(D-R \not- B-N \not- C-V\) | A1 | or reverse |
| \(F-R \not- D-S \not- E-P \not- A-M\) | A1 | or reverse, but two paths must be in this order |
| OR \(D-S \not- E-V\) and \(F-R \not- B-N \not- C-V \not- E-P \not- A-M\) | (A1)(A1) | or reverse; two paths must be in this order |
| OR \(F-R \not- B-N \not- C-V\) and \(D-S \not- E-P \not- A-M\) | (A1)(A1) | or reverse; the two paths can be in either order |
| Final matching: AM, BN, CV, DS, EP, FR | B1 | Must be written as a list. Total: 5 |
# Question 1:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Bipartite graph with two sets of vertices (A,B,C,D,E,F and M,N,P,R,S,V), labelled, with 6+ edges correctly drawn | M1 | Bipartite graph, 2 sets of (some) vertices, labelled, 6+ edges |
| Fully correct graph | A1 | Total: 2 |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial matching: AP, BR, CN, ES | — | — |
| First path e.g. $D-R \not- B \;V-C \not- N \; M-A \not- P$ | M1 | 1 correct path |
| Second path e.g. $F-R \not- B \; D-S \not- E \; V-E \not- S$ | M1 | 2nd path started correctly, must be different start point from 1st path (allow $F-R \not- D$ for 2nd M1 if $D-R \not- B$ first) |
| $D-R \not- B-N \not- C-V$ | A1 | or reverse |
| $F-R \not- D-S \not- E-P \not- A-M$ | A1 | or reverse, but two paths must be in this order |
| **OR** $D-S \not- E-V$ and $F-R \not- B-N \not- C-V \not- E-P \not- A-M$ | (A1)(A1) | or reverse; two paths must be in this order |
| **OR** $F-R \not- B-N \not- C-V$ and $D-S \not- E-P \not- A-M$ | (A1)(A1) | or reverse; the two paths can be in either order |
| Final matching: AM, BN, CV, DS, EP, FR | B1 | Must be written as a list. Total: 5 |
---1 Six girls, Alfonsa (A), Bianca (B), Claudia (C), Desiree (D), Erika (E) and Flavia (F), are going to a pizza restaurant. The restaurant provides a special menu of six different pizzas: Margherita (M), Neapolitana (N), Pepperoni (P), Romana (R), Stagioni (S) and Viennese (V).
The table shows the pizzas that each girl likes.
\begin{center}
\begin{tabular}{|l|l|}
\hline
Girl & Pizza \\
\hline
Alfonsa (A) & Margherita (M), Pepperoni (P), Stagioni (S) \\
\hline
Bianca (B) & Neapolitana (N), Romana (R) \\
\hline
Claudia (C) & Neapolitana (N), Viennese (V) \\
\hline
Desiree (D) & Romana (R), Stagioni (S) \\
\hline
Erika (E) & Pepperoni (P), Stagioni (S), Viennese (V) \\
\hline
Flavia (F) & Romana (R) \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Show this information on a bipartite graph.
\item Each girl is to eat a different pizza. Initially, the waiter brings six different pizzas and gives Alfonsa the Pepperoni, Bianca the Romana, Claudia the Neapolitana and Erika the Stagioni. The other two pizzas are put in the middle of the table.
From this initial matching, use the maximum matching algorithm to obtain a complete matching so that every girl gets a pizza that she likes. List your complete matching.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2010 Q1 [7]}}