D1 January 2013 Q5

EdexcelOld spec15 marksMinimum Spanning TreesRoute Inspection

5.

Figure 5: network of roads A to J with lengths in km
Figure 5

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

(a) 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. (3)
(b) 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. (2)

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.

(c) Use the route inspection algorithm to find the roads that will be traversed twice. You must make your method and working clear. (6)
(d) Find the length of the shortest inspection route. (1)

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

(e) 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. (3)
‹ Previous18 of 31 in Minimum Spanning TreesNext ›