Chinese Postman with start/end constraints

6. \begin{figure}[h] \end{figure} [The total weight of the network is 315]
Figure 3 represents a network of roads between nine parks, A, B, C, D, E, F, G, H and J. The number on each edge represents the length, in miles, 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 parks need to be inspected. Robin must travel along each road at least once. Robin wishes to minimise the length of the inspection route. Robin will start the inspection route at C and finish at E .
2. By considering the pairings of all relevant nodes, find the length of Robin's route.
3. State the number of times Robin will pass through G . It is now decided to start and finish the inspection route at A. Robin must still minimise the length of the route and travel along each road at least once.
4. Calculate the difference between the lengths of the two inspection routes.
5. State the edges that need to be traversed twice in the route that starts and finishes at A , but do not need to be traversed twice in the route that starts at C and finishes at E .

3. \begin{figure}[h] \end{figure} [The total weight of the network is \(139 + x + y\) ]

1. Explain what is meant by the term "tree". Figure 3 represents a network of walkways in a warehouse.
   The arcs represent the walkways and the nodes represent junctions between them.
   The number on each arc represents the length, in metres, of the corresponding walkway.
   The values \(x\) and \(y\) are unknown, however it is known that \(x\) and \(y\) are integers and that $$9 < x < y < 14$$
2. 1. Use Dijkstra's algorithm to find the shortest route from A to M.
   2. State an expression for the length of the shortest route from A to M . The warehouse manager wants to check that all of the walkways are in good condition.
      Their inspection route starts at B and finishes at C .
      The inspection route must traverse each walkway at least once and be as short as possible.
3. State the arcs that are traversed twice.
4. State the number of times that H appears in the inspection route. The warehouse manager finds that the total length of the inspection route is 172 metres.
5. Determine the value of \(x\) and the value of \(y\)

1. \begin{figure}[h] \end{figure} [The total weight of the network is 189]
Figure 1 represents a network of pipes in a building. The number on each arc is the length, in metres, of the corresponding pipe.

1. Use Dijkstra's algorithm to find the shortest path from A to F . State the path and its length. On a particular day, Gabriel needs to check each pipe. A route of minimum length, which traverses each pipe at least once and which starts and finishes at A, needs to be found.
2. Use an appropriate algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
3. State the minimum length of Gabriel's route. A new pipe, BG, is added to the network. A route of minimum length that traverses each pipe, including BG, needs to be found. The route must start and finish at A. Gabriel works out that the addition of the new pipe increases the length of the route by twice the length of BG .
4. Calculate the length of BG. You must show your working.

2. \begin{figure}[h] \end{figure} Figure 1 represents a network of corridors in a building. The number on each arc represents the length, in metres, of the corresponding corridor.

1. Use Dijkstra's algorithm to find the shortest path from A to D, stating the path and its length. On a particular day, Naasir needs to check the paintwork along each corridor. Naasir must find a route of minimum length. It must traverse each corridor at least once, starting at B and finishing at G .
2. Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
3. Find the length of Naasir's route. On a different day, all the corridors that start or finish at B are closed for redecorating. Naasir needs to check all the remaining corridors and may now start at any vertex and finish at any vertex. A route is required that excludes all those corridors that start or finish at B .
4. 1. Determine the possible starting and finishing points so that the length of Naasir's route is minimised. You must give reasons for your answer.
   2. Find the length of Naasir's new route.

2. \begin{figure}[h] \end{figure} [The total weight of the network is 299] Figure 1 represents a network of cycle tracks between 10 landmarks, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in kilometres, of the corresponding track. One day, Blanche wishes to cycle from A to K. She wishes to minimise the distance she travels.

1. 1. Use Dijkstra's algorithm to find the shortest path from A to K .
   2. State the length of the shortest path from A to K .
      (6) The cycle tracks between the landmarks now need to be inspected. Blanche must travel along each track at least once. She wishes to minimise the length of her inspection route. Blanche will start her inspection route at D and finish at E .
2. 1. State the edges that will need to be traversed twice.
   2. Find the length of Blanche's route. It is now decided to start the inspection route at A and finish at K . Blanche must minimise the length of her route and travel along each track at least once.
3. By considering the pairings of all relevant nodes, find the length of Blanche's new route. You must make your method and working clear.