7.04b Minimum spanning tree: Prim's and Kruskal's algorithms

5 The network shows the lengths, in miles, of roads connecting eleven villages. \includegraphics[max width=\textwidth, alt={}, center]{76bccb26-f2ec-4798-bb6b-89c922f9651a-04_1100_1575_406_251}

1. Use Prim's algorithm, starting from \(A\), to find the minimum spanning tree for the network.
2. State the length of your minimum spanning tree.
3. Draw your minimum spanning tree.
4. A student used Kruskal's algorithm to find the same minimum spanning tree. Find the seventh and eighth edges that the student added to his spanning tree.

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.

7 The diagram shows the locations of some schools. The number on each edge shows the distance, in miles, between pairs of schools. \includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-14_1031_1231_428_392} Sam, an adviser, intends to travel from one school to the next until he has visited all of the schools, before returning to his starting school. The shortest distances for Sam to travel between some of the schools are shown in Table 1 opposite.

1. Complete Table 1.
2. 1. On the completed Table 1, use the nearest neighbour algorithm, starting from \(B\), to find an upper bound for the length of Sam's tour.
   2. Write down Sam's actual route if he were to follow the tour corresponding to the answer in part (b)(i).
   3. Using the nearest neighbour algorithm, starting from each of the other vertices in turn, the following upper bounds for the length of Sam's tour were obtained: 77, 77, 77, 76, 77 and 76. Write down the best upper bound. 7
3. 1. On Table 2 below, showing the order in which you select the edges, use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the schools \(A , B , C\), \(D , F\) and \(G\).
   2. Hence find a lower bound for the length of Sam's minimum tour.
   3. By deleting each of the other vertices in turn, the following lower bounds for the length of a minimum tour were found: \(50,48,52,51,56\) and 64 . Write down the best lower bound.
4. Given that the length of a minimum tour is \(T\) miles, use your answers to parts (b) and (c) to write down the smallest interval within which you know \(T\) must lie.
   (2 marks) \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Table 2}

   	\(\boldsymbol { A }\)	\(\boldsymbol { B }\)	\(\boldsymbol { C }\)	\(\boldsymbol { D }\)	\(\boldsymbol { F }\)	G
   A	-	2	6	4	16	27
   \(\boldsymbol { B }\)	2	-	8	3	15	26
   \(\boldsymbol { C }\)	6	8	-	10	22	32
   \(\boldsymbol { D }\)	4	3	10	-	12	23
   \(\boldsymbol { F }\)	16	15	22	12	-	20
   G	27	26	32	23	20	-

   \end{table}
   \includegraphics[max width=\textwidth, alt={}]{5a414265-6273-41c5-ad5f-f6316bd774d0-17_2486_1714_221_153}

4 The following network shows the lengths, in miles, of roads connecting nine villages, \(A , B , \ldots , I\). A programme of resurfacing some roads is undertaken to ensure that each village can access all other villages along a resurfaced road, while keeping the amount of road to be resurfaced to a minimum. \includegraphics[max width=\textwidth, alt={}, center]{d666b2d9-cb14-4d29-a842-8c87f1b25dbd-08_1008_1043_589_497}

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. Given that Prim's algorithm is used with different start vertices, state the final edge to be added to the minimum spanning tree if:
   1. the start vertex is \(E\);
   2. the start vertex is \(G\).
3. Given that Kruskal's algorithm is used to find the minimum spanning tree, state which edge would be:
   1. the first to be included in the tree;
   2. the last to be included in the tree.

3

1. 1. State the number of edges in a minimum spanning tree of a network with 11 vertices.
   2. State the number of edges in a minimum spanning tree of a network with \(n\) vertices.
2. The following network has 11 vertices, \(A , B , \ldots , K\). The number on each edge represents the distance, in miles, between a pair of vertices. \includegraphics[max width=\textwidth, alt={}, center]{4c5c963b-0183-4dc7-9054-b2c7a3eb8c1b-03_1468_1239_721_404}
   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.

3

1. 1. State the number of edges in a minimum spanning tree for a network with 10 vertices.
   2. State the number of edges in a minimum spanning tree for a network with \(n\) vertices.
