OCR D1 2013 January — Question 3 14 marks

Exam BoardOCR
ModuleD1 (Decision Mathematics 1)
Year2013
SessionJanuary
Marks14
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicShortest Path
TypeDijkstra combined with Chinese Postman
DifficultyStandard +0.3 This is a standard D1 question combining two routine algorithms (Dijkstra and Chinese Postman). Part (i) is straightforward algorithm application, while parts (ii) and (iii) require identifying odd vertices and finding pairings—all standard textbook procedures with no novel insight required. Slightly easier than average due to the algorithmic nature.
Spec7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes
3 The total weight of the arcs in the network below is 230 . \includegraphics[max width=\textwidth, alt={}, center]{012e87d3-d157-485c-a8bc-2c59c0862f87-3_545_1394_310_331}
  1. Apply Dijkstra's algorithm to the copy of the network in the answer book to find the least weight path from \(A\) to \(H\). Give the path and its weight. In the remainder of this question, any least weight paths required may be found without using a formal algorithm.
  2. The arc \(A D\) is removed. Apply the route inspection algorithm, showing your working, to find the weight of the least weight closed route that uses every arc (except \(A D\) ) at least once.
  3. Suppose, instead, that the arc \(A D\) is available, but \(\operatorname { arcs } A C\) and \(C D\) are both removed. Apply the route inspection algorithm, showing your working, to find the weight of the least weight closed route that uses every arc (except \(A C\) and \(C D\) ) at least once.
3 The total weight of the arcs in the network below is 230 .\\
\includegraphics[max width=\textwidth, alt={}, center]{012e87d3-d157-485c-a8bc-2c59c0862f87-3_545_1394_310_331}\\
(i) Apply Dijkstra's algorithm to the copy of the network in the answer book to find the least weight path from $A$ to $H$. Give the path and its weight.

In the remainder of this question, any least weight paths required may be found without using a formal algorithm.\\
(ii) The arc $A D$ is removed. Apply the route inspection algorithm, showing your working, to find the weight of the least weight closed route that uses every arc (except $A D$ ) at least once.\\
(iii) Suppose, instead, that the arc $A D$ is available, but $\operatorname { arcs } A C$ and $C D$ are both removed. Apply the route inspection algorithm, showing your working, to find the weight of the least weight closed route that uses every arc (except $A C$ and $C D$ ) at least once.

\hfill \mbox{\textit{OCR D1 2013 Q3 [14]}}
This paper (5 questions)
View full paper
Q1 9 Q2 10 Q3 14 Q4 17 Q5 22