Count vertex occurrences in 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).

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 Paulo sells vegetables from his van. He drives around the streets of a small village. The network shows the streets in the village. The number on each edge shows the time, in minutes, to drive along that street. Paulo starts from his house located at vertex \(A\) and drives along all the streets at least once before returning to his house. \includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-10_1518_1605_598_198} The total of all the times in the diagram is 79.5 minutes.

1. Find the length of an optimal Chinese postman route around the village, starting and finishing at \(A\). (Shortest routes between vertices may be found by inspection.)
2. For an optimal Chinese postman route, state:
   1. the number of times the vertex \(F\) would occur;
   2. the number of times the vertex \(D\) would occur.
3. Toto is standing for the position of Mayor in the local elections. He intends to travel along all the roads at least once. He can start his journey at any vertex and can finish his journey at any vertex.
   1. Find the length of an optimal route for Toto.
      [0pt]
   2. State the vertices from which Toto could start in order to achieve this optimal route. [3 marks]

5 The network shows the paths mown through a wildflower meadow so that visitors can use these paths to enjoy the flowers. The lengths of the paths are shown in metres. \includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-10_1097_1603_413_214} The total length of all the paths is 1400 m .
The mower is kept in a shed at \(A\). The groundskeeper must mow all the paths and return the mower to its shed.

1. Find the length of an optimal Chinese postman route starting and finishing at \(A\).
2. State the number of times that the mower, following the optimal route, will pass through:
   1. \(C\);
   2. \(D\).

4 Amal delivers free advertiser magazines to all the houses in his village. The network shows the roads in his village. The number on each road shows the time, in minutes, that Amal takes to walk along that road. \includegraphics[max width=\textwidth, alt={}, center]{fb95068f-f76d-492a-b385-bce17b26ae30-08_846_1264_445_388}

1. Amal starts his delivery round from his house, at vertex \(A\). He must walk along each road at least once.
   1. Find the length of an optimal Chinese postman route around the village, starting and finishing at Amal's house.
   2. State the number of times that Amal passes his friend Dipak's house, at vertex \(D\).
2. Dipak offers to deliver the magazines while Amal is away on holiday. Dipak must walk along each road at least once. Assume that Dipak takes the same length of time as Amal to walk along each road.
   1. Dipak can start his journey at any vertex and finish his journey at any vertex. Find the length of time for an optimal route for Dipak.
   2. State the vertices at which Dipak could finish, in order to achieve his optimal route.
3. 1. Find the length of time for an optimal route for Dipak, if, instead, he wants to finish at his house, at vertex \(D\), and can start his journey at any other vertex.
   2. State the start vertex.