2. The following network has 10 vertices: \(A , B , \ldots , J\). The number on each edge represents the distance between a pair of adjacent vertices. \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-06_921_1710_717_150}
   1. Use Kruskal's algorithm to find the minimum spanning tree for the network.
   2. State the length of your minimum spanning tree.
   3. Draw your minimum spanning tree. \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-07_38_118_440_159} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-07_40_118_529_159}

3 A group of eight friends, \(A , B , C , D , E , F , G\) and \(H\), keep in touch by sending text messages. The cost, in pence, of sending a message between each pair of friends is shown in the following table. One of the group wishes to pass on a piece of news to all the other friends, either by a direct text or by the message being passed on from friend to friend, at the minimum total cost.

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 table.
   2. Draw your minimum spanning tree.
   3. Find the minimum total cost.
2. Person \(H\) leaves the group. Find the new minimum total cost.

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\).

3 The following network shows the lengths, in miles, of roads connecting ten villages, \(A , B , C , \ldots , J\). \includegraphics[max width=\textwidth, alt={}, center]{77c4efd4-a905-48f3-a6f7-36b0e47dbc6d-06_899_1458_397_285}

1. 1. Use Kruskal's algorithm, showing the order in which you select the edges, to find a minimum spanning tree for the network.
   2. Find 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. State the final edge that would be added to complete the minimum spanning tree if the starting point were:
   1. \(A\);
   2. \(F\).

4 [Answer this question on the insert provided.]
A competition challenges teams to hike across a moor, visiting each of eight peaks, in the quickest possible time. The teams all start at peak \(A\) and finish at peak \(H\), but other than this the peaks may be visited in any order. The estimated journey times, in hours, between peaks are shown in the table. A dash in the table means that there is no direct route between two peaks.

1. Use Prim's algorithm on the table in the insert to find a minimum spanning tree. Start by crossing out row \(A\). Show which entries in the table are chosen and indicate the order in which the rows are deleted. What can you deduce from this answer about the quickest possible time needed to complete the challenge?
2. On the insert, draw a network to represent the information given in the table above. A team decides to visit each peak exactly once on the hike from peak \(A\) to peak \(H\).
3. Explain why the team cannot use the arc \(A C\).
4. Explain why the team must use the arc \(E F\).
5. There are only two possible routes that the team can use. Find both routes and determine which is the quicker route.

12 JANUARY 2005
Afternoon
1 hour 30 minutes

• This insert should be used to answer Questions 4 and 7.
• Write your name, centre number and candidate number in the spaces provided at the top of this page.
• Write your answers to Questions 4 and 7 in the spaces provided in this insert, and attach it to your answer booklet.

4

1. 	\(A\)	\(B\)	C	D	\(E\)	\(F\)	G	\(H\)
   A	-	4	2	3	-	-	-	-
   \(B\)	4	-	1	-	3	-	-	-
   C	2	1	-	2	-	6	5	-
   \(D\)	3	-	2	-	-	-	4	-
   E	-	3	-	-	-	8	-	7
   \(F\)	-	-	6	-	8	-	-	8
   \(G\)	-	-	5	4	-	-	-	9
   \(H\)	-	-	-	-	7	8	9	-

2. B \(E\) \(C\) F
   • \(H\) \(A\) •
   • \({ } ^ { \text {F } }\)
   H D
   G
3. \(\_\_\_\_\)
4. \(\_\_\_\_\)
5. \(\_\_\_\_\) 7
   1. 1. \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-11_191_1179_269_482} Do not cross out your working values (temporary labels) \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-11_871_1557_612_335} Shortest route from \(A\) to \(E =\) \(\_\_\_\_\) Length = \(\_\_\_\_\) Shortest route from \(A\) to \(J =\) \(\_\_\_\_\) Length = \(\_\_\_\_\)
      2. Length of route \(=\) \(\_\_\_\_\) Vertices visited in order \(\_\_\_\_\)
      3. Explanation \(\_\_\_\_\)
   2. \(\_\_\_\_\) Length = \(\_\_\_\_\)

