Chinese Postman with flexible endpoints

5 The diagram shows a network of sixteen roads on a housing estate. The number on each edge is the length, in metres, of the road. The total length of the sixteen roads is 1920 metres. \begin{figure}[h] \end{figure}

1. Chris, an ice-cream salesman, travels along each road at least once, starting and finishing at the point \(A\). Find the length of an optimal 'Chinese postman' route for Chris.
2. Pascal, a paperboy, starts at \(A\) and walks along each road at least once before finishing at \(D\). Find the length of an optimal route for Pascal.
3. Millie is to walk along all the roads at least once delivering leaflets. She can start her journey at any point and she can finish her journey at any point.
   1. Find the length of an optimal route for Millie.
   2. State the points from which Millie could start in order to achieve this optimal route.

5 The network below shows some streets in a town. The number on each edge shows the length of that street, in metres. Leaflets are to be distributed by a restaurant owner, Tony, from his restaurant located at vertex \(B\). Tony must start from his restaurant, walk along all the streets at least once, before returning to his restaurant. \includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-10_643_1353_625_340} The total length of the streets is 2430 metres.

1. Find the length of an optimal Chinese postman route for Tony.
2. Colin also wishes to distribute some leaflets. He starts from his house at \(H\), walks along all the streets at least once, before finishing at the restaurant at \(B\). Colin wishes to walk the minimum distance. Find the length of an optimal route for Colin.
3. David also walks along all the streets at least once. He can start at any vertex and finish at any vertex. David also wishes to walk the minimum distance.
   1. Find the length of an optimal route for David.
   2. State the vertices from which David could start in order to achieve this optimal route.

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)

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 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.