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

1. 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.

1. Use Prim's algorithm to find a minimum spanning tree for this network. Make your order of arc selection clear.
2. Use your answer to part (a) to determine an initial upper bound for the length of Agent Goodie's route.
3. Show that there are two nearest neighbour routes which start from A . State these routes and their lengths.
4. State the better upper bound from your answers to (b) and (c).
5. Starting by deleting B, and all of its arcs, find a lower bound for the length of Agent Goodie's route.
6. Consider your answers to (d) and (e) and hence state an optimal route.

3. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

1. State the value of the initial flow.
2. State the capacity of cut \(\mathrm { C } _ { 1 }\). The labelling procedure has been used and the result drawn on Diagram 1 in the answer book.
3. Use Diagram 1 to find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
   (4)
4. Draw a maximum flow pattern on Diagram 2 in your answer book.
   (2)
5. Prove that the flow shown in (d) is maximal.
   (2)

5. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed, network. The capacity of each arc is shown on that arc and the numbers in circles represent an initial flow from S to T . Two cuts, \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\) are shown on Figure 1.

1. Find the capacity of each of the two cuts and the value of the initial flow.
   (3)
2. Complete the initialisation of the labelling procedure on Figure 1 in the answer book, by entering values along \(\mathrm { SB } , \mathrm { AB } , \mathrm { BE }\) and BG .
   (2)
3. Hence use the labelling procedure to find a maximum flow of 85 through the network. You must list each flow-augmenting path you use, together with its flow.
   (5)
4. Show your flow pattern on Figure 2.
   (2)
5. Prove that your flow is maximal.
   (2)

1. \begin{figure}[h] \end{figure} Figure 1 shows a directed, capacitated network where the number on each arc is its capacity. A possible flow is shown from \(S\) to \(T\) and the value in brackets on each arc is the flow in that arc.

1. Find the values of \(x , y\), and \(z\).
   (3)
2. Find, by inspection, the maximal flow from \(S\) to \(T\) and verify that it is maximal.
   (2)

3 Five towns, 1, 2, 3, 4 and 5, are connected by direct routes as shown. The arc weights represent distances. \includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-4_632_540_312_744}

1. The printed answer book shows the initial tables and the results of iterations \(1,2,3\) and 5 when Floyd's algorithm is applied to the network.
   (A) Complete the two tables for iteration 4.
   (B) Use the final route table to give the shortest route from vertex 5 to vertex 2.
   (C) Use the final distance table to produce a complete network with weights representing the shortest distances between vertices.
2. Use the nearest neighbour algorithm, starting at vertex \(\mathbf { 4 }\), to produce a Hamilton cycle in the complete network. Give the length of your cycle.
3. Interpret your Hamilton cycle from part (ii) in terms of towns actually visited.
4. Find an improved Hamilton cycle by applying the nearest neighbour algorithm starting from one of the other vertices.
5. Using the complete network of shortest distances (excluding loops), find a lower bound for the solution to the Travelling Salesperson Problem by deleting vertex 4 and its arcs, and by finding the length of a minimum connector for the remainder. (You may find the minimum connector by inspection.)
6. Given that the sum of the road lengths in the original network is 43 , give a walk of minimum length which traverses every arc on the original network at least once, and which returns to the start. Show your methodology. Give the length of your walk.

\(\mathbf { 5 }\) & 4 & - & - & 2
\hline

