Minimum spanning trees

Figure 3 represents nine computer terminals, A, B, C, D, E, F, G, H and J, at Pearsonby School. The school wishes to connect them to form a single computer network. The number on each arc represents the cost, in pounds, of connecting the corresponding computer terminals.

Use Prim’s algorithm, starting at B, to find the minimum spanning tree for the computer network. You must clearly state the order in which you select the arcs of your tree.

State the minimum cost of connecting the nine computer terminals.

It is discovered that some computer terminals are already connected. There are already direct connections along BD and FJ, as shown in bold in Diagram 1 in the answer book. It is decided to use these connections.

Use Kruskal’s algorithm to find the minimum spanning tree that includes arcs BD and FJ. You must list the arcs in the order that you consider them. In each case, state whether or not you are adding the arcs to your spanning tree.

Figure 3 represents a network of tram tracks. The number on each edge represents the length, in miles, of the corresponding track. One day, Sarah wishes to travel from A to F. She wishes to minimise the distance she travels.

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

On another day, Sarah wishes to travel from A to F via J.

Find a route of minimal length that goes from A to F via J and state its length.

Use Prim’s algorithm, starting at G, to find the minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree.

State the length, in miles, of the minimum spanning tree.

The numbers on the 17 arcs in the network shown in Figure 5 represent the distances, in km, between nine nodes, A, B, C, D, E, F, G, H and J.

Use Kruskal’s algorithm to find a minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.

Starting at G, use Prim’s algorithm to find a minimum spanning tree. You must clearly state the order in which you select the arcs of your tree.

Find the weight of the minimum spanning tree.

A connected graph V has n nodes. The sum of the degrees of all the nodes in V is m. The graph T is a minimum spanning tree of V.

Write down, in terms of m, the number of arcs in V.

Write down, in terms of n, the number of arcs in T.

Hence, write down an inequality, in terms of m and n, comparing the number of arcs in T and V.

The network represented by the table shows the least distances, in km, between seven theatres, A, B, C, D, E, F and G. Jasmine needs to visit each theatre at least once starting and finishing at A. She wishes to minimise the total distance she travels. The least distance between A and B, is x km, where 21 < x < 27

Using Prim’s algorithm, starting at A, obtain a minimum spanning tree for the network. You should list the arcs in the order in which you consider them.

Use your answer to (a) to determine an initial upper bound for the length of Jasmine’s route.

Use the nearest neighbour algorithm, starting at A, to find a second upper bound for the length of the route.

The nearest neighbour algorithm starting at F gives a route of F – E – B – A – G – D – C – F.

State which of these two nearest neighbour routes gives the better upper bound. Give a reason for your answer.

Starting by deleting A, and all of its arcs, a lower bound of 159 km for the length of the route is found.

Find x, making your method clear.

Write down the smallest interval that you can be confident contains the optimal length of Jasmine’s route. Give your answer as an inequality.

The table shows the least times, in seconds, that it takes a robot to travel between six points in an automated warehouse. These six points are an entrance, A, and five storage bins, B, C, D, E and F. The robot will start at A, visit each bin, and return to A. The total time taken for the robot’s route is to be minimised.

Show that there are two nearest neighbour routes that start from A. You must make the routes and their lengths clear.

Starting by deleting F, and all of its arcs, find a lower bound for the time taken for the robot’s route.

Use your results to write down the smallest interval which you are confident contains the optimal time for the robot’s route.

The table shows the average journey time, in minutes, between six towns, A, B, C, D, E and F.

Use Prim’s algorithm, starting at A, to find a minimum spanning tree for this network. You must list the arcs that form your tree in the order in which you selected them.

Draw your tree using the vertices given in Diagram 1 in the answer book.

Find the weight of your minimum spanning tree.

Kruskal’s algorithm may also be used to find a minimum spanning tree.

State three differences between Prim’s algorithm and Kruskal’s algorithm.

The table shows the times, in days, needed to repair the network of roads between six towns, A, B, C, D, E and F, following a flood.

Use Prim’s algorithm, starting at A, to find the minimum connector for this network. You must list the arcs that form your tree in the order that you selected them.

Draw your minimum connector using the vertices given in Diagram 1 in the answer book.

Add arcs from D, E and F to Diagram 2 in the answer book, so that it shows the network of roads shown by the table.

Use Kruskal’s algorithm to find the minimum connector. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum connector.

State the minimum time needed, in days, to reconnect the six towns.

The table shows the least distances, in km, between five hiding places, A, B, C, D and E. Agent Goodie has to leave a secret message in each of the hiding places. He will start and finish at A, and wishes to minimise the total distance travelled.

Use Prim’s algorithm to find a minimum spanning tree for this network. Make your order of arc selection clear.

Use your answer to part (a) to determine an initial upper bound for the length of Agent Goodie’s route.

Show that there are two nearest neighbour routes which start from A. State these routes and their lengths.

State the better upper bound from your answers to (b) and (c).

Starting by deleting B, and all of its arcs, find a lower bound for the length of Agent Goodie’s route.

Consider your answers to (d) and (e) and hence state an optimal route.

[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 table shows the lengths, in km, of a network of roads between seven villages, A, B, C, D, E, F and G.

Complete the drawing of the network in Diagram 1 of the answer book by adding the necessary arcs from vertex D together with their weights.

Use Kruskal’s algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.

Draw the minimum spanning tree using the vertices provided in Diagram 2 in the answer book.

State the weight of the minimum spanning tree.

Define the terms

tree,

minimum spanning tree.

Use Kruskal’s algorithm to find a minimum spanning tree for the network shown in Figure 1. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.

Draw your minimum spanning tree using the vertices given in Diagram 1 in the answer book.

State whether your minimum spanning tree is unique. Justify your answer.

The network in Figure 1 shows the distances, in km, between six towns, A, B, C, D, E and F. Mabintou needs to visit each town. She will start and finish at A and wishes to minimise the total distance travelled.

By inspection, complete the two copies of the table of least distances in your answer book.

Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Mabintou’s route. Write down the route which gives this upper bound.

Starting by deleting A, and all of its arcs, find a lower bound for the route length.

Use Kruskal’s algorithm to find a minimum spanning tree for the network shown in Figure 2. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.

Starting at A, use Prim’s algorithm to find a minimum spanning tree for the network in Figure 2. You must clearly state the order in which you include the arcs in your tree.

Draw a minimum spanning tree for the network in Figure 2 using the vertices given in Diagram 1 of the answer book. State the weight of the minimum spanning tree.

A new spanning tree is required which includes the arcs DI and HG, and which has the lowest possible total weight.

Explain which algorithm you would choose to complete the tree, and how the algorithm should be adapted. (You do not need to find the tree.)

The network in figure 2 shows the distances, in km, between eight weather data collection points. Starting and finishing at A, Alice needs to visit each collection point at least once, in a minimum distance.

Obtain a minimum spanning tree for the network using Kruskal’s algorithm, stating the order in which you select the arcs.

Use your answer to part (a) to determine an initial upper bound for the length of the route.

Starting from your initial upper bound use short cuts to find an upper bound, which is below 630km. State the corresponding route.

Use the nearest neighbour algorithm starting at B to find a second upper bound for the length of the route.

By deleting C, and all of its arcs, find a lower bound for the length of the route.

Use your results to write down the smallest interval which you are confident contains the optimal length of the route.