| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2014 |
| Session | June |
| Marks | 6 |
| 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 alternating path algorithm for maximum matching in bipartite graphs. Students are guided step-by-step through the process with clear instructions, and the initial incomplete matching is provided. While it requires understanding of the algorithm, it's a routine procedural question with no novel problem-solving required, making it slightly easier than average. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02c Graph terminology: walk, trail, path, cycle, route |
| Adele | (A) | \includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_47_43_1210_750} | (B) | Battleship |
| Ezra | (E) | 『 | (F) | Flat iron |
| Jonah | (J) | \includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_45_377_1389_759} | (O) | Old boot |
| Lily | (L) | \includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_45_377_1486_759} | (R) | Racing car |
| Molly | (M) | \includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_44_377_1583_759} | (S) | Scottie dog |
| Noah | (N) | \includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_40_29_1684_764} | (T) | Top hat |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Alternating path: \(A - B - J - O\) ... wait, need to check edges. Path: \(A \to B\) (unmatched), so \(A-B\) is the shortest alternating path finishing at \(B\) | B1 | Must start at A, end at B or T, alternating between unmatched and matched edges |
| Updated matching: \(A-B\), \(E-F\), \(J-O\), \(L-R\), \(M-S\), excluding Noah | B1 | Matching stated correctly, excluding Noah and one token (T) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Alternating path starting at \(N\): \(N - T\) (unmatched arc, since T is still free) | B1 | Shortest alternating path \(N \to T\) |
| Complete matching: \(A-B\), \(E-F\), \(J-O\), \(L-R\), \(M-S\), \(N-T\) | B1 | All six students matched |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Starting at \(B\): \(B\) can be matched to \(A\) or \(J\) | M1 | Systematic consideration of choices from \(B\) |
| If \(B-A\): then remaining students \(E,J,L,M,N\) must match \(F,O,R,S,T\) — leading to one complete matching | A1 | |
| If \(B-J\): then \(J\) takes \(B\), freeing up path to give exactly one other complete matching | ||
| Conclusion: exactly two complete matchings | A1 | Both matchings listed/demonstrated, conclusion stated |
# Question 1:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Alternating path: $A - B - J - O$ ... wait, need to check edges. Path: $A \to B$ (unmatched), so $A-B$ is the shortest alternating path finishing at $B$ | B1 | Must start at A, end at B or T, alternating between unmatched and matched edges |
| Updated matching: $A-B$, $E-F$, $J-O$, $L-R$, $M-S$, excluding Noah | B1 | Matching stated correctly, excluding Noah and one token (T) |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Alternating path starting at $N$: $N - T$ (unmatched arc, since T is still free) | B1 | Shortest alternating path $N \to T$ |
| Complete matching: $A-B$, $E-F$, $J-O$, $L-R$, $M-S$, $N-T$ | B1 | All six students matched |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Starting at $B$: $B$ can be matched to $A$ or $J$ | M1 | Systematic consideration of choices from $B$ |
| If $B-A$: then remaining students $E,J,L,M,N$ must match $F,O,R,S,T$ — leading to one complete matching | A1 | |
| If $B-J$: then $J$ takes $B$, freeing up path to give exactly one other complete matching | | |
| Conclusion: exactly two complete matchings | A1 | Both matchings listed/demonstrated, conclusion stated |
---1 Six students are choosing their tokens for a board game. The bipartite graph in Fig. 1 shows which token each student is prepared to have.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_522_976_351_525}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{center}
\end{figure}
Initially Ezra takes the flat iron, Jonah the old boot, Lily the racing car and Molly the scottie dog. This leaves Adele and Noah with tokens that they do not want. This incomplete matching is shown in Fig. 2 below.
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Adele & (A) & \includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_47_43_1210_750}
& (B) & Battleship \\
\hline
Ezra & (E) & 『 & (F) & Flat iron \\
\hline
Jonah & (J) & \includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_45_377_1389_759}
& (O) & Old boot \\
\hline
Lily & (L) & \includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_45_377_1486_759}
& (R) & Racing car \\
\hline
Molly & (M) & \includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_44_377_1583_759}
& (S) & Scottie dog \\
\hline
Noah & (N) & \includegraphics[max width=\textwidth, alt={}]{cfa46190-9a1e-4552-a551-c28d5c4286ad-2_40_29_1684_764}
& (T) & Top hat \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{center}
\end{table}
\begin{enumerate}[label=(\roman*)]
\item Write down the shortest possible alternating path that starts at A and finishes at either B or T . Hence write down a matching that only excludes Noah and one of the tokens.
\item Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at N and finishes at whichever of B and T has still not been taken. Hence write down a complete matching between the students and the tokens.
\item By starting at B on Fig. 1, show that there are exactly two complete matchings between the students and the tokens.
\end{enumerate}
\hfill \mbox{\textit{OCR D2 2014 Q1 [6]}}