7.04e Route inspection: Chinese postman, pairing odd nodes

6. \begin{figure}[h] \end{figure} [The total weight of the network is 315]
Figure 3 represents a network of roads between nine parks, A, B, C, D, E, F, G, H and J. The number on each edge represents the length, in miles, of the corresponding road.

1. 1. Use Dijkstra's algorithm to find the shortest path from A to J.
   2. State the length of the shortest path from A to J . The roads between the parks need to be inspected. Robin must travel along each road at least once. Robin wishes to minimise the length of the inspection route. Robin will start the inspection route at C and finish at E .
2. By considering the pairings of all relevant nodes, find the length of Robin's route.
3. State the number of times Robin will pass through G . It is now decided to start and finish the inspection route at A. Robin must still minimise the length of the route and travel along each road at least once.
4. Calculate the difference between the lengths of the two inspection routes.
5. State the edges that need to be traversed twice in the route that starts and finishes at A , but do not need to be traversed twice in the route that starts at C and finishes at E .

5. \begin{figure}[h] \end{figure} [The total weight of the network is 166] Figure 3 models a network of cycle lanes that must be inspected. The number on each arc represents the length, in km, of the corresponding cycle lane. Lance needs to cycle along each lane at least once and wishes to minimise the length of his inspection route. He must start and finish at A.

1. Use an appropriate algorithm to find the length of the route. State the cycle lanes that Lance will need to traverse twice. You should make your method and working clear.
   (6)
2. State the number of times that vertex C appears in Lance's route.
   (1) It is now decided that the inspection route may finish at any vertex. Lance will still start at A and must cycle along each lane at least once.
3. Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of this new minimum route.
   (3)

