Route Inspection

1. Use the Route Inspection algorithm to find which paths, if any, need to be traversed twice. It is decided to start the inspection at node \(C\). The inspection must still traverse each pipe at least once but may finish at any node.
2. Explaining your reasoning briefly, determine the node at which the inspection should finish if the route is to be minimised. State the length of your route.
   (3)

\includegraphics{figure_2} Figure 2 shows the network of pipes represented by arcs. The length of each pipe, in kilometres, is shown by the number on each arc. The network is to be inspected for leakages, using the shortest route and starting and finishing at A.

1. Use the route inspection algorithm to find which arcs, if any, need to be traversed twice. [4]
2. State the length of the minimum route. [The total weight of the network is 394 km.] [1]

It is now permitted to start and finish the inspection at two distinct vertices.

1. State, with a reason, which two vertices should be chosen to minimise the length of the new route. [2]

A jeweller is making pendants. Each pendant is made by bending a single, continuous strand of wire. Each pendant has the same design as shown below. \includegraphics{figure_7} The lengths on the diagram are in millimetres. The sum of these lengths is 240 mm As the jeweller does not cut the wire, some sections require a double length of wire.

1. The jeweller makes a pendant by starting and finishing at \(B\) Find the minimum length of the strand of wire that the jeweller needs to make the pendant. Fully justify your answer. [4 marks]
2. The jeweller makes another pendant of the same design. Find the minimum possible length for the strand of wire that the jeweller would need. [2 marks]
3. By considering the differences between the pendants in part (a) and part (b), state one reason why the jeweller may prefer the pendant in part (a). [1 mark]

The network below shows 13 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges. The total of all the times is 384 minutes.

1. Use Dijkstra's algorithm on the network below, starting from \(M\), to find the minimum time to travel from \(M\) to each of the other towns. [7 marks]
2. 1. Find the travelling time of an optimum Chinese postman route around the network, starting and finishing at \(M\). [6 marks]
   2. State the number of times that the vertex \(F\) would appear in a corresponding route. [1 mark]

\includegraphics{figure_4}

The network below shows 13 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges. The total of all the times is 384 minutes.

1. Use Dijkstra's algorithm on the network below, starting from \(M\), to find the minimum time to travel from \(M\) to each of the other towns. [7 marks]
2. 1. Find the travelling time of an optimum Chinese postman route around the network, starting and finishing at \(M\). [6 marks]
   2. State the number of times that the vertex \(F\) would appear in a corresponding route. [1 mark]

\includegraphics{figure_4}

5 The network below represents the streets in a small village. The weights on the arcs show distances in metres. The total length of all the streets shown is 2200 metres. \includegraphics[max width=\textwidth, alt={}, center]{372c062a-793f-4fb8-a769-957479f5fce7-07_499_1264_367_402}

1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest route from \(A\) to \(H\).
2. Write down the shortest route from \(A\) to \(E\) and the shortest route from \(A\) to \(G\). Sheng-Li needs to travel along every street to deliver leaflets. He will start and finish at \(A\).
3. Explain why Sheng-Li will need to repeat some streets.
4. Showing your working, find the length of the shortest route that Sheng-Li can take, starting and ending at \(A\), to deliver leaflets to every street. The streets have houses on both sides. Sheng-Li does not want to keep crossing the streets from one side to the other. His friend Nadia offers to help him. They decide that they will work together and set off from \(A\), with Sheng-Li delivering to one side of \(A B\) and Nadia delivering to the other side. Each street will have to be travelled along twice, either by both of them travelling along it once or by one of them travelling along it twice. Nadia and Sheng-Li travel \(A - B - C - E\). At this point Sheng-Li is called back to \(A\). He travels along \(E - C - A\), delivering leaflets on one side of \(C A\). Nadia completes the leaflet delivery on her own.
5. Calculate the minimum distance that Nadia will need to travel on her own to complete the delivery. Explain how your answer was achieved and how you know that it is the minimum possible distance.
   [0pt] [4]

\includegraphics{figure_1}

1. Using an appropriate algorithm, obtain a suitable route starting and finishing at A. [5 marks]
2. Calculate the total length of this route. [2 marks]

