Route inspection

[ The total weight of the network is 85 ] Figure 4 represents a network of roads. The number on each edge represents the length, in miles, of the corresponding road. Robyn wishes to travel from A to H. She wishes to minimise the distance she travels.

Use Dijkstra’s algorithm to find the shortest path from A to H. State the shortest path and its length.

On a particular day, Robyn needs to check each road. She must travel along each road at least once. Robyn must start and finish at vertex A.

Use the route inspection algorithm to find the length of the shortest inspection route. State the edges that should be repeated. You should make your method and working clear.

The roads BD and BE become damaged and cannot be used. Robyn needs to travel along all the remaining roads to check that there is no damage to any of them. The inspection route must still start and finish at vertex A.

State the edges that should be repeated.

State a possible route and calculate its length. You must make your method and working clear.

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

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.

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.

Explain why the inspection route should start at a vertex with odd degree.

The guard decides to start the inspection route at F and the length of the inspection route must still be minimised.

Determine where the guard should finish. You must give reasons for your answer.

State a possible route and its length.

[ The total weight of the network is 2090 ]

Explain why a network cannot have an odd number of vertices of odd valency.

Write down the vertices at which the route will start and finish.

A new road, AB, of length 130m 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.

Use the route inspection algorithm to find the roads that will need to be traversed twice. You must make your method and working clear.

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.

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.

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

Use the route inspection algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.

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.

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.

[ The total weight of the network is 181 miles ] Figure 4 represents a network of power cables that have to be inspected. The number on each arc represents the length, in km, of that cable. A route of minimum length that traverses each cable at least once and starts and finishes at A needs to be found.

Use the route inspection algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.

Write down a possible shortest inspection route, giving its length.

It is now decided to start and finish the inspection route at two distinct vertices. The route must still traverse each cable at least once.

Determine possible starting and finishing points so that the length of the route is minimised. You must give reasons for your answer.

[The weight of the network is 379] Figure 5 represents the roads in a highland wildlife conservation park. The vertices represent warden stations. The number on each arc gives the length, in km, of the corresponding road. During the winter months the park is closed. It is only necessary to ensure road access to the warden stations.

Use Prim’s algorithm, starting at A, to find a minimum connector for the network in Figure 5. You must state the order in which you include the arcs.

Given that it costs £80 per km to keep the selected roads open in winter, calculate the minimum cost of ensuring road access to all the warden stations.

At the end of winter, Ben inspects all the roads before the park re-opens. He needs to travel along each road at least once. He will start and finish at A, and wishes to minimise the length of his route.

Use the route inspection algorithm to find the roads that will be traversed twice. You must make your method and working clear.

Find the length of the shortest inspection route.

If Ben starts and finishes his inspection route at different warden stations, a shorter inspection route is possible.

Determine the two warden stations Ben should choose as his starting and finishing points in order that his route has minimum length. Give a reason for your answer and state the length of the route.

[ The total weight of the network is 1436 m ]

Explain the term valency.

to inspect the system to locate the leak. The device will start and finish at A and travel along each pipe at least once. The length of this inspection route needs to be minimised.

Use the route inspection algorithm to find the pipes that will need to be traversed twice. You should make your method and working clear.

Find the length of the inspection route.

Pipe HI is now found to be blocked; it is sealed and will not be replaced. An inspection route is now required that excludes pipe HI. The length of the inspection route must be minimised.

Find the length of the minimum inspection route excluding HI. Justify your answer.

Given that the device may now start at any vertex and finish at any vertex, find a minimum inspection route, excluding HI.

[The total weight of the network is 98 km] Figure 5 models a network of gas pipes that have to be inspected. The number on each arc represents the length, in km, of that pipe. A route of minimum length that traverses each pipe at least once and starts and finishes at A needs to be found.

Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.

Write down a possible shortest inspection route, giving its length.

It is now decided to start the inspection route at D. The route must still traverse each pipe at least once but may finish at any node.

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.

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

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.

State the roads that must be traversed twice and the length of the route.

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.

Given that the route is to be minimised, determine where the machine should finish. Give reasons to justify your answer.