Minimum Spanning Trees

1 The following network shows the lengths, in miles, of roads connecting 11 villages, \(A , B , \ldots , K\). \includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-2_915_1303_591_365}

1. Starting from \(G\) and showing your working at each stage, use Prim's algorithm to find a minimum spanning tree for the network.
2. State the length of your minimum spanning tree.
3. Draw your minimum spanning tree.

3 The following network shows the lengths, in miles, of roads connecting nine villages, \(A , B , \ldots , I\). \includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-06_810_501_445_388} \includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-06_812_499_443_1135}

1. 1. Use Prim's algorithm starting from \(A\), showing the order in which you select the edges, to find a minimum spanning tree for the network.
   2. State the length of your minimum spanning tree.
   3. Draw your minimum spanning tree.
2. Prim's algorithm from different starting points produces the same minimum spanning tree for this network. State the final edge that would complete the minimum spanning tree using Prim's algorithm:
   1. starting from \(D\);
   2. starting from \(H\).

7 A company operates a steam railway between six stations. The minimum cost (in euros) of travelling between pairs of stations is shown in the table below.

1. On Figure 1 below, use Prim's algorithm, starting from \(P\), to find a minimum spanning tree for the graph connecting \(P , Q , R , S , T\) and \(U\). State clearly the order in which you select the vertices and draw your minimum spanning tree. \section*{Question 7 continues on page 20} \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1}

   	\(\boldsymbol { P }\)	\(\boldsymbol { Q }\)	\(\boldsymbol { R }\)	\(\boldsymbol { S }\)	\(\boldsymbol { T }\)	\(\boldsymbol { U }\)
   \(\boldsymbol { P }\)	-	14	7	11	6	12
   \(\boldsymbol { Q }\)	14	-	8	10	9	10
   \(\boldsymbol { R }\)	7	8	-	12	13	15
   \(\boldsymbol { S }\)	11	10	12	-	5	11
   \(\boldsymbol { T }\)	6	9	13	5	-	10
   \(\boldsymbol { U }\)	12	10	15	11	10	-

   \end{table}
2. Another station, \(V\), is opened. The minimum costs (in euros) of travelling to and from \(V\) to each of the other stations are added to the table in part (a), as shown in Figure 2(i) below. Further copies of this table are shown in Figure 2(ii). Arjen is on holiday and he plans to visit each station. He intends to board a train at \(V\) and visit all the other stations, once only, before returning to \(V\).
   1. By first removing \(V\), obtain a lower bound for the minimum travelling cost of Arjen's tour. (You may use Figure 2(i) for your working.)
   2. Use the nearest neighbour algorithm twice, starting each time from \(V\), to find two different upper bounds for the minimum cost of Arjen's tour. State, with a reason, which of your two answers gives the better upper bound. (You may use Figure 2(ii) for your working.)
   3. Hence find an optimal tour of the seven stations. Explain how you know that it is optimal. Answer space for question 7(b) \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{Figure 2(ii)}

      	\(\boldsymbol { P }\)	\(Q\)	\(\boldsymbol { R }\)	\(\boldsymbol { S }\)	\(T\)	\(\boldsymbol { U }\)	\(V\)
      \(\boldsymbol { P }\)	-	14	7	11	6	12	15
      \(Q\)	14	-	8	10	9	10	18
      \(\boldsymbol { R }\)	7	8	-	12	13	15	14
      \(\boldsymbol { S }\)	11	10	12	-	5	11	14
      \(T\)	6	9	13	5	-	10	17
      \(\boldsymbol { U }\)	12	10	15	11	10	-	12
      \(V\)	15	18	14	14	17	12	-

      \end{table}

13
16
5
8
2
15
12
10 6. \section*{Diagram 1}

2. The table shows the distances, in metres, between six vertices, \(\mathbf { A } , \mathbf { B } , \mathbf { C } , \mathbf { D } , \mathbf { E }\) and \(\mathbf { F }\), in a network.

1. Draw the weighted network using the vertices given in Diagram 1 in the answer booklet.
2. Use Kruskal's algorithm to find a minimum spanning tree. You should list the edges in the order that you consider them and state whether you are adding them to your minimum spanning tree.
3. Draw your tree on Diagram 2 in the answer booklet and find its total weight.

2

