Write explicit optimal route

State a complete optimal route as a sequence of vertices, not just its length, showing which edges are repeated.

3 questions · Standard +0.3

7.04c Travelling salesman upper bound: nearest neighbour method
Sort by: Default | Easiest first | Hardest first
Edexcel D1 2001 June Q3
7 marks Standard +0.3
3. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{6d306129-6e1f-424a-b21c-1bf6434ee082-4_678_1151_425_399}
\end{figure} Figure 2 shows a new small business park. The vertices \(A , B , C , D , E , F\) and \(G\) represent the various buildings and the arcs represent footpaths. The number on an arc gives the length, in metres, of the path. The management wishes to inspect each path to make sure it is fit for use. Starting and finishing at \(A\), solve the Route Inspection (Chinese Postman) problem for the network shown in Fig. 2 and hence determine the minimum distance thet needs to be walked in carrying out this inspection. Make your method and working clear and give a possible route of minimum length.
Edexcel D1 2013 June Q5
10 marks Standard +0.3
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-06_712_1520_246_267} \captionsetup{labelformat=empty} \caption{Figure 4
[0pt] [The total weight of the network is 181 miles]}
\end{figure} Figure 4 represents a network of power cables that have to be inspected. The number on each arc represents the length, in km , of that cable. A route of minimum length that traverses each cable at least once and starts and finishes at A needs to be found.
  1. Use the route inspection algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
  2. Write down a possible shortest inspection route, giving its length. It is now decided to start and finish the inspection route at two distinct vertices. The route must still traverse each cable at least once.
  3. Determine possible starting and finishing points so that the length of the route is minimised. You must give reasons for your answer.
Edexcel D1 2004 January Q4
9 marks Standard +0.3
\includegraphics{figure_2} An engineer needs to check the state of a number of roads to see whether they need resurfacing. The roads that need to be checked are represented by the arcs in Fig. 2. The number on each arc represents the length of that road in km. To check all the roads, he needs to travel along each road at least once. He wishes to minimise the total distance travelled. The engineer's office is at \(G\), so he starts and ends his journey at \(G\).
  1. Use an appropriate algorithm to find a route for the engineer to follow. State your route and its length. [6]
The engineer lives at \(D\). He believes he can reduce the distance travelled by starting from home and inspecting all the roads on the way to his office at \(G\).
  1. State whether the engineer is correct in his belief. If so, calculate how much shorter his new route is. If not, explain why not. [3]