Apply Kruskal's algorithm

3 The following network shows the roads connecting seven villages, \(A , B , C , \ldots , G\). The number on each edge represents the length, in miles, between a pair of villages. \includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-06_978_1108_443_466}

1. Use Kruskal's algorithm to find a minimum spanning tree for the network. (5 marks)
2. State the length of your minimum spanning tree.
3. There are two minimum spanning trees for this network. Draw both of these minimum spanning trees.

3 This diagram shows a network. \includegraphics[max width=\textwidth, alt={}, center]{9aa57bb0-3d88-4858-a348-ff95592fa659-2_693_744_1307_694}

1. Obtain a minimum connector for this network. Draw your minimum connector, state the order in which the arcs were chosen and give their total weight.
2. Use the nearest neighbour method, starting from vertex \(A\), to find a cycle that passes through every vertex. The network represents a cubical die, with vertices labelled \(A\) to \(H\), and faces numbered from 1 to 6 in such a way that the numbers on each pair of opposite faces add up to 7 . When two faces meet in an edge, the sum of the numbers on the two faces is recorded as the weight on that edge.
3. (a) List the vertices of each of the two faces that meet in the edge \(A G\).
   (b) What number is on the face \(A C E G\) ?
   (c) Which face is numbered 3?

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 table below shows the distances, in metres, between six vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , in a network.

1. Draw the weighted network using the vertices given in Diagram 1 in the answer book.
2. 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.
3. Draw the minimum spanning tree on Diagram 2 in the answer book and state its total weight.

3. \begin{figure}[h] \end{figure} The network in Figure 2 shows the distances, in miles, between ten towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { H }\), \(\mathrm { L } , \mathrm { M } , \mathrm { P } , \mathrm { S } , \mathrm { W }\) and Y .

1. 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.
   (3)

   	A	B	C	H	L	M	P	S	W	Y
   A	-	6	18	15	54	29	16	26	29	74
   B	6	-	22	21	60	35	10	32	33	80
   C	18	22	-	17	59	31	12	44	11	80
   H	15	21	17	-	42	14	29	41	28	63
   L	54	60	59	42	-	40	70	28	61	21
   M	29	35	31	14	40	-	43	55	21	61
   P	16	10	12	29	70	43	-	42	23	90
   S	26	32	44	41	28	55	42	-	55	48
   W	29	33	11	28	61	21	23	55	-	82
   Y	74	80	80	63	21	61	90	48	82	-

   The table shows the shortest distances, in miles, between the ten towns.
2. 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.
3. 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.
4. Use your answer to (c) to calculate an initial upper bound for the length of Sharon's route.
5. 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.
6. 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.
7. 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).
8. Interpret this route in terms of the actual towns visited.

2. \begin{figure}[h] \end{figure} Figure 1 represents the distances, in metres, between eight vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H , in a network.

1. 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.
2. Complete Matrix 1 in your answer book, to represent the network.
3. Starting at A, use Prim's algorithm to determine a minimum spanning tree. You must clearly state the order in which you considered the vertices and the order in which you included the arcs.
4. State the weight of the minimum spanning tree.

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. \begin{figure}[h] \end{figure} Figure 1 shows 7 locations \(A , B , C , D , E , F\) and \(G\) which are to be connected by pipelines. The arcs show the possible routes. The number on each arc gives the cost, in thousands of pounds, of laying that particular section.

1. Use Kruskal's algorithm to obtain a minimum spanning tree for the network, giving the order in which you selected the arcs.
   (4)
2. Draw your minimum spanning tree and find the least cost of the pipelines.
   (3)

3. The table shows the lengths, in km, of a network of roads between seven villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G.

1. 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.
2. 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.
3. Draw the minimum spanning tree using the vertices provided in Diagram 2 in the answer book.
4. State the weight of the minimum spanning tree.

5. \begin{figure}[h] \end{figure} The numbers on the \(17 \operatorname { 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.

1. 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.
2. 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.
3. 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 .
4. 1. Write down, in terms of \(m\), the number of arcs in V .
   2. Write down, in terms of \(n\), the number of \(\operatorname { arcs }\) in T .
   3. Hence, write down an inequality, in terms of \(m\) and \(n\), comparing the number of arcs in T and V.

1. The table below shows the lengths, in km , of the roads in a network connecting seven towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G .

1. By adding the arcs from vertex D along with their weights, complete the drawing of the network on Diagram 1 in the answer book.
2. 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.
3. State the weight of the minimum spanning tree.

1 Answer this question on the insert provided. This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight.

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

The table shows the road distances in miles between five places in Great Britain. For example, the distance between Birmingham and Cardiff is 103 miles.

	Ayr
250		Birmingham
350	103		Cardiff
235	104	209		Doncaster
446	157	121	261	Exeter

1. Complete the network in the answer booklet to show this information. The vertices are labelled by using the initial letter of each place. [2]
2. List the ten arcs by increasing order of weight. Apply Kruskal's algorithm to the list. Any entries that are crossed out should still be legible. Draw the resulting minimum spanning tree and give its total weight. [4]

A sixth vertex, F, is added to the network. The distances, in miles, between F and each of the other places are shown in the table below.

	A	B	C	D	E
Distance from F	200	50	150	59	250

1. Use the weight of the minimum spanning tree from part (ii) to find a lower bound for the length of the minimum tour (cycle) that visits every vertex of the extended network with six vertices. [2]
2. Apply the nearest neighbour method, starting from vertex A, to find an upper bound for the length of the minimum tour (cycle) through the six vertices. [2]
3. Use the two least weight arcs through A to form a least weight path of the form \(SAT\), where \(S\) and \(T\) are two of \(\{B, C, D, E, F\}\), and give the weight of this path. Similarly write down a least weight path of the form \(UEV\), where \(U\) and \(V\) are two of \(\{A, B, C, D, F\}\), and give the weight of this path. You should find that the two paths that you have written down use all six vertices. Now find the least weight way in which the two paths can be joined together to form a cycle through all six vertices. Hence write down a tour through the six vertices that has total weight less than the upper bound. Write down the total weight of this tour. [8]

In a factory a network of pipes connects 6 vats, A, B, C, D, E and F. Two separate connectors need to be chosen from the network The table shows the lengths of pipes (metres) connecting the 6 vats.

1. Use Kruskal's algorithm to find a minimum connector. Show the order in which you select pipes, draw your connector and give its total length. [5]
2. Produce a new table excluding the pipes which you selected in part (i). Use the tabular form of Prim's algorithm to find a second minimum connector from this reduced set of pipes. Show your working, draw your connector and give its total length. [7]
3. The factory manager prefers the following pair of connectors: \(\{\)AB, BC, BD, BE, BF\(\}\) and \(\{\)AE, BF, CE, DE, DF\(\}\). Give two possible reasons for this preference. [4]