7.04e Route inspection: Chinese postman, pairing odd nodes

3. \begin{figure}[h] \end{figure} [The total weight of the network is \(139 + x + y\) ]

1. Explain what is meant by the term "tree". Figure 3 represents a network of walkways in a warehouse.
   The arcs represent the walkways and the nodes represent junctions between them.
   The number on each arc represents the length, in metres, of the corresponding walkway.
   The values \(x\) and \(y\) are unknown, however it is known that \(x\) and \(y\) are integers and that $$9 < x < y < 14$$
2. 1. Use Dijkstra's algorithm to find the shortest route from A to M.
   2. State an expression for the length of the shortest route from A to M . The warehouse manager wants to check that all of the walkways are in good condition.
      Their inspection route starts at B and finishes at C .
      The inspection route must traverse each walkway at least once and be as short as possible.
3. State the arcs that are traversed twice.
4. State the number of times that H appears in the inspection route. The warehouse manager finds that the total length of the inspection route is 172 metres.
5. Determine the value of \(x\) and the value of \(y\)

1. \begin{figure}[h] \end{figure} [The total weight of the network is 189]
Figure 1 represents a network of pipes in a building. The number on each arc is the length, in metres, of the corresponding pipe.

1. Use Dijkstra's algorithm to find the shortest path from A to F . State the path and its length. On a particular day, Gabriel needs to check each pipe. A route of minimum length, which traverses each pipe at least once and which starts and finishes at A, needs to be found.
2. Use an appropriate algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
3. State the minimum length of Gabriel's route. A new pipe, BG, is added to the network. A route of minimum length that traverses each pipe, including BG, needs to be found. The route must start and finish at A. Gabriel works out that the addition of the new pipe increases the length of the route by twice the length of BG .
4. Calculate the length of BG. You must show your working.

2. \begin{figure}[h] \end{figure} Figure 1 represents a network of corridors in a building. The number on each arc represents the length, in metres, of the corresponding corridor.

1. Use Dijkstra's algorithm to find the shortest path from A to D, stating the path and its length. On a particular day, Naasir needs to check the paintwork along each corridor. Naasir must find a route of minimum length. It must traverse each corridor at least once, starting at B and finishing at G .
2. Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
3. Find the length of Naasir's route. On a different day, all the corridors that start or finish at B are closed for redecorating. Naasir needs to check all the remaining corridors and may now start at any vertex and finish at any vertex. A route is required that excludes all those corridors that start or finish at B .
4. 1. Determine the possible starting and finishing points so that the length of Naasir's route is minimised. You must give reasons for your answer.
   2. Find the length of Naasir's new route.

6. \begin{figure}[h] \end{figure} [The total weight of the network is \(320 + x + y\) ]

1. State, with justification, whether the graph in Figure 4 is Eulerian, semi-Eulerian or neither. The weights on the arcs in Figure 4 represent distances. The weight on arc EF is \(x\) where \(12 < x < 26\) and the weight on arc DG is \(y\) where \(0 < y < 10\) An inspection route of minimum length that traverses each arc at least once is found.
   The inspection route starts and finishes at A and has a length of 409
   It is also given that the length of the shortest route from F to G via A is 140
2. Using appropriate algorithms, find the value of \(x\) and the value of \(y\).

2. \begin{figure}[h] \end{figure} [The total weight of the network is 299] Figure 1 represents a network of cycle tracks between 10 landmarks, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in kilometres, of the corresponding track. One day, Blanche wishes to cycle from A to K. She wishes to minimise the distance she travels.

1. 1. Use Dijkstra's algorithm to find the shortest path from A to K .
   2. State the length of the shortest path from A to K .
      (6) The cycle tracks between the landmarks now need to be inspected. Blanche must travel along each track at least once. She wishes to minimise the length of her inspection route. Blanche will start her inspection route at D and finish at E .
2. 1. State the edges that will need to be traversed twice.
   2. Find the length of Blanche's route. It is now decided to start the inspection route at A and finish at K . Blanche must minimise the length of her route and travel along each track at least once.
3. By considering the pairings of all relevant nodes, find the length of Blanche's new route. You must make your method and working clear.

5. \begin{figure}[h] \end{figure} [The total weight of the network is 423]
Direct roads between nine towns, A, B, C, D, E, F, G, H and J, are represented in Figure 5. The number on each arc represents the length, in miles, of the corresponding road. The table below shows the shortest distances, in miles, between the nine towns. \begin{table}[h] \end{table} A route is needed that minimises the total distance required to traverse each road at least once. The route must start at F and finish at J .