6 The network represents a railway system. The vertices represent the stations and the arcs represent the tracks. The weights on the arcs represent journey times between stations, in minutes. The sum of all the weights is 105 minutes. \includegraphics[max width=\textwidth, alt={}, center]{8f17020a-14bf-4459-9241-1807b954a629-5_981_1215_468_477} Norah wants to travel around the system visiting every station. She wants to start and end at \(A\) and she wants to complete her journey in the shortest possible time.

1. Apply the nearest neighbour method starting at \(A\) to find two suitable tours and calculate the journey time for each of these tours. Which of these answers gives the better upper bound for Norah's journey time?
2. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting vertex \(G\) and all the arcs that are directly joined to \(G\). Draw a diagram to show the arcs in your tree. Hence calculate a lower bound for Norah's journey time. Norah now decides that she wants to use every section of track in her journey. She still wants to start and end at \(A\) and to complete her journey in the shortest possible time.
3. Calculate the journey time for Norah's new problem. Show your working; quickest times between stations may be found by inspection. State which arcs Norah will have to travel twice and how many times she will pass through station \(D\).

4

1. ↓
   	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)
   A	0	4	5	3	2	5	6
   \(B\)	4	0	1	2	4	7	6
   C	5	1	0	3	4	6	7
   \(D\)	3	2	3	0	2	6	4
   \(E\)	2	4	4	2	0	6	6
   \(F\)	5	7	6	6	6	0	10
   \(G\)	6	6	7	4	6	10	0

   Order in which rows were deleted: \(\_\_\_\_\) \(A\) Minimum spanning tree: A
   • \(D\)
   F
   B E \includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-10_33_28_1302_1101} III
   o D C \includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-10_38_38_1297_1491}
   • G Total weight: \(\_\_\_\_\)
2. \(\_\_\_\_\)
3. \(\_\_\_\_\) Lower bound: \(\_\_\_\_\)
4. Tour: \(\_\_\_\_\) Upper bound: \(\_\_\_\_\)

2 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex.
A simply connected graph is one that is both simple and connected.

1. Explain why there is no simply connected graph with exactly five vertices each of which is connected to exactly three others.
2. A simply connected graph has five vertices \(A , B , C , D\) and \(E\), in which \(A\) has order \(4 , B\) has order 2, \(C\) has order 3, \(D\) has order 3 and \(E\) has order 2. Explain how you know that the graph is semi-Eulerian and write down a semi-Eulerian trail on this graph. A network is formed from the graph in part (ii) by weighting the arcs as given in the table below.

   	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)
   \(A\)	-	5	3	8	2
   \(B\)	5	-	6	-	-
   \(C\)	3	6	-	7	-
   \(D\)	8	-	7	-	9
   \(E\)	2	-	-	9	-

3. Apply Prim's algorithm to the network, showing all your working, starting at vertex \(A\). Draw the resulting tree and state its total weight. A sixth vertex, \(F\), is added to the network using arcs \(C F\) and \(D F\), each of which has weight 6 .
4. Use your answer to part (iii) to write down a lower bound for the length of the minimum tour that visits every vertex of the extended network, finishing where it starts. Apply the nearest neighbour method, starting from vertex \(A\), to find an upper bound for the length of this tour. Explain why the nearest neighbour method fails if it is started from vertex \(F\).

6

1. Greatest number of arcs
   for a network with five vertices \(=\) \(\_\_\_\_\) for a network with \(n\) vertices \(=\) \(\_\_\_\_\)
2. (a) For a network with five vertices
   maximum number of passes \(=\) \(\_\_\_\_\) maximum number of comparisons
   in the first pass \(=\) \(\_\_\_\_\) in the second pass = \(\_\_\_\_\) in the third pass = \(\_\_\_\_\) maximum total number of comparisons = \(\_\_\_\_\) (b) For a network with \(n\) vertices
   maximum total number of comparisons = \(\_\_\_\_\)