1. Draw the complete 5-node network of shortest times. (You are not required to use an algorithm to find the shortest times.)
2. Write down the final time matrix and the final route matrix for the complete 5 -node network. (You do not need to apply Floyd's algorithm.)
3. (A) Apply the nearest neighbour algorithm to the complete 5-node network of shortest times, starting at node 1. Give the time for the cycle you produce.
   (B) Starting at node 3, a possible cycle in the complete 5-node network of shortest times is \(\mathbf { 3 2 1 5 4 3 . }\) Give the actual cycle to which this corresponds in the incomplete 5-node network of journey times.
4. By deleting node 5 and its arcs from the complete 5 -node network of shortest times, and then using Kruskal's algorithm, produce a lower bound for the solution to the associated practical travelling salesperson problem. Show clearly your use of Kruskal's algorithm.
5. In the incomplete 5-node network of journey times, find a quickest route starting at node \(\mathbf { 5 }\) and using each of the 7 arcs at least once. Give the time of your route. 4 Helen has a meeting to go to in London. She has to travel from her home in G on the south coast to KC in London. She can drive from G to the west to A to catch a train, or she can drive to the east to W to catch a train on a different line. From both A and W she can travel to mainline terminuses V or LB in London. She will then travel by tube either from V to KC , or from LB to KC . The times for the various steps of her journey are shown in the tables. Both train services and tube services are subject to occasional delays, and these are modelled in the tables.

   Driving times	to A	to W
   From G	20 min	15 min

   \multirow{2}{*}{Train journey}	To V			To LB
   	normal time	probability of delay	delay	normal time	probability of delay	delay
   From A	1 hr 40 min	0.05	10 min	1 hr 45 min	0.05	10 min
   From W	1 hr 30 min	0.10	20 min	1 hr 35 min	0.10	20 min

   \multirow{2}{*}{ Tube journey }	To KC
   \cline { 2 - 4 }	normal time	probability of delay	delay
   From V	7 min	0.20	2 min
   From LB	9 min	0.10	2 min

   Helen wants to choose the route which will give the shortest expected journey time.
6. Draw a decision tree to model Helen's decisions and the possible outcomes.
7. Calculate Helen's shortest expected journey time and give the route which corresponds to that shortest expected journey time. As she gets into her car, Helen hears a travel bulletin on the radio warning of a broken escalator at V. This means that routes through V will take Helen 10 minutes longer.
8. Find the value of the radio information, explaining your calculation.
9. Why might the shortest expected journey time not be the best criterion for choosing a route for Helen?

1. Perform the fourth iteration of the algorithm, and show that there is no change to either matrix in the final iteration.
2. Show how to use the matrices to give the shortest distance and the shortest route from vertex \(\mathbf { 1 }\) to vertex 2.
3. Draw the complete network of shortest distances.
4. Starting at vertex 1, apply the nearest neighbour algorithm to the complete network of shortest distances to find a Hamilton cycle. Give the length of your cycle and interpret it in the original network.
5. By temporarily deleting vertex \(\mathbf { 1 }\) and its connecting arcs from the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson's Problem in that network. Say what this implies in the original network.

4. This question should be answered on the sheet provided. A travelling salesman problem relates to the network represented by the following table of distances in kilometres. You may assume that the network satisfies the triangle inequality. Showing your method clearly, use

1. the nearest neighbour algorithm, beginning with \(A\),
2. Prim's algorithm with \(H\) deleted,
   to show that the minimum distance travelled, \(d \mathrm {~km}\), satisfies the inequality \(357 \leq d \leq 371\).
   (11 marks)

6. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} The network in Figure 3 shows the distances, in miles, between a newspaper distributor based at area \(A\), and five areas, \(B , C , D , E\), and \(F\), to which the distributor must deliver newspapers. Each morning a delivery van has to set out from \(A\) and visit each of these areas before again returning to \(A\), and the driver wishes to keep the total mileage to a minimum.

1. Draw a complete network showing the shortest distances between the six areas.
   (3 marks)
2. Obtain a minimum spanning tree for the complete network and hence find an upper bound for the length of the driver's route.
   (5 marks)
3. Improve this upper bound to find an upper bound of less than 55 miles.
4. By deleting \(A\), find a lower bound for the total length of the route.

7. This question should be answered on the sheet provided. A tinned food producer delivers goods to six supermarket warehouses, \(B , C , D , E , F\) and \(G\), from its base, \(A\). The distances, in kilometres, between each location are given in the table below. \section*{Please hand this sheet in for marking}

6. This question should be answered on the sheet provided. A furniture company in Leeds is considering opening outlets in six other cities.
The table below shows the distances, in miles, between all seven cities.

1. Starting with Leeds, obtain and draw a minimum spanning tree for this network of cities showing your method clearly.
   (4 marks)
   A representative of the company is to visit each of the areas being considered. He wishes to plan a journey of minimum length starting and ending in Leeds and visiting each of the other cities in the table once. Assuming that the network satisfies the triangle inequality,