1. A minimum spanning tree is constructed for a network. A vertex and all arcs joined to it are then deleted from the network. Under what circumstances will the remaining arcs of the minimum spanning tree form a minimum spanning tree for the reduced network? Joseph wants to use Kruskal's algorithm to find the minimum spanning tree for a network. He has sorted the arcs in the network by increasing order of weight. $$\begin{array} { l l l l l l l } B D = 5 & F G = 5 & D E = 6 & D F = 7 & E H = 7 & B C = 8 & D G = 8 \\ G H = 8 & A D = 9 & C D = 9 & E G = 9 & A B = 10 & A E = 10 & C F = 10 \end{array}$$
2. Use Kruskal's algorithm on the list in your answer book, crossing out arcs that are not used. Draw your minimum spanning tree and give its total weight.
3. By considering the minimum spanning tree for the reduced network formed when vertex \(A\) and all arcs joined to \(A\) are deleted, find a lower bound for the shortest closed cycle through every vertex on the original network. The table shows the arc weights for the same network.

   	A	\(B\)	C	D	E	\(F\)	G	\(H\)
   A	-	10	-	9	10	-	-	-
   B	10	-	8	5	-	-	-	-
   C	-	8	-	9	-	10	-	-
   D	9	5	9	-	6	7	8	-
   E	10	-	-	6	-	一	9	7
   F	-	-	10	7	-	-	5	-
   G	-	-	-	8	9	5	-	8
   H	-	-	-	-	7	-	8	-

4. Apply the nearest neighbour method, starting at \(A\), to find a cycle through every vertex. Hence write down an upper bound for the shortest closed cycle through every vertex on the network.

1 The arc weights for a network on a complete graph with six vertices are given in the following table. Apply Prim's algorithm to the table in the Printed Answer Book. Start by crossing out the row for \(A\) and choosing an entry from the column for \(A\). Write down the arcs used in the order that they are chosen. Draw the resulting minimum spanning tree and give its total weight.

3 Six remote villages are linked by a set of roads. Two villages are connected directly if there is a road between them which does not pass through another village. The table gives the lengths in miles of all direct connections.

1. Why might it be thought surprising that the direct distance between A and D is as long as 12 miles? Give a possible reason why the distance is longer than might have been expected.
2. Use the tabular form of Prim's algorithm, starting at A , to find a minimum connector for these villages. Draw your connector and give its total length.

6 The matrix gives the lengths of the arcs of a network.

1. Using the copy of the matrix in your answer book, apply the tabular form of Prim's algorithm to find a minimum connector for the network. Start by choosing vertex A and show the order in which you include vertices.
   List the arcs in your connector and give its total length. Serena takes a different approach to find a minimum connector. She first uses Dijkstra's algorithm to find shortest paths from A to each of the other vertices. She then uses the arcs in those paths to construct a connector.
2. Draw the network using the vertices printed in your answer book.
3. Apply Serena's method to produce a connector. List the arcs in the connector and give its total length. Serena adapts her method by starting from each vertex in turn, producing six connectors, from which she chooses the best.
4. Serena's approach will not find the minimum connector in all networks, but it is an algorithm. What is its algorithmic complexity? Justify your answer.

1. \begin{figure}[h] \end{figure}

1. Define the terms
   1. tree,
   2. minimum spanning tree.
2. Use Prim's algorithm, starting at A , to find a minimum spanning tree for the network shown in Figure 1. You must clearly state the order in which you select the arcs of the tree.
3. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the tree.

3

1. 1. State the number of edges in a minimum spanning tree of a network with 10 vertices.
   2. State the number of edges in a minimum spanning tree of a network with \(n\) vertices.
2. The following network has 10 vertices: \(A , B , \ldots , J\). The numbers on each edge represent the distances, in miles, between pairs of vertices. \includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-03_1294_1118_785_445}
   1. Use Kruskal's algorithm to find the minimum spanning tree for the network.
   2. State the length of your spanning tree.
   3. Draw your spanning tree.

1. Describe the differences between Prim's algorithm and Kruskal's algorithm for finding a minimum connector of a network.

\includegraphics{figure_2}

1. Listing the arcs in the order that you select them, find a minimum connector for the network in Fig. 2, using
   1. Prim's algorithm,
   2. Kruskal's algorithm.
   [4]

2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \section*{Question 2 continued} \section*{D} \begin{verbatim} B $$\mathrm { A }$$ \end{verbatim} \begin{verbatim} \(\stackrel { \bullet } { \text { E } }\) \end{verbatim} \section*{Diagram 1} Weight of the minimum spanning tree: \(\_\_\_\_\)

The network shows 10 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges. \includegraphics{figure_3}

1. Use Kruskal's algorithm, showing the order in which you select the edges, to find a minimum spanning tree for the 10 towns. [6 marks]
2. State the length of your minimum spanning tree. [1 mark]
3. Draw your minimum spanning tree. [3 marks]
4. If Prim's algorithm, starting at \(B\), had been used to find the minimum spanning tree, state which edge would have been the final edge to complete the minimum spanning tree. [1 mark]

3 A theme park has 11 rides, \(A , B , \ldots K\). The network shows the distances, in metres, between pairs of rides. The rides are to be connected by cabling so that information can be collated. The manager of the theme park wishes to use the minimum amount of cabling. \includegraphics[max width=\textwidth, alt={}, center]{a1290c22-f28d-42aa-89d5-10d60ca4741c-03_988_1575_488_248}

