| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2009 |
| Session | June |
| Marks | 13 |
| 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 paths) with clearly defined steps. Part (a) involves routine bipartite graph construction and finding alternating paths using a given initial matching. Part (b) appears to be an allocation problem setup. The question requires only direct application of a well-practiced algorithm with no novel problem-solving or insight needed. |
| Spec | 7.02g Eulerian graphs: vertex degrees and traversability7.02h Hamiltonian paths: and cycles |
| \(F\) | \(G\) | \(H\) | \(J\) | \(K\) | ||
| Avocado and bacon | \(( A )\) | \(\checkmark\) | \(\checkmark\) | |||
| Beef and horseradish | \(( B )\) | \(\checkmark\) | \(\checkmark\) | \(\checkmark\) | \(\checkmark\) | |
| Chicken and stuffing | \(( C )\) | \(\checkmark\) | \(\checkmark\) | |||
| Duck and plum sauce | \(( D )\) | \(\checkmark\) | \(\checkmark\) | |||
| Egg and tomato | \(( E )\) | \(\checkmark\) |
| \(F\) | \(G\) | \(H\) | \(J\) | \(K\) | ||
| Lemon | \(L\) | 8 | 8 | 8 | 8 | 1 |
| Mandarin | \(M\) | 4 | 8 | 6 | 4 | 2 |
| Nectarine | \(N\) | 9 | 9 | 9 | 7 | 1 |
| Orange | \(O\) | 4 | 6 | 5 | 4 | 3 |
| Peach | \(P\) | 6 | 9 | 7 | 5 | 0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Reduce rows: subtract row minimum from each row | M1 | Substantially correct attempt to reduce rows |
| Correct reduced rows matrix | A1 | cao |
| Reduce columns: subtract column minimum | M1 | Substantially correct attempt to reduce columns |
| Correct reduced columns matrix | A1 | cao |
| Cross out 0's using two (minimum no. of) lines | ||
| Augment by 1 | M1 | Substantially correct attempt at augmenting |
| Augmenting correctly | A1 | Augmenting correctly |
| Cross out 0's using three (minimum no. of) lines | ||
| Augment by 3 | M1 | Substantially correct attempt at augmenting (by more than 1 in a single step) |
| Augmenting correctly | A1 | Augmenting correctly |
| Lemon = Gwen, Mandarin = Fiona, Nectarine = Mr King, Orange = Helen, Peach = Jack | B1 | Correct allocation |
# Question 1(b): Hungarian Algorithm
| Answer/Working | Mark | Guidance |
|---|---|---|
| Reduce rows: subtract row minimum from each row | M1 | Substantially correct attempt to reduce rows |
| Correct reduced rows matrix | A1 | cao |
| Reduce columns: subtract column minimum | M1 | Substantially correct attempt to reduce columns |
| Correct reduced columns matrix | A1 | cao |
| Cross out 0's using two (minimum no. of) lines | | |
| Augment by 1 | M1 | Substantially correct attempt at augmenting |
| Augmenting correctly | A1 | Augmenting correctly |
| Cross out 0's using three (minimum no. of) lines | | |
| Augment by 3 | M1 | Substantially correct attempt at augmenting (by more than 1 in a single step) |
| Augmenting correctly | A1 | Augmenting correctly |
| Lemon = Gwen, Mandarin = Fiona, Nectarine = Mr King, Orange = Helen, Peach = Jack | B1 | Correct allocation |
---1
\begin{enumerate}[label=(\alph*)]
\item A café sells five different types of filled roll. Mr King buys one of each to take home to his family. The family consists of Mr King's daughter Fiona ( $F$ ), his mother Gwen ( $G$ ), his wife Helen ( $H$ ), his son Jack ( $J$ ) and Mr King ( $K$ ).
The table shows who likes which rolls.
\begin{center}
\begin{tabular}{ | l c | c | c | c | c | c | }
\hline
& & $F$ & $G$ & $H$ & $J$ & $K$ \\
\hline
Avocado and bacon & $( A )$ & $\checkmark$ & & $\checkmark$ & & \\
\hline
Beef and horseradish & $( B )$ & & $\checkmark$ & $\checkmark$ & $\checkmark$ & $\checkmark$ \\
\hline
Chicken and stuffing & $( C )$ & & $\checkmark$ & & $\checkmark$ & \\
\hline
Duck and plum sauce & $( D )$ & & & $\checkmark$ & & $\checkmark$ \\
\hline
Egg and tomato & $( E )$ & $\checkmark$ & & & & \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\roman*)]
\item Draw a bipartite graph to represent this information. Put the fillings ( $A , B , C , D$ and $E$ ) on the left-hand side and the members of the family ( $F , G , H , J$ and $K$ ) on the right-hand side.
Fiona takes the avocado roll; Gwen takes the beef roll; Helen takes the duck roll and Jack takes the chicken roll.
\item Draw a second bipartite graph to show this incomplete matching.
\item Construct the shortest possible alternating path from $E$ to $K$ and hence find a complete matching. State which roll each family member has with this complete matching.
\item Find a different complete matching.
\end{enumerate}\item Mr King decides that the family should eat more fruit. Each family member gives a score out of 10 to five fruits. These scores are subtracted from 10 to give the values below.
\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Family member}
\begin{tabular}{ | l c | c | c | c | c | c | }
\hline
& & $F$ & $G$ & $H$ & $J$ & $K$ \\
\hline
Lemon & $L$ & 8 & 8 & 8 & 8 & 1 \\
\hline
Mandarin & $M$ & 4 & 8 & 6 & 4 & 2 \\
\hline
Nectarine & $N$ & 9 & 9 & 9 & 7 & 1 \\
\hline
Orange & $O$ & 4 & 6 & 5 & 4 & 3 \\
\hline
Peach & $P$ & 6 & 9 & 7 & 5 & 0 \\
\hline
\end{tabular}
\end{center}
\end{table}
The smaller entries in each column correspond to fruits that the family members liked most.\\
Mr King buys one of each of these five fruits. Each family member is to be given a fruit.\\
Apply the Hungarian algorithm, reducing rows first, to find a minimum cost matching. You must show your working clearly. Which family member should be given which fruit?
\end{enumerate}
\hfill \mbox{\textit{OCR D2 2009 Q1 [13]}}