2. find an initial upper bound for the length of his journey,
3. improve this upper bound to find an upper bound of less than 575 miles.
4. By deleting Leeds, find a lower bound for his journey.

6. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} A band is going on tour to play gigs in six towns, including their home town, \(A\). The network in Figure 1 shows the distances, in miles, between the various towns. The band must begin and end their tour at \(A\) and visit each of the other towns once, and they wish to keep the total distance travelled as small as possible.

1. By inspection, draw a complete network showing the shortest distances between the towns.
2. Use your complete network and the nearest neighbour algorithm, starting at \(A\), to find an upper bound for the total distance travelled.
3. 1. Use your complete network to obtain and draw a minimum spanning tree and hence obtain another upper bound for the total distance travelled.
   2. Improve this upper bound using two shortcuts to find an upper bound below 225 miles.
4. By deleting \(A\), find a lower bound for the total distance travelled.
5. State an interval of as small a width as possible within which \(d\), the minimum distance travelled, in miles, must lie. \section*{Please hand this sheet in for marking}

   Stage	Previous tournament	Current tournament
   \multirow[t]{3}{*}{1}	G	J K L
   	\(H\)	J K L
   	I	J K L
   \multirow[t]{3}{*}{2}	D	G H I
   	\(E\)	G H I
   	\(F\)	G H I
   \multirow[t]{3}{*}{3}	A	D E F
   	\(B\)	D E F
   	C	D E F
   4	None	A B C

   \section*{Please hand this sheet in for marking}
   1. \includegraphics[max width=\textwidth, alt={}, center]{073926c5-03cc-41d4-82bf-315740ead663-8_684_992_461_427}
   2. \section*{Sheet for answering question 6 (cont.)}
   3. 2. \(\_\_\_\_\)
   5. \(\_\_\_\_\)

4 The complete bipartite graph \(K _ { 3,4 }\) connects the vertices \(\{ 2,4,6 \}\) to the vertices \(\{ 1,3,5,7 \}\).

1. How many arcs does the graph \(K _ { 3,4 }\) have?
2. Deduce how many different paths are there that pass through each of the vertices once and once only. The direction of travel of the path does not matter. The arcs are weighted with the product of the numbers at the vertices that they join.
3. (a) Use an appropriate algorithm to find a minimum spanning tree for this network.
   (b) Give the weight of the minimum spanning tree.

4 The table shows the activities involved in a project, their durations in hours and their immediate predecessors. The activities can be represented as an activity network.

1. Use standard algorithms to find the activities that form
   You must show working to demonstrate the use of the algorithms. Only one of the paths from part (a) has a practical interpretation.
2. What is the practical interpretation of the total weight of that path? The duration of activity E can be changed. No other durations change.
3. What is the smallest increase to the duration of E that will make activity E become part of a longest path through the network?

6 Eight footpaths connect six villages. The lengths of these footpaths, in km , are given in the table.

1. The shortest route from B to C using these footpaths has length 10 km . Without using an algorithm, write down this shortest route from B to C.
2. Use an appropriate algorithm to find the shortest route from A to F .
3. Write down all the pairs of villages for which the shortest route between them uses at least one footpath that is not in the minimum spanning tree for the six villages.

2 A network is shown below. \includegraphics[max width=\textwidth, alt={}, center]{c9fb5dad-1069-46cd-b167-80b77016f03c-2_533_869_1160_244}

1. Use an appropriate algorithm to find the least weight (shortest) path from A to D.
2. Use Kruskal's algorithm to find a minimum spanning tree for the network.

5 A garden centre sells mixed packs of flower bulbs.
Each pack contains bulbs which produce flowers of two different colours. The cost, in \(\pounds\), of a pack of each colour combination is shown in the table below.

1. Represent the information in the table as a network in which the vertices are the colours and the arcs are the packs available, weighted using the costs.
2. Construct a minimum spanning tree for the network. Taylor wants to buy at most four different packs of bulbs and to ensure that the packs include bulbs capable of producing all four flower colours. Taylor wants to minimise the total cost of these packs.
3. Determine whether or not buying the packs represented by the solution to part (b) solves Taylor's problem.
4. Represent Taylor's problem as an LP formulation, in which the variables are the number of packs of each type.

