| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2016 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Standard +0.3 This is a standard application of the maximum matching algorithm (alternating paths) from Decision Mathematics 2. While it requires careful tracking through multiple steps, the algorithm is mechanical and well-practiced. Part (iii) adds slight conceptual depth by asking about necessary arcs, but this is still routine for D2 students who have learned matching theory. |
| 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 |
| Sailing ships | (1) | January/February | ||
| Seascape | (2) | • ◯ | (MA) | March/April |
| Snow scene | (3) | \includegraphics[max width=\textwidth, alt={}]{490ff276-6639-40a1-bffb-dc6967f3ab21-2_54_381_1451_716} | (MJ) | May/June |
| Street scene | \includegraphics[max width=\textwidth, alt={}]{490ff276-6639-40a1-bffb-dc6967f3ab21-2_59_38_1536_712} | (JA) | July/August | |
| Sunset | (5) | (SO) | September/October | |
| Swans | (6) | (ND) | November/December |
The content provided does not contain a valid mark scheme. It appears to be a blank page footer from an OCR examination paper with copyright information only.
No marking points, annotations (M1, A1, B1, etc), or assessment criteria are present to clean up or convert.1 Josh is making a calendar. He has chosen six pictures, each of which will represent two months in the calendar. He needs to choose which picture to use for each two-month period. The bipartite graph in Fig. 1 shows for which months each picture is suitable.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{490ff276-6639-40a1-bffb-dc6967f3ab21-2_497_1246_488_415}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{center}
\end{figure}
Initially Josh chooses the sailing ships for March/April, the sunset for July/August, the snow scene for November/December and the swans for May/June. This incomplete matching is shown in Fig. 2 below.
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Sailing ships & (1) & & & January/February \\
\hline
Seascape & (2) & • ◯ & (MA) & March/April \\
\hline
Snow scene & (3) & \includegraphics[max width=\textwidth, alt={}]{490ff276-6639-40a1-bffb-dc6967f3ab21-2_54_381_1451_716}
& (MJ) & May/June \\
\hline
Street scene & & \includegraphics[max width=\textwidth, alt={}]{490ff276-6639-40a1-bffb-dc6967f3ab21-2_59_38_1536_712}
& (JA) & July/August \\
\hline
Sunset & (5) & & (SO) & September/October \\
\hline
Swans & (6) & & (ND) & November/December \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{center}
\end{table}
(i) Write down the shortest possible alternating path that starts at (JF) and finishes at either (2) or (4). Hence write down a matching that only excludes (SO) and one of the pictures.\\
(ii) Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at (SO) and finishes at whichever of (2) and (4) has still not been matched. Hence write down a complete matching between the pictures and the months.\\
(iii) Explain why three of the arcs in Fig. 1 must appear in the graph of any complete matching. Hence find a second complete matching.
\hfill \mbox{\textit{OCR D2 2016 Q1 [7]}}