5. \begin{figure}[h] \end{figure} Figure 6 represents a network of footpaths in a park. The number on each arc is the length, in metres, of the corresponding footpath. An inspection route of minimum length that traverses each footpath at least once needs to be found.

1. Write down the nodes at which the route will start and finish.
   (1) It is now decided to start the inspection route at B and finish the inspection route at D . A route of minimum length that traverses each footpath at least once needs to be found.
2. By considering the pairings of all relevant nodes find the arcs that will need to be traversed twice. You must make your method and working clear.
3. Write down a possible shortest inspection route, giving its length.

3 A local council is responsible for gritting roads. The diagram shows the length, in miles, of the roads that have to be gritted. \includegraphics[max width=\textwidth, alt={}, center]{76bccb26-f2ec-4798-bb6b-89c922f9651a-03_671_686_488_669} Total length \(= 87\) miles The gritter is based at \(A\), and must travel along all the roads, at least once, before returning to \(A\).

1. Explain why it is not possible to start from \(A\) and, by travelling along each road only once, return to \(A\).
2. Find an optimal 'Chinese postman' route around the network, starting and finishing at \(A\). State the length of your route.

1. Calculate the shortest distance that the mole must travel if it starts and ends at vertex \(A\).
2. The pipe connecting \(B\) to \(H\) is removed for repairs. By considering every possible pairing of odd vertices, and showing your working clearly, calculate the shortest distance that the mole must travel to pass along each pipe on this reduced network, starting and finishing at \(A\).

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 following network shows the times, in minutes, taken by a policeman to walk along roads connecting 12 places, \(A , B , \ldots , L\), on his beat. Each day, the policeman has to walk along each road at least once, starting and finishing at \(A\). \includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-08_1141_1313_461_360} The total of all the times in the network is 224 minutes.

1. Find the length of an optimal Chinese postman route for the policeman.
2. State the number of times that the vertex \(J\) would appear in a route corresponding to the length found in part (a).

\includegraphics{figure_2} The arcs in Fig. 2 represent roads in a town. The weight on each arc gives the time, in minutes, taken to drive along that road. The times taken to drive along \(AB\) and \(DE\) vary depending upon the time of day. A police officer wishes to drive along each road at least once, starting and finishing at \(A\). The journey is to be completed in the least time.

1. Briefly explain how you know that a route between \(B\) and \(E\) will have to be repeated. [1]
2. List the possible routes between \(B\) and \(E\). State how long each would take, in terms of \(x\) where appropriate. [2]
3. Find the range of values that \(x\) must satisfy so that \(DE\) would be one of the repeated arcs. [3] Given that \(x = 7\),
4. find the total time needed for the police officer to carry out this journey. [3]

A company delivers parcels to houses in a village, using a van. The network below shows the roads in the village. Each node represents a road junction and the weight of each arc represents the length, in miles, of the road between the junctions. \includegraphics{figure_6} The total length of all of the roads in the village is 31.4 miles. On one particular day, the driver is due to make deliveries to at least one house on each road, so the van must travel along each road at least once. However, the driver has forgotten to add fuel to the van and it only has 4.5 litres of fuel to use to make its deliveries. The van uses, on average, 1 litre of fuel to travel 7.8 miles along the roads of this village. Whilst making each delivery, the driver turns off the van's engine so it does not use any fuel. Determine whether the van has enough fuel for the driver to make all of the deliveries to houses on each road of the village, starting and finishing at the same junction. Fully justify your answer. [6 marks]

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.

\includegraphics{figure_3} An algorithm is described by the flow chart shown in Figure 3.

1. Given that \(x = 54\) and \(y = 63\), complete the table in the answer book to show the results obtained at each step when the algorithm is applied. [7]
2. State what the algorithm achieves. [2]

(Total 9 marks)

1. Explain why it is impossible to draw a network with exactly three odd vertices. [2]

\includegraphics{figure_1} The Route Inspection problem is solved for the network in Fig. 1 and the length of the route is found to be 100.

1. Determine the value of \(x\), showing your working clearly. [4]

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