| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Chinese Postman with flexible endpoints |
| Difficulty | Standard +0.3 This is a standard Chinese Postman problem with a straightforward extension to flexible endpoints. Part (a) is routine application of the algorithm (identifying odd vertices, finding pairings, repeating arcs). Parts (b-d) require understanding that flexible endpoints allow starting/ending at odd vertices to reduce repeated arcs, but the logic is direct once the concept is grasped. The network is small enough to work with easily, and all steps follow standard D1 procedures without requiring novel insight. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(B(AD)E + F(J)H = 45 + 30 = 75^*\) | M1 | Three distinct pairings of the correct four odd nodes |
| \(B(CK)F + E(DG)H = 50 + 35 = 85\) | A1 | Any two rows correct including pairings and totals |
| \(B(CKJ)H + E(DGHJ)F = 60 + 65 = 125\) | A1 | All three rows correct including pairings and totals |
| Arcs BA, AD, DE, FJ and JH will be traversed twice | A1 | Accept BADE, FJH |
| Route length \(= 384 + 75 = 459\) metres | A1ft | Correct answer of 459, or \(384 +\) their smallest repeat from at least two totals |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Starting at an odd vertex means finishing at another odd vertex, removing need to repeat the route between them; only one repeated route needed rather than two | B2, 1, 0 | Full argument requires both: (i) finishing at an odd vertex and (ii) only repeating one route/pairing rather than two |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Only need to repeat one pair of odd vertices not including F: \(BE=45\), \(EH=35\), \(BH=60\) | M1 | Identifies need to repeat one route of \(BE(45)\), \(EH(35)\), \(BH(60)\) not including F |
| EH is smallest; guard should finish at B | A1 | Must state EH is the least not including F; must identify B as finishing vertex |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Route e.g. FJKFCKLJHGHEDGDECBDAB | B1 | Start at F, finish at B, 21 vertices; node appearances: A(1), B(2), C(2), D(3), E(2), F(2), G(2), H(2), J(2), K(2), L(1) |
| Length of route \(= 419\) metres | B1ft | \(384 +\) their EH (least route not including F); dependent on M mark in (a) |
# Question 6:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $B(AD)E + F(J)H = 45 + 30 = 75^*$ | M1 | Three distinct pairings of the correct four odd nodes |
| $B(CK)F + E(DG)H = 50 + 35 = 85$ | A1 | Any two rows correct including pairings and totals |
| $B(CKJ)H + E(DGHJ)F = 60 + 65 = 125$ | A1 | All three rows correct including pairings and totals |
| Arcs BA, AD, DE, FJ and JH will be traversed twice | A1 | Accept BADE, FJH |
| Route length $= 384 + 75 = 459$ metres | A1ft | Correct answer of 459, or $384 +$ their smallest repeat from at least two totals |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Starting at an odd vertex means finishing at another odd vertex, removing need to repeat the route between them; only one repeated route needed rather than two | B2, 1, 0 | Full argument requires both: (i) finishing at an odd vertex and (ii) only repeating one route/pairing rather than two |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Only need to repeat one pair of odd vertices not including F: $BE=45$, $EH=35$, $BH=60$ | M1 | Identifies need to repeat one route of $BE(45)$, $EH(35)$, $BH(60)$ not including F |
| EH is smallest; guard should finish at B | A1 | Must state EH **is the least not including F**; must identify B as finishing vertex |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Route e.g. FJKFCKLJHGHEDGDECBDAB | B1 | Start at F, finish at B, 21 vertices; node appearances: A(1), B(2), C(2), D(3), E(2), F(2), G(2), H(2), J(2), K(2), L(1) |
| Length of route $= 419$ metres | B1ft | $384 +$ their EH (least route not including F); dependent on M mark in (a) |
---6.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-07_684_1420_233_312}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{center}
\end{figure}
[The total weight of the network is 384]\\
Figure 5 models a network of corridors in an office complex that need to be inspected by a security guard. The number on each arc is the length, in metres, of the corresponding section of corridor.
Each corridor must be traversed at least once and the length of the inspection route must be minimised. The guard must start and finish at vertex A.
\begin{enumerate}[label=(\alph*)]
\item Use the route inspection algorithm to find the length of the shortest inspection route. State the arcs that should be repeated. You should make your method and working clear.\\
(5)
It is now possible for the guard to start at one vertex and finish at a different vertex. An inspection route that traverses each corridor at least once is still required.
\item Explain why the inspection route should start at a vertex with odd degree.\\
(2)
The guard decides to start the inspection route at F and the length of the inspection route must still be minimised.
\item Determine where the guard should finish. You must give reasons for your answer.
\item State a possible route and its length.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2016 Q6 [11]}}