| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2008 |
| Session | January |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Draw bipartite graph from description |
| Difficulty | Easy -1.8 Part (i) is a straightforward translation of written constraints into a bipartite graph with no problem-solving required—purely mechanical matching of requirements to room features. This is basic graph construction from a table, typical of routine D2 exercises requiring only careful reading and drawing. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02e Bipartite graphs: K_{m,n} notation7.02f Bipartite test: colouring argument |
| Room | Floor | Can be seen from road | Looks out onto garden | Has balcony |
| 1 | Ground | ✓ | ||
| 2 | Ground | ✓ | ||
| 3 | First | ✓ | ✓ | |
| 4 | First | ✓ | ✓ | |
| 5 | Second | ✓ | ✓ | |
| 6 | Second | ✓ |
| \multirow{2}{*}{} | Room | |||||
| 1 | 2 | 3 | 4 | 5 | 6 | |
| Arnie (A) | 3 | 6 | 4 | 1 | 5 | 2 |
| Brigitte ( \(B\) ) | 5 | 3 | 2 | 4 | 1 | 6 |
| Charles (C) | 2 | 1 | 3 | 4 | 5 | 6 |
| Diana (D) | 5 | 4 | 1 | 3 | 2 | 6 |
| Edward ( \(E\) ) | 5 | 6 | 4 | 3 | 2 | 1 |
| Faye (F) | 5 | 6 | 4 | 1 | 3 | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Reduce rows (subtract row minimum from each row) | M1 | Or reduce columns first |
| Correct reduced row matrix shown | A1 | cao with rows reduced first; follow through their reasonable reduced cost matrix if possible |
| Then reduce columns (subtract column minimum) | M1 | |
| Correct fully reduced matrix | ||
| Cross out 0's using 5 lines | M1 | Any valid choice of lines (max for theirs) |
| Augment by 1 to get a complete allocation | M1 | Augmenting appropriately |
| Augmentation completely correct | A1 | Augmentation completely correct (ft) |
| \(A=1,\ B=5,\ C=2,\ D=3,\ E=6,\ F=4\) | B1 | This allocation listed in any form, cao |
| Arnie | B1 | Arnie named (not just \(A\)), cao |
# Question 1 (iv):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Reduce rows (subtract row minimum from each row) | M1 | Or reduce columns first |
| Correct reduced row matrix shown | A1 | cao with rows reduced first; follow through their reasonable reduced cost matrix if possible |
| Then reduce columns (subtract column minimum) | M1 | |
| Correct fully reduced matrix | | |
| Cross out 0's using 5 lines | M1 | Any valid choice of lines (max for theirs) |
| Augment by 1 to get a complete allocation | M1 | Augmenting appropriately |
| Augmentation completely correct | A1 | Augmentation completely correct (ft) |
| $A=1,\ B=5,\ C=2,\ D=3,\ E=6,\ F=4$ | B1 | This allocation listed in any form, cao |
| Arnie | B1 | Arnie named (not just $A$), cao |
---1 Arnie (A), Brigitte (B), Charles (C), Diana (D), Edward (E) and Faye (F) are moving into a home for retired Hollywood stars. They all still expect to be treated as stars and each has particular requirements.
Arnie wants a room that can be seen from the road, but does not want a ground floor room; Brigitte wants a room that looks out onto the garden; Charles wants a ground floor room; Diana wants a room with a balcony; Edward wants a second floor room; Faye wants a room, with a balcony, that can be seen from the road.
The table below shows the features of each of the six rooms available.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Room & Floor & Can be seen from road & Looks out onto garden & Has balcony \\
\hline
1 & Ground & ✓ & & \\
\hline
2 & Ground & & ✓ & \\
\hline
3 & First & & ✓ & ✓ \\
\hline
4 & First & ✓ & & ✓ \\
\hline
5 & Second & & ✓ & ✓ \\
\hline
6 & Second & ✓ & & \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\roman*)]
\item Draw a bipartite graph to show the possible pairings between the stars ( $A , B , C , D , E$ and $F$ ) and the rooms ( $1,2,3,4,5$ and 6 ).
Originally Arnie was given room 4, Brigitte was given room 3, Charles was given room 2, Diana was given room 5, Edward was given room 6 and Faye was given room 1.
\item Identify the star that has not been given a room that satisfies their requirements. Draw a second bipartite graph to show the incomplete matching that results when this star is not given a room.
\item Construct the shortest possible alternating path, starting from the star without a room and ending at the room that was not used, and hence find a complete matching between the stars and the rooms. Write a list showing which star should be given which room.
When the stars view the rooms they decide that some are much nicer than others. Each star gives each room a value from 1 to 6 , where 1 is the room they would most like and 6 is the room they would least like. The results are shown below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
\multirow{2}{*}{} & \multicolumn{6}{|c|}{Room} \\
\hline
& 1 & 2 & 3 & 4 & 5 & 6 \\
\hline
Arnie (A) & 3 & 6 & 4 & 1 & 5 & 2 \\
\hline
Brigitte ( $B$ ) & 5 & 3 & 2 & 4 & 1 & 6 \\
\hline
Charles (C) & 2 & 1 & 3 & 4 & 5 & 6 \\
\hline
Diana (D) & 5 & 4 & 1 & 3 & 2 & 6 \\
\hline
Edward ( $E$ ) & 5 & 6 & 4 & 3 & 2 & 1 \\
\hline
Faye (F) & 5 & 6 & 4 & 1 & 3 & 2 \\
\hline
\end{tabular}
\end{center}
\item Apply the Hungarian algorithm to this table, reducing rows first, to find a minimum 'cost' allocation between the stars and the rooms. Write a list showing which star should be given which room according to this allocation. Write down the name of any star whose original requirements are not satisfied.
\end{enumerate}
\hfill \mbox{\textit{OCR D2 2008 Q1 [14]}}