1. 1. By considering the pairings of all relevant nodes, find the roads that would need to be traversed twice.
   2. State the total length of this route.
2. Starting at A, use Prim's algorithm to find the minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree. Pete needs to visit all nine towns, starting and finishing in the same town, and wishes to minimise the total distance he travels.
3. Starting at G, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Pete's route. Write down the route that gives this upper bound.
4. By deleting G and all of its arcs, find a lower bound for the length of Pete's route. Pete decides to take the route he found in (c).
5. Interpret the route in terms of the actual towns visited.

3. \begin{figure}[h] \end{figure} [The total weight of the network is 413] Figure 1 represents a network of cycle tracks between ten towns, A, B, C, D, E, F, G, H, J and K. The number on each arc represents the length, in kilometres, of the corresponding track.

1. Use Dijkstra's algorithm to find the shortest path from A to J. Abi needs to travel along every track shown in Figure 1 to check that they are all in good repair. She needs to start her inspection route at town G and finish her route at either town J or town K. Abi wishes to minimise the total distance required to traverse every track.
2. By considering all relevant pairings of vertices, determine whether Abi should finish her inspection route at town J or town K. You must
   The direct track between town B and town C and the direct track between town H and town K are now closed to all users. A second person, Tarig, is asked to check all the remaining tracks starting at G and finishing at H. Tarig wishes to minimise the total length of his inspection route.
3. Determine which route, Abi's or Tarig's, is shorter. You must make your working clear.

5 Answer part (i) of this question on the insert provided. Rhoda Raygh enjoys driving but gets extremely irritated by speed cameras.
The network represents a simplified map on which the arcs represent roads and the weights on the arcs represent the numbers of speed cameras on the roads. The sum of the weights on the arcs is 72 . \includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-05_874_1484_664_333}

1. Rhoda lives at Ayton ( \(A\) ) and works at Kayton ( \(K\) ). Use Dijkstra's algorithm on the diagram in the insert to find the route from \(A\) to \(K\) that involves the least number of speed cameras and state the number of speed cameras on this route.
2. In her job Rhoda has to drive along each of the roads represented on the network to check for overhanging trees. This requires finding a route that covers every arc at least once, starting and ending at Kayton (K). Showing all your working, find a suitable route for Rhoda that involves the least number of speed cameras and state the number of speed cameras on this route.
3. If Rhoda checks the roads for overhanging trees on her way home, she will instead need a route that covers every arc at least once, starting at Kayton and ending at Ayton. Calculate the least number of speed cameras on such a route, explaining your reasoning.

3 Answer this question on the insert provided. \includegraphics[max width=\textwidth, alt={}, center]{43fe5fd5-4b98-4c3a-90ca-a1bd5cf065fe-3_492_1006_356_568}

1. This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight.
2. Use your answer to part (i) to find the weight of a minimum spanning tree for the network with vertex \(E\), and all the arcs joined to \(E\), removed. Hence find a lower bound for the travelling salesperson problem on the original network.
3. Show that the nearest neighbour method, starting from vertex \(A\), fails on the original network.
4. Apply the nearest neighbour method, starting from vertex \(B\), to find an upper bound for the travelling salesperson problem on the original network.
5. Apply Dijkstra's algorithm to the copy of the network in the insert to find the least weight path from \(A\) to \(G\). State the weight of the path and give its route.
6. The sum of the weights of all the arcs is 300 . Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. The weights of least weight paths from vertex \(A\) should be found using your answer to part (v); the weights of other such paths should be determined by inspection.

1 Answer this question on the insert provided. \includegraphics[max width=\textwidth, alt={}, center]{e1495f6b-c09f-46a1-a6f8-02354e28887a-02_533_1353_342_395}

1. Apply Dijkstra's algorithm to the copy of this network in the insert to find the least weight path from \(A\) to \(F\). State the route of the path and give its weight.
2. Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. Write down a closed route that has this least weight. An extra arc is added, joining \(B\) to \(E\), with weight 2 .
3. Write down the new least weight path from \(A\) to \(F\). Explain why the new least weight closed route, that uses every arc at least once, has no repeated arcs.

