Optimal starting/finishing vertices

5. \begin{figure}[h] \end{figure} \section*{[The total weight of the network is 214]} Figure 5 models a network of canals that have to be inspected. The number on each arc represents the length, in km , of the corresponding canal. Priya needs to travel along each canal at least once and wishes to minimise the length of her inspection route. She must start and finish at A .

1. Use the route inspection algorithm to find the length of her route. State the arcs that will need to be traversed twice. You should make your method and working clear.
   (6)
2. State the number of times that vertex F would appear in Priya's route.
   (1) It is now decided to start the inspection route at H . The route must still travel along each canal at least once but may finish at any vertex.
3. Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of the minimum route.
   (3)

5. \begin{figure}[h] \end{figure} [The total weight of the network is 166] Figure 3 models a network of cycle lanes that must be inspected. The number on each arc represents the length, in km, of the corresponding cycle lane. Lance needs to cycle along each lane at least once and wishes to minimise the length of his inspection route. He must start and finish at A.

1. Use an appropriate algorithm to find the length of the route. State the cycle lanes that Lance will need to traverse twice. You should make your method and working clear.
   (6)
2. State the number of times that vertex C appears in Lance's route.
   (1) It is now decided that the inspection route may finish at any vertex. Lance will still start at A and must cycle along each lane at least once.
3. Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of this new minimum route.
   (3)

5. \begin{figure}[h] \end{figure} (The total weight of the network in Figure 3 is 543 km .)
Figure 3 models a network of railway tracks that have to be inspected. The number on each arc is the length, in km , of that section of railway track.
Each track must be traversed at least once and the length of the inspection route must be minimised.
The inspection route must start and finish at the same vertex.

1. Use an appropriate algorithm to find the length of the shortest inspection route. You should make your method and working clear. It is now permitted to start and finish the inspection at two distinct vertices.
2. State which two vertices should be chosen to minimise the length of the new route. Give a reason for your answer.

5. \begin{figure}[h] \end{figure} \section*{[The total weight of the network is 344 miles]} Figure 4 represents a railway network. The number on each arc represents the length, in miles, of that section of the railway. Sophie needs to travel along each section to check that it is in good condition.
She must travel along each arc of the network at least once, and wants to find a route of minimum length. She will start and finish at A.

1. Use the route inspection algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
2. Write down a possible shortest inspection route, giving its length. Sophie now decides to start the inspection route at E. The route must still traverse each arc at least once but may finish at any vertex.
3. Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of your route.

4. \begin{figure}[h] \end{figure} [The total weight of the network is 2090]

1. Explain why a network cannot have an odd number of vertices of odd valency. Figure 4 represents a network of 13 roads in a village. The number on each arc is the length, in metres, of the corresponding road. A route of minimum length that traverses each road at least once needs to be found. The route may start at any vertex and finish at any vertex.
2. Write down the vertices at which the route will start and finish.
   (1) A new road, AB , of length 130 m is built. A route of minimum length that traverses each road, including AB , needs to be found. The route must start and finish at A .
3. Use the route inspection algorithm to find the roads that will need to be traversed twice. You must make your method and working clear.
4. Calculate the length of a possible shortest inspection route. It is now decided to start and finish the inspection route at two distinct vertices. A route of minimum length that traverses each road, including AB , needs to be found. The route must start at A .
5. State the finishing point so that the length of the route is minimised. Calculate how much shorter the length of this route is compared to the length of the route in (d). You must make your method and calculations clear.
   (3)

6. \begin{figure}[h] \end{figure} Figure 4 models a network of water pipes that need to be inspected. The number on each arc represents the length, in km , of that pipe. A machine is to be used to inspect for leaks. The machine must travel along each pipe at least once, starting and finishing at the same point, and the length of the inspection route is to be minimised.
[0pt] [The total weight of the network is 185 km ]

1. Starting at A, use an appropriate algorithm to find the length of the shortest inspection route. You should make your method and working clear. Given that it is now permitted to start and finish the inspection at two distinct vertices,
2. state which two vertices should be chosen to minimise the length of the new route. Give a reason for your answer.

5. \begin{figure}[h] \end{figure} [The total weight of the network is 625 m ]
Figure 3 models a network of paths in a park. The number on each arc represents the length, in m , of that path.
Rob needs to travel along each path to inspect the surface. He wants to minimise the length of his route.

1. Use the route inspection algorithm to find the length of his route. State the arcs that should be repeated. You should make your method and working clear.
   (6) The surface on each path is to be renewed. A machine will be hired to do this task and driven along each path.
   The machine will be delivered to point G and will start from there, but it may be collected from any point once the task is complete.
2. Given that each path must be traversed at least once, determine the finishing point so that the length of the route is minimised. Give a reason for your answer and state the length of your route.
   (3)

\includegraphics{figure_2} Figure 2 models a network of roads which need to be inspected to assess if they need to be resurfaced. The number on each arc represents the length, in km, of that road. Each road must be traversed at least once and the length of the inspection route must be minimised.

1. Starting and finishing at \(A\), solve this route inspection problem. You should make your method and working clear. State the length of the shortest route. (The weight of the network is 77 km.) [5]

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

1. state which two vertices you should choose to minimise the length of the route. Give a reason for your answer. [2]

(Total 7 marks)

\includegraphics{figure_2} Figure 2 shows the network of pipes represented by arcs. The length of each pipe, in kilometres, is shown by the number on each arc. The network is to be inspected for leakages, using the shortest route and starting and finishing at A.

1. Use the route inspection algorithm to find which arcs, if any, need to be traversed twice. [4]
2. State the length of the minimum route. [The total weight of the network is 394 km.] [1]

It is now permitted to start and finish the inspection at two distinct vertices.

1. State, with a reason, which two vertices should be chosen to minimise the length of the new route. [2]

A jeweller is making pendants. Each pendant is made by bending a single, continuous strand of wire. Each pendant has the same design as shown below. \includegraphics{figure_7} The lengths on the diagram are in millimetres. The sum of these lengths is 240 mm As the jeweller does not cut the wire, some sections require a double length of wire.

1. The jeweller makes a pendant by starting and finishing at \(B\) Find the minimum length of the strand of wire that the jeweller needs to make the pendant. Fully justify your answer. [4 marks]
2. The jeweller makes another pendant of the same design. Find the minimum possible length for the strand of wire that the jeweller would need. [2 marks]
3. By considering the differences between the pendants in part (a) and part (b), state one reason why the jeweller may prefer the pendant in part (a). [1 mark]