| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Effect of adding/removing edge |
| Difficulty | Standard +0.3 This is a standard route inspection (Chinese Postman) problem with straightforward application of the algorithm. Parts (a)-(c) are textbook exercises requiring identification of odd vertices and pairing. Parts (d)-(e) involve removing an edge, but the analysis remains routine—checking if the graph becomes Eulerian or requires minimal pairing adjustments. No novel insight required, just methodical application of a well-defined algorithm. |
| Spec | 7.02b Graph terminology: tree, simple, connected, simply connected7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| The valency of a vertex is the number of edges incident to it | B2, 1, 0 (2) | Give B1 if refers to arc/edge but not node/vertex; B2 for clear correct statement |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(DE + HI = 131 + 75 = 206\) | M1, 1A1 | Three pairings of four odd nodes |
| \(DH + EI = 146 + 137 = 283\) | 2A1 | Two rows correct including pairing and total |
| \(DI + EH = 143 + 62 = 205^*\) | 3A1 | Three rows correct including pairing and total |
| Arcs EH, DF and FI will be traversed twice | 4A1ft (5) | Smallest repeated arcs; accept DFI |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Route length \(= 1436 + 205 = 1641\) m | B1ft (1) | Must have choice of at least two pairs from (b); \(1436 +\) their least |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Since HI is removed, only D and E are odd; only DE needs to be repeated; Route length \(= 1436 - 75 + 131 = 1492\) m | M1, A1 (2) | Aim to include DE(131) ft from (b) and remove HI(75); CAO 1492; NMS gets M0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Route starts and finishes at D and E, e.g. DCFDAEBGEFKIFHJGHE (18 vertices) | M1, A1 (2) | D and E identified as start/finish; CAO route with 18 vertices; each of A–K present; 3E's, 3F's, 2D's, 2G's, 2H's |
## Question 4:
### Part (a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| The valency of a vertex is the number of edges incident to it | B2, 1, 0 **(2)** | Give B1 if refers to arc/edge but not node/vertex; B2 for clear correct statement |
### Part (b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| $DE + HI = 131 + 75 = 206$ | M1, 1A1 | Three pairings of four odd nodes |
| $DH + EI = 146 + 137 = 283$ | 2A1 | Two rows correct including pairing and total |
| $DI + EH = 143 + 62 = 205^*$ | 3A1 | Three rows correct including pairing and total |
| Arcs EH, DF and FI will be traversed twice | 4A1ft **(5)** | Smallest repeated arcs; accept DFI |
### Part (c):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Route length $= 1436 + 205 = 1641$ m | B1ft **(1)** | Must have choice of at least two pairs from (b); $1436 +$ their least |
### Part (d):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Since HI is removed, only D and E are odd; only DE needs to be repeated; Route length $= 1436 - 75 + 131 = 1492$ m | M1, A1 **(2)** | Aim to include DE(131) ft from (b) and remove HI(75); CAO 1492; NMS gets M0 |
### Part (e):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Route starts and finishes at D and E, e.g. DCFDAEBGEFKIFHJGHE (18 vertices) | M1, A1 **(2)** | D and E identified as start/finish; CAO route with 18 vertices; each of A–K present; 3E's, 3F's, 2D's, 2G's, 2H's |
---4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-5_661_1525_292_269}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
\section*{[The total weight of the network is 1436 m ]}
\begin{enumerate}[label=(\alph*)]
\item Explain the term valency.
Figure 3 models a system of underground pipes. The number on each arc represents the length, in metres, of that pipe.
Pressure readings indicate that there is a leak in the system and an electronic device is to be used to inspect the system to locate the leak. The device will start and finish at A and travel along each pipe at least once. The length of this inspection route needs to be minimised.
\item Use the route inspection algorithm to find the pipes that will need to be traversed twice. You should make your method and working clear.
\item Find the length of the inspection route.
Pipe HI is now found to be blocked; it is sealed and will not be replaced. An inspection route is now required that excludes pipe HI . The length of the inspection route must be minimised.
\item Find the length of the minimum inspection route excluding HI. Justify your answer.
\item Given that the device may now start at any vertex and finish at any vertex, find a minimum inspection route, excluding HI.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2012 Q4 [12]}}