5 Answer this question on the insert provided. The network below represents a simplified map of a building. The arcs represent corridors and the weights on the arcs represent the lengths of the corridors, in metres. The sum of the weights on the arcs is 765 metres. \includegraphics[max width=\textwidth, alt={}, center]{dbf782dd-879c-4f0f-b532-246a0db9f130-5_1271_1539_584_303}

1. Janice is the cleaning supervisor in the building. She is at the position marked as J when she is called to attend a cleaning emergency at B. On the network in the insert, use Dijkstra's algorithm, starting from vertex J and continuing until B is given a permanent label, to find the shortest path from J to B and the length of this path.
2. In her job J anice has to walk along each of the corridors represented on the network. This requires finding a route that covers every arc at least once, starting and ending at J. Showing all your working, find the shortest distance that J anice must walk to check all the corridors. The labelled vertices represent 'cleaning stations'. J anice wants to visit every cleaning station using the shortest possible route. She produces a simplified network with no repeated arcs and no arc that joins a vertex to itself.
3. On the insert, complete Janice's simplified network. Which standard network problem does Janice need to solve to find the shortest distance that she must travel?

1 The design for the lines on a playing area for a game is shown below. The letters are not part of the design. \includegraphics[max width=\textwidth, alt={}, center]{22571082-016b-409b-bfeb-e7ebf48ccac7-2_350_855_388_605} Priya paints the lines by pushing a machine. When she is pushing the machine she is about a metre behind the point being painted. She must not duplicate any line by painting it twice.

• To relocate the machine, it must be stopped and then started again to continue painting the lines.
• When the machine is being relocated it must still be pushed along the lines of the design, and not 'cut across' on a diagonal for example.
• The machine can be turned through \(90 ^ { \circ }\) without having to be stopped.
  1. What is the minimum number of times that the machine will need to be started to paint the design?

The design is horizontally and vertically symmetric. $$\mathrm { AB } = 6 \text { metres, } \mathrm { AE } = 26 \text { metres, } \mathrm { AF } = 1.5 \text { metres and } \mathrm { AS } = 9 \text { metres. }$$

(a) Find the minimum distance that Priya needs to walk to paint the design. You should show enough working to make your reasoning clear but you do not need to use an algorithmic method.
(b) Why, in practice, will the distance be greater than this?
(c) What additional information would you need to calculate a more accurate shortest distance?

5. \begin{figure}[h] \end{figure} [The total weight of the network is 625 m ]
Figure 3 models a network of paths in a park. The number on each arc represents the length, in m , of that path.
Rob needs to travel along each path to inspect the surface. He wants to minimise the length of his route.

1. Use the route inspection algorithm to find the length of his route. State the arcs that should be repeated. You should make your method and working clear.
   (6) The surface on each path is to be renewed. A machine will be hired to do this task and driven along each path.
   The machine will be delivered to point G and will start from there, but it may be collected from any point once the task is complete.
2. Given that each path must be traversed at least once, determine the finishing point so that the length of the route is minimised. Give a reason for your answer and state the length of your route.
   (3)

7 Stella is visiting Tijuana on a day trip. The diagram shows the lengths, in metres, of the roads near the bus station. \includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-007_1539_1162_495_424} Stella leaves the bus station at \(A\). She decides to walk along all of the roads at least once before returning to \(A\).

1. Explain why it is not possible to start from \(A\), travel along each road only once and return to \(A\).
2. Find the length of an optimal 'Chinese postman' route around the network, starting and finishing at \(A\).
3. At each of the 9 places \(B , C , \ldots , J\), there is a statue. Find the number of times that Stella will pass a statue if she follows her optimal route.

7 Stella is visiting Tijuana on a day trip. The diagram shows the lengths, in metres, of the roads near the bus station. \includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-06_1539_1162_495_424} Stella leaves the bus station at \(A\). She decides to walk along all of the roads at least once before returning to \(A\).

1. Explain why it is not possible to start from \(A\), travel along each road only once and return to \(A\).
2. Find the length of an optimal 'Chinese postman' route around the network, starting and finishing at \(A\).
3. At each of the 9 places \(B , C , \ldots , J\), there is a statue. Find the number of times that Stella will pass a statue if she follows her optimal route.

7 [Figure 2, printed on the insert, is provided for use in this question.]
The network shows the times, in seconds, taken by Craig to walk along walkways connecting ten hotels in Las Vegas. \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-07_1435_1267_525_351} The total of all the times in the diagram is 2280 seconds.