3 \includegraphics[max width=\textwidth, alt={}, center]{c2deec7d-0617-4eb0-a47e-5b42ba55b753-4_399_1331_255_367}

1. By listing the vertices passed through, in the order they are used, give an example for the graph above of:
   1. a walk from A to H that is not a trail,
   2. a trail from A to H that is not a path,
   3. a path from A to H that is not a cycle. The arcs are weighted to form a network. The arc weights are shown in the table, apart from the weight of arc AG. The arcs model a system of roads and the weights represent distances in km.

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

      The road modelled by arc AG is temporarily closed.
2. Use the matrix form of Prim's algorithm to find a minimum spanning tree, of total weight 30 km , that does not include arc AG. The road modelled by arc AG is now reopened.
3. 1. For what set of values of \(x\) could AG be included in a minimum spanning tree for the full network?
   2. Which arc from the minimum spanning tree in part (b) is not used when arc AG is included?

7 A complete graph on five vertices is weighted to form a network, as given in the weighted matrix below.

1. Apply Prim's algorithm to the copy of this weighted matrix in the Printed Answer Booklet to construct a minimum spanning tree for the five vertices.
   Draw your minimum spanning tree, stating the order in which you built the tree and giving its total weight.
2. (a) Using only the arcs in the minimum spanning tree, which vertex should be chosen to find the smallest total of the weights of the paths from that vertex to each of the other vertices?
   (b) State the minimum total for this vertex.
3. Show that the total number of comparisons needed to find a minimum spanning tree for a \(5 \times 5\) matrix is 16 .
4. If a computer takes 4 seconds to find a minimum spanning tree for a network with 100 vertices, how long would it take to find a minimum spanning tree for a network with 500 vertices?

5

1. Write down a way in which the nearest neighbour method can fail to solve the problem of finding a least weight cycle through all the vertices of a network.
2. Explain why, when trying to find a least weight cycle through all the vertices of a network, an ad hoc method may be preferable to an algorithmic approach. The distance matrix below represents a network connecting six viewpoints \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F . The distance matrix shows the direct distances between each pair of viewpoints where a direct route exists.
   The distances are measured in km.
   A blank shows that there is no direct route between the two viewpoints.

   	A	B	C	D	E	F
   A		6		4
   B	6		5	2	9
   C		5		15	7	6
   D	4	2	15		5
   E		9	7	5
   F			6

3. Draw the network on the vertices given in the Printed Answer Booklet.
4. Apply the nearest neighbour method, starting from A. A hiker wants to travel between the six viewpoints, starting and finishing at A.
   The hiker must visit every viewpoint at least once, but may visit a viewpoint more than once.
5. Show that the hiker does not need to travel as far as 50 km .
6. Use an appropriate algorithm to find the shortest distance from F to each of the other viewpoints.
7. Complete the table in the Printed Answer Book to show the shortest distance between each pair of viewpoints.
8. Use your answer to part (g) to find a lower bound for the distance the hiker must travel by initially deleting vertex A.

5 The manager of a farm shop wants to pave routes on the farm so that, after visiting the shop, customers can visit the animals in fields A, B, C, D and E.
The table shows the cost, in \(\pounds\), of making a paved path between each pair of fields.
A river means that it is not possible to make a paved path between C and E .

1. Determine the minimum cost of connecting the fields.
2. 1. By applying the lower bound algorithm to each vertex in turn, determine a best lower bound for \(P\), the minimum cost of making a circular tour (cycle) of paved paths that visits each field once.
   2. By applying the nearest neighbour algorithm, starting at each vertex in turn, find a best upper bound for \(P\). You do not need to attempt any route improvements.
   3. Give the order in which the fields are visited in a circular tour of paved paths that corresponds to the best upper bound found in part (b)(ii).
