OCR MEI D1 — Question 2

Exam BoardOCR MEI
ModuleD1 (Decision Mathematics 1)
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicShortest Path
TypeDijkstra combined with MST
DifficultyModerate -0.3 This is a straightforward two-part question testing standard algorithmic procedures from D1. Part (i) is a routine application of Dijkstra's algorithm with clear start/end vertices, and part (ii) requires completing a partially-done Kruskal's algorithm. Both are textbook exercises requiring careful execution but no problem-solving insight or novel thinking—slightly easier than average due to the algorithmic nature and partial scaffolding in part (ii).
Spec7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms
2 Answer this question on the insert provided.
  1. Use Dijkstra's algorithm to find the least weight route from A to G in the network shown in Fig. 2.1. Show the order in which you label vertices, give the route and its weight. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-003_458_586_525_758} \captionsetup{labelformat=empty} \caption{Fig. 2.1}
    \end{figure}
  2. Fig. 2.2 shows a partially completed application of Kruskal's algorithm to find a minimum spanning tree for the network. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-003_417_524_1309_786} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
    \end{figure} Complete the algorithm and give the total weight of your minimum spanning tree.
(i) Draw John's graph. [2]
- B1: Correct representation of bus routes
- B1: Correct representation of train lines
(ii) Is John's graph simple? Justify your answer. [2]
- M1: Identification of multiple arcs between same pair of nodes
- A1: Correct conclusion that the graph is not simple
(iii) Draw Jamil's graph. [2]
- B1: Correct nodes including C(bus) and C(train)
- B1: Correct arcs representing all connections
(iv) Is Jamil's graph a tree? Justify your answer. [2]
- M1: Check for connectivity and counting arcs
- A1: Correct conclusion with justification (5 nodes, 5 arcs; contains a cycle)
**(i)** Draw John's graph. [2]
- B1: Correct representation of bus routes
- B1: Correct representation of train lines

**(ii)** Is John's graph simple? Justify your answer. [2]
- M1: Identification of multiple arcs between same pair of nodes
- A1: Correct conclusion that the graph is not simple

**(iii)** Draw Jamil's graph. [2]
- B1: Correct nodes including C(bus) and C(train)
- B1: Correct arcs representing all connections

**(iv)** Is Jamil's graph a tree? Justify your answer. [2]
- M1: Check for connectivity and counting arcs
- A1: Correct conclusion with justification (5 nodes, 5 arcs; contains a cycle)
2 Answer this question on the insert provided.
(i) Use Dijkstra's algorithm to find the least weight route from A to G in the network shown in Fig. 2.1. Show the order in which you label vertices, give the route and its weight.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-003_458_586_525_758}
\captionsetup{labelformat=empty}
\caption{Fig. 2.1}
\end{center}
\end{figure}

(ii) Fig. 2.2 shows a partially completed application of Kruskal's algorithm to find a minimum spanning tree for the network.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-003_417_524_1309_786}
\captionsetup{labelformat=empty}
\caption{Fig. 2.2}
\end{center}
\end{figure}

Complete the algorithm and give the total weight of your minimum spanning tree.

\hfill \mbox{\textit{OCR MEI D1  Q2}}
This paper (3 questions)
View full paper
Q1 14 Q2 Q3 12