Basic Chinese Postman (closed route)

3 The following network shows the lengths, in miles, of roads connecting nine villages, \(A , B , \ldots , I\). A delivery man lives in village \(A\) and is to drive along all the roads at least once before returning to \(A\). \includegraphics[max width=\textwidth, alt={}, center]{d666b2d9-cb14-4d29-a842-8c87f1b25dbd-06_1072_1027_548_502}

1. Find the length of an optimal Chinese postman route around the nine villages, starting and finishing at \(A\).
2. For an optimal Chinese postman route corresponding to your answer in part (a), state:
   1. the number of times village \(E\) would be visited;
   2. the number of times village \(I\) would be visited.

5. \begin{figure}[h] \end{figure} [The total weight of the network is 82] \section*{Question 5 continued}

5 There is a one-way system in Manchester. Mia is parked at her base, \(B\), in Manchester and intends to visit four other places, \(A , C , D\) and \(E\), before returning to her base. The following table shows the distances, in kilometres, for Mia to drive between the five places \(A , B , C , D\) and \(E\). Mia wants to keep the total distance that she drives to a minimum.

1. Find the length of the tour \(B E C D A B\).
2. Find the length of the tour obtained by using the nearest neighbour algorithm starting from \(B\).
3. Write down which of your answers to parts (a) and (b) would be the better upper bound for the total distance that Mia drives.
4. On a particular day, the council decides to reverse the one-way system. For this day, find the length of the tour obtained by using the nearest neighbour algorithm starting from \(B\).

4 A communications company is conducting a feasibility study into the installation of underground television cables between 5 neighbouring districts. The length of the possible pathways for the television cables between each pair of districts, in miles, is shown in the table. The pathways all run alongside cycle tracks. 4

1. Give a possible reason, in context, why some of the table entries are labelled as ***. 4
2. As part of the feasibility study, Sally, an engineer needs to assess each possible pathway between the districts. To do this, Sally decides to travel along every pathway using a bicycle, starting and finishing in the same district. From past experience, Sally knows that she can travel at an average speed of 12 miles per hour on a bicycle. Find the minimum time, in minutes, that it will take Sally to cycle along every pathway.
   [0pt] [4 marks]

\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]

1. Explain why a network cannot have an odd number of vertices of odd degree. (2)

\includegraphics{figure_4} Figure 4 shows a network of paths in a public park. The number on each arc represents the length of that path in metres. Hamish needs to walk along each path at least once to check the paths for frost damage starting and finishing at \(A\). He wishes to minimise the total distance he walks.

1. Use the route inspection algorithm to find which paths, if any, need to be traversed twice. (4)
2. Find the length of Hamish's route. [The total weight of the network in Figure 4 is 4180 m.] (1)

(Total 7 marks)

\includegraphics{figure_2}

1. Describe a practical problem that could be modelled using the network in Fig. 2 and solved using the route inspection algorithm. [1]
2. Use the route inspection algorithm to find which paths, if any, need to be traversed twice. [4]
3. State whether your answer to part (b) is unique. Give a reason for your answer. [1]
4. Find the length of the shortest inspection route that traverses each arc at least once and starts and finishes at the same vertex. [1]

Given that it is permitted to start and finish the inspection at two distinct vertices,

1. find which two vertices should be chosen to minimise the length of the route. Give a reason for your answer. [2]

A council wants to convert all of the street lighting in a village to use LED lighting. The network below shows each street in the village. Each node represents a junction and the weight of each arc represents the length, in metres, of the street. The street lights are only positioned on one side of each street in the village. \includegraphics{figure_6} The total length of all of the streets in the village is 2250 metres. In order to determine the total number of street lights in the village, a council worker is required to walk along every street in the village at least once, starting and finishing at the same junction. The shortest possible distance the council worker can walk in order to determine the total number of street lights in the village is \(x\) metres.

1. Find the value of \(x\) Fully justify your answer. [4 marks]
2. A new council regulation requires that the mean distance along a street between adjacent LED street lights in a village be less than 25 metres. The council worker counted 91 different street lights on their journey around the village. Determine whether or not the village will meet the new council regulation. [2 marks]