3. M1 Vertices in tree	M2 Arcs in tree			M3 Vertices not in tree
   				A B C D E
   DE	D 2 \(E\)			\(A B C\)
   	\includegraphics[max width=\textwidth, alt={}]{e1495f6b-c09f-46a1-a6f8-02354e28887a-11_109_220_1879_786}
   	\includegraphics[max width=\textwidth, alt={}]{e1495f6b-c09f-46a1-a6f8-02354e28887a-11_163_220_2005_786}
   				\multirow{3}{*}{}
   	\includegraphics[max width=\textwidth, alt={}]{e1495f6b-c09f-46a1-a6f8-02354e28887a-11_231_220_2174_786}

   \(\boldsymbol { M 4 }\)
   Sorted list

   \(|\)

   \(D\)	2	\(E\)
   \(A\)	3	\(E\)
   \(A\)	4	\(C\)
   \(C\)	5	\(D\)
   \(B\)	6	\(E\)
   \(B\)	7	\(C\)
   \(A\)	8	\(B\)
   \(C\)	9	\(E\)

4. \(\_\_\_\_\)

2 Five rooms, \(A , B , C , D , E\), in a building need to be connected to a computer network using expensive cabling. Rob wants to find the cheapest way to connect the rooms by finding a minimum spanning tree for the cable lengths. The length of cable, in metres, needed to connect each pair of rooms is given in the table below.

1. Apply Prim's algorithm in matrix (table) form, starting at vertex \(A\) and showing all your working. Write down the order in which arcs were added to the tree. Draw the resulting tree and state the length of cable needed. A sixth room, \(F\), is added to the computer network. The distances from \(F\) to each of the other rooms are \(A F = 32 , B F = 29 , C F = 31 , D F = 35 , E F = 30\).
2. Use your answer to part (i) to write down a lower bound for the length of the minimum tour that visits every vertex of the extended network, finishing where it starts. Apply the nearest neighbour method, starting from vertex \(A\), to find an upper bound for the length of this tour.

4 Pam has seven employees. When it snows they all need to be contacted by telephone.
The table shows the expected time, in minutes, that it will take Pam and her employees to contact each other.

1. Use the nearest neighbour method, starting from Pam, to find a cycle through all the employees and Pam. If there is a choice of names choose the one that occurs first alphabetically. Calculate the total weight of this cycle.
2. Apply Prim's algorithm to the copy of the table in the answer book, starting by crossing out the row for Pam and looking down the column for Pam. List the arcs in the order in which they were chosen. Draw the resulting minimum spanning tree and calculate its total weight.
3. Find a lower bound for the minimum weight cycle through Pam and her seven employees by initially removing Gita from the minimum spanning tree. Pam realises that it takes less time if she splits the employees into teams.
4. Use the minimum spanning tree to suggest how to split the employees into two teams, so that Pam contacts the two team leaders and they each contact the members of their team. Using this solution, find the minimum elapsed time by which all the employees can be contacted.

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?

3 The network below represents a system of roads. The vertices represent villages and the arcs represent the roads between the villages. The weights on the arcs represent travel times by bicycle between villages, in minutes. \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-02_531_1113_1304_516} Alf wants to cycle from his home at \(A\) to visit each of the other villages and return to \(A\) in the shortest possible time.

1. Which standard network problem does Alf need to solve to find the quickest tour through all the villages?
2. Apply the nearest neighbour method starting at \(A\) to find a tour through all the villages that starts and ends at \(A\). Calculate the journey time for this tour. What can you deduce from this about the shortest possible time for Alf's tour?
3. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting vertex \(A\) and all the arcs that are directly joined to \(A\). Start building your tree at vertex \(B\). (You do not need to represent the network as a matrix.) Give the order in which vertices are added to your tree and draw a diagram to show the arcs in your tree. Hence calculate a lower bound for Alf's journey time.
4. Write down a route for Alf that would take him 125 minutes.

4 A simplified map of an area of moorland is shown below. The vertices represent farmhouses and the arcs represent the paths between the farmhouses. The weights on the arcs show distances in km. \includegraphics[max width=\textwidth, alt={}, center]{dbefedb2-b398-45e8-92eb-eb510ff16def-4_618_1420_356_319} Ted wants to visit each farmhouse and then return to his starting point.