4. \begin{figure}[h] \end{figure} [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 .

1. Use the route inspection algorithm to find the tunnels that will need to be traversed twice. You should make your method and working clear.
2. Find a route of minimum length, starting and finishing at A . State the length of your route. 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.
3. What effect will the new tunnel have on the total length of his route? Justify your answer.

3. \begin{figure}[h] \end{figure} Figure 4 models a network of roads in a housing estate. The number on each arc represents the length, in km , of the road. The total weight of the network is 11 km .
A council worker needs to travel along each road once to inspect the road surface. He will start and finish at A and wishes to minimise the length of his route.

1. Use an appropriate algorithm to find a route for the council worker. You should make your method and working clear. State your route and its length.
   (6) A postal worker needs to walk along each road twice, once on each side of the road. She must start and finish at A . The length of her route is to be minimised. You should ignore the width of the road.
2. 1. Explain how this differs from the standard route inspection problem.
      (1)
   2. Find the length of the shortest route for the postal worker.
      (2)

5. \begin{figure}[h] \end{figure} (The total weight of the network in Figure 3 is 543 km .)
Figure 3 models a network of railway tracks that have to be inspected. The number on each arc is the length, in km , of that section of railway track.
Each track must be traversed at least once and the length of the inspection route must be minimised.
The inspection route must start and finish at the same vertex.

1. Use an appropriate algorithm to find the length of the shortest inspection route. You should make your method and working clear. It is now permitted to start and finish the inspection at two distinct vertices.
2. State which two vertices should be chosen to minimise the length of the new route. Give a reason for your answer.

3. \begin{figure}[h] \end{figure} [The total weight of the network is 167]
Figure 3 represents a network of paths. The number on each arc gives the time, in minutes, to travel along that path.

1. Use Dijkstra's algorithm to find the quickest route from A to H. State your quickest route and the time taken.
   (5) Kevin must walk along each path at least once and return to his starting point.
2. Use an appropriate algorithm to find the time of Kevin's quickest possible route, starting and finishing at A. You should make your method and working clear.

5. \begin{figure}[h] \end{figure} [The total weight of the network is 31.6 km ]
Figure 5 models a network of roads. The road markings on these roads are to be renewed. The number on each arc represents the length, in km , of that road. In order to renew the road markings, each road must be traversed at least once.

1. Use the route inspection algorithm, starting and finishing at A , to find a suitable route, which should be stated. You must make your method and working clear.
2. State the roads that must be traversed twice and the length of the route.
   (3) The machine that will be used to renew the road markings can only be delivered to D . It will start at D, but it may finish at any vertex.
   Each road must still be traversed at least once.
3. Given that the route is to be minimised, determine where the machine should finish. Give reasons to justify your answer.
   (3)

2. \begin{figure}[h] \end{figure} Figure 2 models a network of canals. The number on each arc gives the length, in miles, of that canal. Brett needs to travel along each canal to check that it is in good repair. He wishes 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. A canal between B and F , of length 12 miles, is to be opened and needs to be included in Brett's inspection route.
2. Determine if the addition of this canal will increase or decrease the length of Brett's minimum route. You must make your reasoning clear.

5. \begin{figure}[h] \end{figure} [The weight of the network is 379]
Figure 5 represents the roads in a highland wildlife conservation park. The vertices represent warden stations. The number on each arc gives the length, in km , of the corresponding road. During the winter months the park is closed. It is only necessary to ensure road access to the warden stations.

1. Use Prim's algorithm, starting at A , to find a minimum connector for the network in Figure 5. You must state the order in which you include the arcs.
2. Given that it costs \(\pounds 80\) per km to keep the selected roads open in winter, calculate the minimum cost of ensuring road access to all the warden stations. At the end of winter, Ben inspects all the roads before the park re-opens. He needs to travel along each road at least once. He will start and finish at A, and wishes to minimise the length of his route.
3. Use the route inspection algorithm to find the roads that will be traversed twice. You must make your method and working clear.
4. Find the length of the shortest inspection route. If Ben starts and finishes his inspection route at different warden stations, a shorter inspection route is possible.
5. Determine the two warden stations Ben should choose as his starting and finishing points in order that his route has minimum length. Give a reason for your answer and state the length of the route.

3. \begin{figure}[h] \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.

3. \begin{figure}[h] \end{figure} Figure 3 shows a network of roads. The number on each arc represents the length, in km, of that road.

1. Use Dijkstra's algorithm to find the shortest route from A to I. State your shortest route and its length.
   (5) Sam has been asked to inspect the network and assess the condition of the roads. He must travel along each road at least once, starting and finishing at A .
2. Use an appropriate algorithm to determine the length of the shortest route Sam can travel. State a shortest route.
   (4)
   (The total weight of the network is 197 km )

4. \begin{figure}[h] \end{figure} \section*{[The total weight of the network is 1436 m ]}

1. 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.
2. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You should make your method and working clear.
3. 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.
4. Find the length of the minimum inspection route excluding HI. Justify your answer.
5. Given that the device may now start at any vertex and finish at any vertex, find a minimum inspection route, excluding HI.

5. \begin{figure}[h] \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.

5. \begin{figure}[h] \end{figure} \section*{[The total weight of the network is 344 miles]} Figure 4 represents a railway network. The number on each arc represents the length, in miles, of that section of the railway. Sophie needs to travel along each section to check that it is in good condition.
She must travel along each arc of the network at least once, and wants to find a route of minimum length. She will start and finish at A.

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. Sophie now decides to start the inspection route at E. The route must still traverse each arc at least once but may finish at any vertex.
3. Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of your route.

4. \begin{figure}[h] \end{figure} Figure 4 represents the network of sensor wires used in a medical scanner. The number on each arc represents the length, in cm, of that section of wire. After production, each scanner is tested.
A machine will be programmed to inspect each section of wire.
It will travel along each arc of the network at least once, starting and finishing at A. Its route must be of minimum length.

1. Use the route inspection algorithm to find the length of a shortest inspection route. You must make your method and working clear. The machine will inspect 15 cm of wire per second.
2. Calculate the total time taken, in seconds, to test 120 scanners. It is now possible for the machine to start at one vertex and finish at a different vertex. An inspection route of minimum length is still required.
3. Explain why the machine should be programmed to start at a vertex with odd degree. Due to constraints at the factory, only B or D can be chosen as the starting point and there will also be a 2 second pause between tests.
4. Determine the new minimum total time now taken to test 120 scanners. You must state which vertex you are starting from and make your calculations clear.
   (4)

3. \begin{figure}[h] \end{figure} Figure 1 models a network of tracks in a forest that need to be inspected by a park ranger. The number on each arc is the length, in km, of that section of the forest track. Each track must be traversed at least once and the length of the inspection route must be minimised. The inspection route taken by the ranger must start and end at vertex A.

1. Use the route inspection algorithm to find the length of a shortest inspection route. State the arcs that should be repeated. You should make your method and working clear.
2. State the number of times that vertex J would appear in the inspection route. The landowner decides to build two huts, one hut at vertex K and the other hut at a different vertex. In future, the ranger will be able to start his inspection route at one hut and finish at the other. The inspection route must still traverse each track at least once.
3. Determine where the other hut should be built so that the length of the route is minimised. You must give reasons for your answer and state a possible route and its length.

4. \begin{figure}[h] \end{figure} [The total weight of the network is 2090]

1. Explain why a network cannot have an odd number of vertices of odd valency. Figure 4 represents a network of 13 roads in a village. The number on each arc is the length, in metres, of the corresponding road. A route of minimum length that traverses each road at least once needs to be found. The route may start at any vertex and finish at any vertex.
2. Write down the vertices at which the route will start and finish.
   (1) A new road, AB , of length 130 m is built. A route of minimum length that traverses each road, including AB , needs to be found. The route must start and finish at A .
3. Use the route inspection algorithm to find the roads that will need to be traversed twice. You must make your method and working clear.
4. Calculate the length of a possible shortest inspection route. It is now decided to start and finish the inspection route at two distinct vertices. A route of minimum length that traverses each road, including AB , needs to be found. The route must start at A .
5. State the finishing point so that the length of the route is minimised. Calculate how much shorter the length of this route is compared to the length of the route in (d). You must make your method and calculations clear.
   (3)

6. \begin{figure}[h] \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.

1. 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.
2. 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.
3. Determine where the guard should finish. You must give reasons for your answer.
4. State a possible route and its length.

4. \begin{figure}[h] \end{figure} Figure 4 represents a network of roads. The number on each edge represents the length, in miles, of the corresponding road. Robyn wishes to travel from A to H. She wishes to minimise the distance she travels.

1. Use Dijkstra's algorithm to find the shortest path from A to H. State the shortest path and its length. On a particular day, Robyn needs to check each road. She must travel along each road at least once. Robyn must start and finish at vertex A.
2. Use the route inspection algorithm to find the length of the shortest inspection route. State the edges that should be repeated. You should make your method and working clear.
   (5) The roads BD and BE become damaged and cannot be used. Robyn needs to travel along all the remaining roads to check that there is no damage to any of them. The inspection route must still start and finish at vertex A.
3. 1. State the edges that should be repeated.
   2. State a possible route and calculate its length. You must make your method and working clear.

4. \begin{figure}[h] \end{figure} [The total weight of the network is 293] Figure 2 models a network of roads. The number on each edge gives the time, in minutes, taken to travel along the corresponding road.

1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to J . State the quickest route.
   (6) The road represented by edge GJ is closed due to essential maintenance. Sahil needs to travel along all the other roads to check that they are in good repair. Sahil wishes to complete his route as quickly as possible and will start and finish at the same vertex.
2. Use the route inspection algorithm to find the duration of Sahil's quickest route. State the edges that will need to be traversed twice. You should make your method and working clear.
   (6) Given that Sahil will start and finish at vertex C,
3. state the number of times that Sahil will visit vertex E and vertex F in his inspection route.
   (2)

2. \begin{figure}[h] \end{figure} A surveyor 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 Figure 3. The number on each arc represents the length of that road in miles. To check all the roads, she needs to travel along each road at least once. She wishes to minimise the total distance travelled. The surveyor's office is at F , so she starts and ends her journey at F .

1. Find a route for the surveyor to follow. State your route and its length. You must make your method and reasoning clear. The surveyor lives at D and wonders if she can reduce the distance travelled by starting from home and inspecting all the roads on the way to her office at F .
2. By considering the pairings of all relevant nodes, find the arcs that will need to be traversed twice in the inspection route from D to F. You must make your method and working clear.
3. Determine which of the two routes, the one starting at F and ending at F , or the one starting at D and ending at F , is longer. You must show your working.

6. \begin{figure}[h] \end{figure} Figure 4 models a network of water pipes that need to be inspected. The number on each arc represents the length, in km , of that pipe. A machine is to be used to inspect for leaks. The machine must travel along each pipe at least once, starting and finishing at the same point, and the length of the inspection route is to be minimised.
[0pt] [The total weight of the network is 185 km ]

1. Starting at A, use an appropriate algorithm to find the length of the shortest inspection route. You should make your method and working clear. Given that it is now permitted to start and finish the inspection at two distinct vertices,
2. state which two vertices should be chosen to minimise the length of the new route. Give a reason for your answer.

1. \begin{figure}[h] \end{figure} A local council is responsible for maintaining pavements in a district. The roads for which it is responsible are represented by arcs in Fig. 1.The junctions are labelled \(A , B , C , \ldots , G\). The number on each arc represents the length of that road in km. The council has received a number of complaints about the condition of the pavements. In order to inspect the pavements, a council employee needs to walk along each road twice (once on each side of the road) starting and ending at the council offices at \(C\). The length of the route is to be minimal. Ignore the widths of the roads.

1. Explain how this situation differs from the standard Route Inspection problem.
2. Find a route of minimum length and state its length.

3. \begin{figure}[h] \end{figure} [The total weight of the network is 120]

1. Explain what is meant by the term "path".
2. State, with a reason, whether the network in Figure 2 is Eulerian, semi-Eulerian or neither. Figure 2 represents a network of cycle tracks between eight villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H . The number on each arc represents the length, in km , of the corresponding track. Samira lives in village A, and wishes to visit her friend, Daisy, who lives in village H.
3. Use Dijkstra's algorithm to find the shortest path that Samira can take. An extra cycle track of length 9 km is to be added to the network. It will either go directly between C and D or directly between E and G . Daisy plans to cycle along every track in the new network, starting and finishing at H .
   Given that the addition of either track CD or track EG will not affect the final values obtained in (c),
4. use a suitable algorithm to find out which of the two possible extra tracks will give Daisy the shortest route, making your method and working clear. You must

5. \begin{figure}[h] \end{figure} [The weight of the network is \(20 x + 3\) ] Figure 4 shows a graph G that contains 8 arcs and 6 vertices.

1. State the minimum number of arcs that would need to be added to make G into an Eulerian graph.
2. Explain whether or not the route \(\mathrm { A } - \mathrm { C } - \mathrm { F } - \mathrm { E } - \mathrm { C } - \mathrm { D } - \mathrm { B }\) is an example of a path on G. Figure 4 represents a network of 8 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road. You are given that \(x > 1.6\) A route is required that
   The route inspection algorithm is applied to the network in Figure 4 and the time taken for the route is found to be at most 189 minutes. Given that the inspection route contains two roads that need to be traversed twice,
3. determine the range of possible values of \(x\), making your reasoning clear.