3. Give a practical reason why the total cost of paving for the project might be more than the best upper bound found in part (b)(ii). It becomes possible to use an existing bridge to make a paved route between C and E . Using this bridge, there is a new indirect route from A to D that costs less than \(\pounds 900\) to pave.
4. When this bridge is used, what can be determined about the minimum cost of
   1. paving the route between C and E
   2. connecting all the fields?

7 A network is formed by weighting the graph below using the listed arc weights. \includegraphics[max width=\textwidth, alt={}, center]{133395d2-5020-4054-a229-70168f1d0f95-8_168_190_310_258} \(\begin{array} { l l l l l l l l } 2.9 & 0.9 & 1.5 & 3.5 & 4.2 & 5.3 & 4.7 & 2.3 \end{array}\)

1. 1. Show the result after the first pass and after the second pass, when the list of weights is sorted into increasing order using bubble sort.
   2. Show the result after the first pass and after the second pass, when the list of weights is sorted into increasing order using shuttle sort. In the remaining passes of bubble sort another 14 comparisons are made.
      In the remaining passes of shuttle sort another 11 comparisons are made.
      The total number of swaps needed is the same for both sorting methods.
2. Use the total number of comparisons and the total number of swaps to compare the efficiency of bubble sort and shuttle sort for sorting this list of weights. The sorted list of arc weights for the network is as follows. \(\begin{array} { l l l l l l l l } 0.9 & 1.5 & 2.3 & 2.9 & 3.5 & 4.2 & 4.7 & 5.3 \end{array}\) These weights can be given to the arcs of the graph in several ways to form different networks.
3. 1. What is the smallest weight that does not have to appear in a minimum spanning tree for any of these networks? You must explain your reasoning.
   2. Show a way of weighting the arcs, using the weights in the list, that results in the largest possible total for a minimum spanning tree. You should state the total weight of your minimum spanning tree.
   3. Determine the total weight of an optimal solution of the route inspection problem for the network found in part (c)(ii). \section*{END OF QUESTION PAPER}

1 Fiona is a mobile hairdresser. One day she needs to visit five clients, A to E, starting and finishing at her own house at F . She wants to find a suitable route that does not involve her driving too far.

1. Which standard network problem does Fiona need to solve? The shortest distances between clients, in km, are given in the matrix below.

   	A	B	C	D	E
   A	-	12	8	6	4
   B	12	-	10	8	10
   C	8	10	-	13	10
   D	6	8	13	-	10
   E	4	10	10	10	-

2. Use the copy of the matrix in the Printed Answer Booklet to construct a minimum spanning tree for these five client locations.
   State the algorithm you have used, show the order in which you build your tree and give its total weight. Draw your minimum spanning tree. The distance from Fiona's house to each client, in km, is given in the table below.

   	A	B	C	D	E
   F	2	11	9	7	5

3. Use this information together with your answer to part (ii) to find a lower bound for the length of Fiona's route.
4. (a) Find all the cycles that result from using the nearest neighbour method, starting at F .
   (b) Use these to find an upper bound for the length of Fiona's route.
5. Fiona wants to drive less than 35 km . Using the information in your answers to parts (iii) and (iv) explain whether or not a route exists which is less than 35 km in length.

1. The table represents a network that shows the time taken, in minutes, to travel by car between eight villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H .

1. 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 select them.
2. Draw your minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the tree.
3. State whether your minimum spanning tree is unique. Justify your answer.

2. Kruskal's algorithm finds a minimum spanning tree for a connected graph with \(n\) vertices.

1. Explain the terms
   1. connected graph,
   2. tree,
   3. spanning tree.
2. Write down, in terms of \(n\), the number of arcs in the minimum spanning tree. The table below 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 .

   	A	B	C	D	E	F	G
   A	-	17	-	19	30	-	-
   B	17	-	21	23	-	-	-
   C	-	21	-	27	29	31	22
   D	19	23	27	-	-	40	-
   E	30	-	29	-	-	33	25
   F	-	-	31	40	33	-	39
   G	-	-	22	-	25	39	-

3. Complete the drawing of the network on Diagram 1 in the answer book by adding the necessary arcs from vertex C together with their weights.
4. 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.
5. State the weight of the minimum spanning tree.