1. In your answer book the arcs have been sorted into increasing order of weight. Use Kruskal's algorithm to find a minimum spanning tree for the network, and give its total weight. Hence find a route visiting each farmhouse, and returning to the starting point, which has length 82 km .
2. Give the weight of the minimum spanning tree for the six vertices \(A , B , C , E , F , G\). Hence find a route visiting each of the seven farmhouses once, and returning to the starting point, which has length 81 km .
3. Show that the nearest neighbour method fails to produce a cycle through every vertex when started from \(A\) but that it succeeds when started from \(B\). Adapt this cycle to find a complete cycle of total weight less than 70 , and find the total length of the shorter cycle.

5 This question uses the same network as question 4.
The network below represents a treasure trail. The arcs represent paths and the weights show distances in units of 100 metres. \includegraphics[max width=\textwidth, alt={}, center]{cdad4fbe-4b94-4c8f-bb42-24d20eeaab4d-5_680_1154_431_459} Gus wants to hunt for the treasure. He assumes that the treasure is located at a vertex, but he does not know which one.

1. (a) Use the nearest neighbour method starting at \(G\) to find an upper bound for the length of the shortest closed route through every vertex.
   (b) Gus follows this route, but starting at \(A\). Write down his route, starting and ending at \(A\).
2. Use Prim's algorithm on the network, starting at \(A\), to find a minimum spanning tree. You should write down the arcs in the order they are included, draw the tree and give its total weight (in units of 100 metres).
3. (a) Vertex \(H\) and all arcs joined to \(H\) are removed from the original network. Write down the weight of the minimum spanning tree for vertices \(A , B , C , D , E , F\) and \(G\) in the resulting reduced network.
   (b) Use this minimum spanning tree for the reduced network to find a lower bound for the length of the shortest closed route through every vertex in the original network.
4. Find a route that passes through every vertex, starting and ending at \(A\), that is longer than the lower bound from part (iii)(b) but shorter than the upper bound from part (i)(a). Give the length of your route, in metres. Assume that Gus travels along paths at a rate of \(x\) minutes for every 100 metres and that he spends \(y\) minutes at each vertex hunting for the treasure. Gus starts by hunting for the treasure at \(A\). He then follows the route from part (iv), starting and finishing at \(A\) and hunting for the treasure at each vertex. Unknown to Gus, the treasure is found before he gets to it, so he has to search at every vertex. Gus can take at most 2 hours from when he starts searching at \(A\) to when he arrives back at \(A\).
5. Use this information to write down a constraint on \(x\) and \(y\). The treasure was at \(H\) and was found 40 minutes after Gus started. This means that Gus takes more than 40 minutes to get to \(H\).
6. Use this information to write down a second constraint on \(x\) and \(y\).

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.

7 A tour guide wants to find a route around eight places of interest: Queen Elizabeth Olympic Park ( \(Q\) ), Royal Albert Hall ( \(R\) ), Statue of Eros ( \(S\) ), Tower Bridge ( \(T\) ), Westminster Abbey ( \(W\) ), St Paul's Cathedral ( \(X\) ), York House ( \(Y\) ) and Museum of Zoology ( \(Z\) ). The table below shows the travel times, in minutes, from each of the eight places to each of the other places.

1. Use the nearest neighbour method to find an upper bound for the minimum time to travel to each of the eight places, starting and finishing at \(Y\). Write down the route and give the time in minutes.
2. The Answer Book lists the arcs by increasing order of weight (reading across the rows). Apply Kruskal's algorithm to this list to find the minimum spanning tree for all eight places. Draw your tree and give its total weight.
3. (a) Vertex \(Q\) and all arcs joined to \(Q\) are temporarily removed. Use your answer to part (ii) to write down the weight of the minimum spanning tree for the seven vertices \(R , S , T , W , X , Y\) and \(Z\).
   (b) Use your answer to part (iii)(a) to find a lower bound for the minimum time to travel to each of the eight places of interest, starting and finishing at \(Y\). The tour guide allows for a 5 -minute stop at each of \(S\) and \(Y\), a 10 -minute stop at \(T\) and a 30 -minute stop at each of \(Q , R , W , X\) and \(Z\). The tour guide wants to find a route, starting and ending at \(Y\), in which the tour (including the stops) can be completed in five hours (300 minutes).
4. Use the nearest neighbour method, starting at \(Q\), to find a closed route through each vertex. Hence find a route for the tour, showing that it can be completed in time.

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.