1. Use Prim's algorithm, starting from \(A\), to find the minimum spanning tree for the network.
2. State the length of cabling required.
3. Draw your minimum spanning tree.
4. The manager decides that the edge \(A E\) must be included. Find the extra length of cabling now required to give the smallest spanning tree that includes \(A E\).

5. \section*{Question 5 continued} \section*{D} A

• \({ } ^ { \text {B } }\)
• F \(\stackrel { \bullet } { \mathrm { H } }\)

Diagram 1

The following network shows the lengths, in miles, of roads connecting nine villages, \(A\), \(B\), ..., \(I\). \includegraphics{figure_3}

1. 1. Use Prim's algorithm starting from \(E\), showing the order in which you select the edges, to find a minimum spanning tree for the network. [4]
   2. State the length of your minimum spanning tree. [1]
   3. Draw your minimum spanning tree. [2]
2. On a particular day, village \(B\) is cut off, so its connecting roads cannot be used. Find the length of a minimum spanning tree for the remaining eight villages. [2]

4. \begin{figure}[h] \end{figure}

1. State two differences between Kruskal's algorithm and Prim's algorithm for finding a minimum spanning tree.
   (2)
2. Listing the arcs in the order that you consider them, find a minimum spanning tree for the network in Figure 4, using
   1. Prim's algorithm,
   2. Kruskal's algorithm.
      (6)

3 [Figure 1, printed on the insert, is provided for use in part (b) of this question.]
The diagram shows a network of roads. The number on each edge is the length, in kilometres, of the road. \includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-03_716_1303_559_388}

1. 1. Use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the network.
   2. State the length of your minimum spanning tree.
2. 1. Use Dijkstra's algorithm on Figure 1 to find the shortest distance from \(A\) to \(J\).
   2. A new road, of length \(x \mathrm {~km}\), is built connecting \(I\) to \(J\). The minimum distance from \(A\) to \(J\) is reduced by using this new road. Find, and solve, an inequality for \(x\).

7 A construction company has built eight wind turbines on a moorland site. The network below shows nodes which represent the site entrance, \(E\), and the wind turbine positions, \(S , T , \ldots , Z\) \includegraphics[max width=\textwidth, alt={}, center]{372edcfa-c3cd-4c83-89e9-2bb5fd9825f1-12_924_1294_479_356} Each arc represents an access track with its length given in metres.
These 17 tracks were created in order to build the wind turbines. Eight of the tracks are to be retained so that each turbine can be accessed for maintenance, directly or indirectly, from the site entrance. The other nine tracks will be removed. 7

1. 1. To save money the construction company wants to maximise the total length of the eight tracks to be retained. Determine which tracks the construction company should retain.
      7
      1. (ii) Find the total length of the eight tracks that are to be retained. 7
   2. The total length of the 17 tracks is 14.6 km
      The cost of removing all 17 tracks would be \(\pounds 87,600\) Using your answer to part (a)(ii), calculate an estimate for the cost of removing the nine tracks that will not be retained.
      [0pt] [2 marks]
      7
   3. Comment on why the modelling used in part (b) may not give an accurate estimate for the cost of removing the nine tracks.

6 An animal sanctuary has a rainwater collection site. The manager of the sanctuary is installing a pipe system to connect the rainwater collection site to five other sites in the sanctuary. Each site does not need to be connected directly to the rainwater collection site. There are nine possible routes between the sites that are suitable for water pipes. The distances, in metres, of the nine possible routes are given in the table below. Water pipe costs 60 pence per metre. Find the minimum cost of connecting all the sites to the rainwater collection site. Fully justify your answer. \(7 \quad\) A linear programming problem has the constraints $$\begin{aligned} 1 \leq x & \leq 6 \\ 1 \leq y & \leq 6 \\ y & \geq x \\ x + y & \leq 11 \end{aligned}$$

2 This question is about a simply connected network with at least three arcs joining 4 nodes. The weights on the arcs are all different and any direct paths always have a smaller weight than the total weight of any indirect paths between two vertices.

1. Kruskal's algorithm is used to construct a minimum connector. Explain why the arcs with the smallest and second smallest weights will always be included in this minimum connector.
2. Draw a diagram to show that the arc with the third smallest weight need not always be included in a minimum connector.

1 The following network shows the lengths, in miles, of roads connecting nine villages. \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-02_856_1251_568_374}

1. Use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the network.
2. Find the length of your minimum spanning tree.
3. Draw your minimum spanning tree.
4. State the number of other spanning trees that are of the same length as your answer in part (a).

6 A connected graph \(G\) has five vertices and has eight edges with lengths \(8,10,10,11,13,17\), 17 and 18.

1. Find the minimum length of a minimum spanning tree for \(G\).
2. Find the maximum length of a minimum spanning tree for \(G\).
3. Draw a sketch to show a possible graph \(G\) when the length of the minimum spanning tree is 53 .