| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Effect of adding/removing edge |
| Difficulty | Moderate -0.3 This is a standard route inspection (Chinese Postman) algorithm question with straightforward application. Part (a) requires identifying odd-degree vertices and pairing them optimally—a routine D1 procedure. Part (b) asks for the route itself. Part (c) involves analyzing how adding an edge affects the solution, requiring some insight but still following the algorithm mechanically. While it's a 10-mark question requiring multiple steps, it's a textbook application of a well-defined algorithm with no novel problem-solving required, making it slightly easier than average. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| BC + EG = 10.4 + 10.1 = 20.5 smallest<br>BE + CG = 8.3 + 16.1 = 24.4<br>BG + CE = 14.9 + 11.9 = 26.8<br><br>So repeat tunnels BA, AC and EG | M1 A1 A1 A1 | M1: Three pairings of their four odd nodes<br>1A1: one row correct<br>2A1: two rows correct<br>3A1: all correct<br>4A1: correct arcs identified |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Any route e.g. ACFGDCABDEGEBA<br>Length: 73.3 + their 20.5 = 93.8km | B1 M1 A1 | 1B1: Any correct route (14 nodes)<br>1M1: 73.3 + ft their least, from a choice of at least two.<br>1A1: cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| The new tunnel would make C and G even.<br>So only BE would need to be repeated.<br>Extra distance would be 10 + 8.3 = 18.3 < 20.5 [91.6 < 93.8]<br>So it would decrease the total distance. | B1 DB1 | 1B1: A correct explanation, referring to BE and relevant numbers (8.3, 12.2, 2.2, 18.3,81.3, 91.6) maybe confused, incomplete or lack conclusion –bod gets B1<br>2B1D: A correct, clear explanation all there + conclusion (ft on their numbers.) |
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| BC + EG = 10.4 + 10.1 = 20.5 smallest<br>BE + CG = 8.3 + 16.1 = 24.4<br>BG + CE = 14.9 + 11.9 = 26.8<br><br>So repeat tunnels BA, AC and EG | M1 A1 A1 A1 | M1: Three pairings of their four odd nodes<br>1A1: one row correct<br>2A1: two rows correct<br>3A1: all correct<br>4A1: correct arcs identified |
**Total: 5 marks**
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Any route e.g. ACFGDCABDEGEBA<br>Length: 73.3 + their 20.5 = 93.8km | B1 M1 A1 | 1B1: Any correct route (14 nodes)<br>1M1: 73.3 + ft their least, from a choice of at least two.<br>1A1: cao |
**Total: 3 marks**
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| The new tunnel would make C and G even.<br>So only BE would need to be repeated.<br>Extra distance would be 10 + 8.3 = 18.3 < 20.5 [91.6 < 93.8]<br>So it would decrease the total distance. | B1 DB1 | 1B1: A correct explanation, referring to BE and relevant numbers (8.3, 12.2, 2.2, 18.3,81.3, 91.6) maybe confused, incomplete or lack conclusion –bod gets B1<br>2B1D: A correct, clear explanation all there + conclusion (ft on their numbers.) |
**Total: 2 marks**
**Grand Total for Q4: 10 marks**
---\includegraphics{figure_2}
[The total weight of the network is 73.3 km]
Figure 2 models a network of tunnels that have to be inspected. The number on each arc represents the length, in km, of that tunnel.
Malcolm needs to travel through each tunnel at least once and wishes to minimise the length of his inspection route.
He must start and finish at A.
\begin{enumerate}[label=(\alph*)]
\item Use the route inspection algorithm to find the tunnels that will need to be traversed twice. You should make your method and working clear.
[5]
\item Find a route of minimum length, starting and finishing at A.
State the length of your route.
[3]
A new tunnel, CG, is under construction. It will be 10 km long.
Malcolm will have to include the new tunnel in his inspection route.
\item What effect will the new tunnel have on the total length of his route?
Justify your answer.
[2]
\end{enumerate}
(Total 10 marks)
\hfill \mbox{\textit{Edexcel D1 2010 Q4 [10]}}