1. 1. Craig is staying at the Circus ( \(C\) ) and has to visit the Oriental ( \(O\) ). Use Dijkstra's algorithm on Figure 2 to find the minimum time to walk from \(C\) to \(O\).
   2. Write down the corresponding route.
2. 1. Find, by inspection, the shortest time to walk from \(A\) to \(M\).
   2. Craig intends to walk along all the walkways. Find the minimum time for Craig to walk along every walkway and return to his starting point.

4 [Figure 2, printed on the insert, is provided for use in this question.]
The network shows 11 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges. \includegraphics[max width=\textwidth, alt={}, center]{92175666-ef7a-4dca-9cdb-ebde1b40b2c9-04_1762_1056_516_484} The total of all of the times is 308 minutes.

1. 1. Use Dijkstra's algorithm on Figure 2 to find the minimum time to travel from \(A\) to \(K\).
   2. State the corresponding route.
2. Find the length of an optimum Chinese postman route around the network, starting and finishing at \(A\). (The minimum time to travel from \(D\) to \(H\) is 40 minutes.)

3 [Figure 1, printed on the insert, is provided for use in this question.]
The diagram shows roads connecting some places of interest in Berlin. The numbers represent the times taken, in minutes, to walk along the roads. \includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-4_1427_1404_502_319} The total of all walking times is 167 minutes.

1. Mia is staying at \(D\) and is to visit \(H\).
   1. Use Dijkstra's algorithm on Figure 1 to find the minimum time to walk from \(D\) to \(H\).
   2. Write down the corresponding route.
2. Each day, Leon has to deliver leaflets along all of the roads. He must start and finish at \(A\).
   1. Use your answer to part (a) to write down the shortest walking time from \(D\) to \(A\).
   2. Find the walking time of an optimum Chinese Postman route for Leon. (6 marks)

4 In Paris, there is a park where there are statues of famous people; there are many visitors each day to this park. Lighting is to be installed at nine places, \(A , B , \ldots , I\), in the park. The places have to be connected either directly or indirectly by cabling, to be laid alongside the paths, as shown in the diagram. The diagram shows the length of each path, in metres, connecting adjacent places. \includegraphics[max width=\textwidth, alt={}, center]{f99fad35-3304-4e8f-be02-1439dfdc10e1-4_1109_1120_612_459}

1. 1. Use Prim's algorithm, starting from \(A\), to find the minimum length of cabling required.
   2. State this minimum length.
   3. Draw the minimum spanning tree.
2. A security guard walks along all the paths before returning to his starting place. Find the length of an optimal Chinese postman route for the guard.

4 The diagram shows a network of roads connecting 6 villages. The number on each edge is the length, in miles, of the road. \includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-04_670_1298_466_356} Total length of the roads \(= 164\) miles

1. A police patrol car based at village \(A\) has to travel along each road at least once before returning to \(A\). Find the length of an optimal 'Chinese postman' route for the police patrol car.
2. A council worker starts from \(A\) and travels along each road at least once before finishing at \(C\). Find the length of an optimal route for the council worker.
3. A politician is to travel along all the roads at least once. He can start his journey at any village and can finish his journey at any village.
   1. Find the length of an optimal route for the politician.
   2. State the vertices from which the politician could start in order to achieve this optimal route.

4 The diagram shows the various ski-runs at a ski resort. There is a shop at \(S\). The manager of the ski resort intends to install a floodlighting system by placing a floodlight at each of the 12 points \(A , B , \ldots , L\) and at the shop at \(S\). The number on each edge represents the distance, in metres, between two points. \includegraphics[max width=\textwidth, alt={}, center]{eb305e75-0e85-4f99-8f04-27046a153532-04_842_830_577_607} Total of all edges \(= 1135\)

1. The manager wishes to use the minimum amount of cabling, which must be laid along the ski-runs, to connect the 12 points \(A , B , \ldots , L\) and the shop at \(S\).
   1. Starting from the shop, and showing your working at each stage, use Prim's algorithm to find the minimum amount of cabling needed to connect the shop and the 12 points.
   2. State the length of your minimum spanning tree.
   3. Draw your minimum spanning tree.
   4. The manager used Kruskal's algorithm to find the same minimum spanning tree. Find the seventh and the eighth edges that the manager added to his spanning tree.
2. At the end of each day a snow plough has to drive at least once along each edge shown in the diagram in preparation for the following day's skiing. The snow plough must start and finish at the point \(L\). Use the Chinese Postman algorithm to find the minimum distance that the snow plough must travel.
   (6 marks)