Minimum Spanning Trees (Edexcel International A Level (IAL) Maths: Decision 1): Exam Questions

Explain why it is impossible to draw a graph with eight vertices in which the vertex orders are 1, 2, 2, 3, 3, 4, 4 and 6

Figure 3 shows the network T. The numbers on the arcs represent the distances, in km, between the eight vertices, A, B, C, D, E, F, G and H.

Determine whether or not A – C – D – E – C – B – F is an example of a path on T. You must justify your answer.

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

Draw the minimum spanning tree using the vertices given in Diagram 1

The weight of arc CF is now increased to a value of . The minimum spanning tree for T is unique and includes the same arcs as those found in (c).

Write down the smallest interval that must contain .

The network in Figure 2 shows the distances, in miles, between ten towns, A, B, C, H, L, M, P, S, W and Y.

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.

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

State the weight of the minimum spanning tree found in (b).

Sharon needs to visit all of the towns, starting and finishing in the same town, and wishes to minimise the total distance she travels.

Use your answer to (c) to calculate an initial upper bound for the length of Sharon’s route.

Use the nearest neighbour algorithm on the table, starting at W, to find an upper bound for the length of Sharon’s route. Write down the route which gives this upper bound.

Using the nearest neighbour algorithm, starting at Y, an upper bound of length 212 miles was found.

State the best upper bound that can be obtained by using this information and your answers from (d) and (e). Give the reason for your answer.

By deleting W and all of its arcs, find a lower bound for the length of Sharon’s route.

Sharon decides to take the route found in (e).

Interpret this route in terms of the actual towns visited.

Figure 1 shows a graph, T.

Write down an example of a path from A to J on T.

State, with a reason, whether A – B – C – D – E – G – F – H – J is an example of a tour on T.

The numbers on the 15 arcs in Figure 2 represent the distances, in km, between nine vertices, A, B, C, D, E, F, G, H and J, in a network.

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

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

State the weight of the minimum spanning tree.

Figure 5 models a network of roads. The number on each edge gives the length, in km, of the corresponding road. The vertices, A, B, C, D, E, F, G and H, represent eight towns. Bronwen needs to visit each town. She will start and finish at A and wishes to minimise the total distance travelled.

By applying Dijkstra’s algorithm, starting at A, complete the table of least distances.

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

A reduced network is formed by deleting A and all arcs that are directly joined to A.

(i) Use Prim’s algorithm, starting at C, to construct a minimum spanning tree for the reduced network. You must clearly state the order in which you select the arcs of your tree.

(ii) Hence, calculate a lower bound for the length of Bronwen’s route.

Using only the results from (b) and (c), write down the smallest interval that you can be confident contains the length of Bronwen’s optimal route.

The table below represents a complete network that shows the least costs of travelling between eight cities, A, B, C, D, E, F, G and H.

Srinjoy must visit each city at least once. He will start and finish at A and wishes to minimise his total cost.

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

State the weight of the minimum spanning tree.

Use your answer to (b) to help you calculate an initial upper bound for the total cost of Srinjoy’s route.

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

State the best upper bound that can be obtained by using your answers to (c) and (d).

Starting by deleting A and all of its arcs, find a lower bound for the total cost of Srinjoy’s route. You must make your method and working clear.

Use your results to write down the smallest interval that must contain the optimal cost of Srinjoy’s route.

Figure 3 models a network of roads. The number on each edge gives the length, in km, of the corresponding road. The vertices, A, B, C, D, E, F and G, represent seven towns. Derek needs to visit each town. He 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.

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

Interpret the route found in (b) in terms of the towns actually visited.

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

Clive needs to travel along the roads to check that they are in good repair. He wishes to minimise the total distance travelled and must start at A and finish at G.

By considering the pairings of all relevant nodes, find the length of Clive’s route. State the edges that need to be traversed twice. You must make your method and working clear.

Figure 5 shows a weighted graph that contains 12 arcs and 8 vertices.

It is given that

• no two arcs have the same weight

• and are positive integers

• arc CD is not in the minimum spanning tree for the graph

Explain why

It is also given that when Prim’s algorithm, starting at A, is applied to the weighted graph, AB is the first arc selected.

Show that and write down and simplify two further constraints on the values of and .

Represent these four constraints on Diagram 1.

Using Diagram 1 only, write down the possible pairs of values that and can take in the form ()

The minimum spanning tree for the weighted graph in Figure 5 has total weight 73 Six of the seven arcs in the minimum spanning tree are AB, AD, BC, CE, EF and GH.

Determine the value of and the value of . You must make your method and working clear.

Explain the difference between the classical and the practical travelling salesperson problems.

The table below shows the distances, in km, between seven museums, A, B, C, D, E, F and G.

Fran must visit each museum. She will start and finish at A and wishes to minimise the total distance travelled.

Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the length of Fran’s route. Make your method clear.

Starting at D, a second upper bound of 203 km was found.

State whether this is a better upper bound than the answer to (b), giving a reason for your answer.

A reduced network is formed by deleting G and all the arcs that are directly joined to G.

(i) Use Prim’s algorithm, starting at A, to construct a minimum spanning tree for the reduced network. You must clearly state the order in which you select the arcs of your tree.

(ii) Hence calculate a lower bound for the length of Fran’s route.

By deleting A, a second lower bound was found to be 188 km.

State whether this is a better lower bound than the answer to (d)(ii), giving a reason for your answer.

Using only the results from (c) and (e), write down the smallest interval that you can be confident contains the length of Fran’s optimal route.

The table below shows the distances, in metres, between six vertices, A, B, C, D, E and F, in a network.

Draw the weighted network using the vertices given in Diagram 1 .

Use Kruskal’s algorithm to find a minimum spanning tree for the network. You should list the edges in the order that you consider them and state whether you are adding them to your minimum spanning tree.

Draw the minimum spanning tree on Diagram 2 and state its total weight.

Weight of minimum spanning tree _________________________________

Define the terms

(i) tree,

(ii) minimum spanning tree.

Use Kruskal’s algorithm to find the minimum spanning tree for the network shown in Figure 1. You must clearly show the order in which you consider the edges. For each edge, state whether or not you are including it in the minimum spanning tree.

Draw the minimum spanning tree using the vertices given in Diagram 1 below and state the weight of the minimum spanning tree.

Figure 1 represents a network of roads between ten villages, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in kilometres, of the corresponding road. The local council needs to find the shortest route from A to J.

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

During the winter, the council needs to ensure that all ten villages are accessible by road even if there is heavy snow. The council wishes to minimise the total length of road it needs to keep clear.

Use Prim’s algorithm, starting at A, to find a minimum connector for the five villages A, B, C, D and E. You must clearly state the order in which you select the edges of your minimum connector.

Use Kruskal’s algorithm to find a minimum connector for the five villages F, G, H, J and K. You must clearly show the order in which you consider the edges. For each edge, state whether or not you are including it in your minimum connector.

Calculate the total length of road that the council must keep clear of snow to ensure that all ten villages are accessible.