Chinese Postman with different start/end

5 A council is responsible for gritting main roads in a district. The network shows the main roads in the district. The number on each edge shows the length of the road, in kilometres. The gritter starts from the depot located at point \(A\), and must drive along all the roads at least once before returning to the depot. \includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-10_1294_923_525_555}

1. Find the length of an optimal Chinese postman route around the main roads in the district, starting and finishing at \(A\).
2. Zac, a supervisor, wishes to inspect all the roads. He leaves the depot, located at point \(A\), and drives along all the roads at least once before finishing at his home, located at point \(C\). Find the length of an optimal route for Zac.
3. Liz, a reporter, intends to drive along all the roads at least once in order to report on driving conditions. She can start her journey at any point and can finish her journey at any point.
   1. Find the length of an optimal route for Liz.
   2. State the points from which Liz could start in order to achieve this optimal route.
      \includegraphics[max width=\textwidth, alt={}]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-11_2486_1714_221_153}

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.

5. \begin{figure}[h] \end{figure} [The total weight of the network is 253] Figure 1 represents a network of roads between 10 cities, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in miles, of the corresponding road. One day, Mabintou 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 your path and its length. On another day, Mabintou wishes to travel from F to K via A.
2. Find a route of minimum length from F to K via A and state its length. The roads between the cities need to be inspected. James must travel along each road at least once. He wishes to minimise the length of his inspection route. James will start his inspection route at A and finish at J.
3. By considering the pairings of all relevant nodes, find the length of James' route. State the arcs that will need to be traversed twice. You must make your method and working clear.
   (6)
4. State the number of times that James will pass through F. It is now decided to start the inspection route at D. James must minimise the length of his route. He must travel along each road at least once but may finish at any vertex.
5. State the vertex where the new inspection route will finish.
6. Calculate the difference between the lengths of the two inspection routes.

3. \begin{figure}[h] \end{figure} [The total weight of the network is 458] Figure 2 represents a network of roads between nine towns, A, B, C, D, E, F, G, H and J. The number on each edge represents the length, in kilometres, 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 towns must be inspected. Claude must travel along each road at least once. Claude will start the inspection route at A and finish at J. Claude wishes to minimise the length of the inspection route.
2. By considering the pairings of all relevant nodes, find the length of Claude's route. State the arcs that will need to be traversed twice. If Claude does not start the inspection route at A and finish at J, a shorter inspection route is possible.
3. Determine the two towns at which Claude should start and finish so that the route has minimum length. Give a reason for your answer and state the length of this route.

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.

3. \begin{figure}[h] \end{figure} [The total weight of the network is 413] Figure 1 represents a network of cycle tracks between ten towns, A, B, C, D, E, F, G, H, J and K. The number on each arc represents the length, in kilometres, of the corresponding track.

1. Use Dijkstra's algorithm to find the shortest path from A to J. Abi needs to travel along every track shown in Figure 1 to check that they are all in good repair. She needs to start her inspection route at town G and finish her route at either town J or town K. Abi wishes to minimise the total distance required to traverse every track.
2. By considering all relevant pairings of vertices, determine whether Abi should finish her inspection route at town J or town K. You must
   The direct track between town B and town C and the direct track between town H and town K are now closed to all users. A second person, Tarig, is asked to check all the remaining tracks starting at G and finishing at H. Tarig wishes to minimise the total length of his inspection route.
3. Determine which route, Abi's or Tarig's, is shorter. You must make your working clear.