7.04c Travelling salesman upper bound: nearest neighbour method

1. \section*{Question 1 continued}

2. \begin{table}[h] \end{table} Table 1 represents a network that shows the travel times, in minutes, between eight towns, A, B, C, D, E, F, G and H.

1. Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must clearly state the order in which you select the edges of your tree.
2. State the weight of the minimum spanning tree. \begin{table}[h]

   \cline { 2 - 9 } \multicolumn{1}{c|}{}	A	B	C	D	E	F	G	H
   J	33	37	41	35	\(x\)	40	28	42

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table} Table 2 shows the travel times, in minutes, between town J and towns A, B, C, D, E, F, G and H .
   The journey time between towns E and J is \(x\) minutes where \(x > 28\) A salesperson needs to visit all of the nine towns, starting and finishing at J. The salesperson wishes to minimise the total time spent travelling.
3. Starting at J, use the nearest neighbour algorithm to find an upper bound for the duration of the salesperson's route. Write down the route that gives this upper bound. Using the nearest neighbour algorithm, starting at E, an upper bound of 291 minutes for the salesperson's route was found.
4. State the best upper bound that can be obtained by using this information and your answer to (c). Give the reason for your answer. Starting by deleting J and all of its arcs, a lower bound of 264 minutes for the duration of the salesperson's route was found.
5. Determine the value of \(x\). You must make your method and working clear.

3. \begin{figure}[h] \end{figure} Figure 2 shows a graph G.

1. Write down an example of a cycle on G.
   (1)
2. State, with a reason, whether or not \(\mathrm { P } - \mathrm { Q } - \mathrm { R } - \mathrm { T } - \mathrm { Q } - \mathrm { S }\) is an example of a path on G .
   (2) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{6417303d-c42a-4da4-b0fa-fb7718959417-4_618_1406_1336_340} \captionsetup{labelformat=empty} \caption{Figure 3}
   \end{figure} The numbers on the \(14 \operatorname { arcs }\) in Figure 3 represent the distances, in km , between eight vertices, \(\mathrm { P } , \mathrm { Q }\), \(\mathrm { R } , \mathrm { S } , \mathrm { T } , \mathrm { U } , \mathrm { V }\) and W , in a network.
3. Use Prim's algorithm, starting at P , to find the minimum spanning tree for the network. You must clearly state the order in which you select the arcs of your tree.
4. 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 you are adding the arc to the minimum spanning tree.
5. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. The weight on arc RU is now increased to a value of \(x\). The minimum spanning tree for the network is still unique and includes the same arcs as those found in (e).
6. Write down the smallest interval that must contain \(x\).

1. $$\begin{array} { l l l l l l l l l } 4.2 & 1.8 & 3.1 & 1.3 & 4.0 & 4.1 & 3.7 & 2.3 & 2.7 \end{array}$$

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 7.8
2. Determine whether the number of bins used in (a) is optimal. Give a reason for your answer.
3. The list of numbers is to be sorted into ascending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-02_586_1356_906_358} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure}
4. Use Kruskal's algorithm to find a minimum spanning tree for the network in Figure 1. You must show clearly the order in which you consider the arcs. For each arc, state whether or not you are including it in your minimum spanning tree. A new spanning tree is required which includes the arcs AB and DE , and which has the lowest possible total weight.
5. Explain why Prim's algorithm could not be used to complete the tree.

1. The table above shows the least distances, in km, between six cities, A, B, C, D, E and F. Mohsen needs to visit each city, starting and finishing at A , and wishes to minimise the total distance he will travel.

1. Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the length of Mohsen's route. You must state your route and its length.
2. Starting by deleting A and all of its arcs, find a lower bound for the length of Mohsen's route.
3. Use your answers from (a) and (b) to write down the smallest interval that you can be confident contains the optimal length of the route.

2. \begin{figure}[h] \end{figure} Figure 1 represents a network of roads between ten villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { 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.

1. 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.
2. Use Prim's algorithm, starting at A , to find a minimum connector for the five villages \(\mathrm { A } , \mathrm { B }\), C, D and E. You must clearly state the order in which you select the edges of your minimum connector.
3. Use Kruskal's algorithm to find a minimum connector for the five villages \(\mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { 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.
4. Calculate the total length of road that the council must keep clear of snow to ensure that all ten villages are accessible.

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. The table below shows the least distances, in km, between six towns, A, B, C, D, E and F. Mei must visit each town at least once. She will start and finish at A and wishes her route to minimise the total distance she will travel.

1. Starting with the minimum spanning tree in the answer book, use the shortcut method to find an upper bound below 520 km for Mei's route. You must state the shortcut(s) you use and the length of your upper bound.
2. Use the nearest neighbour algorithm, starting at A , to find another upper bound for the length of Mei's route.
3. Starting by deleting E, and all of its arcs, find a lower bound for the length of Mei's route. Make your method clear.

4. \begin{figure}[h] \end{figure} 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.

1. By inspection, complete the two copies of the table of least distances in the answer book.
2. 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.
3. Interpret the route found in (b) in terms of the towns actually visited.
4. 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 .
5. 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.

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.

7. The network represented by the table shows the least distances, in km, between eight museums, A, B, C, D, E, F, G and H. A tourist wants to visit each museum at least once, starting and finishing at A. The tourist wishes to minimise the total distance travelled. The shortest distance between A and D is \(x \mathrm {~km}\) where \(32 \leqslant x \leqslant 35\)

1. Using Prim's algorithm, starting at A , obtain a minimum spanning tree for the network. You must clearly state the order in which you select the arcs of your tree.
2. Use your answer to (a) to determine an initial upper bound for the length of the tourist's route.
3. Starting at A, use the nearest neighbour algorithm to find another upper bound for the length of the tourist's route. Write down the route that gives this upper bound. The nearest neighbour algorithm starting at E gives a route of $$\mathrm { E } - \mathrm { H } - \mathrm { A } - \mathrm { D } - \mathrm { G } - \mathrm { C } - \mathrm { B } - \mathrm { F } - \mathrm { E }$$
4. State which of these two nearest neighbour routes gives the better upper bound. Give reasons for your answer. Starting by deleting A, and all of its arcs, a lower bound of 235 km for the length of the route is found.
5. Determine the smallest interval that must contain the optimal length of the tourist's route. You must make your method and working clear.

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

1. 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.
2. State the weight of the minimum spanning tree.
3. Use your answer to (b) to help you calculate an initial upper bound for the total cost of Srinjoy's route.
4. Show that there are two nearest neighbour routes that start from A. You must make the routes and their corresponding costs clear.
5. State the best upper bound that can be obtained by using your answers to (c) and (d).
6. 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.
7. Use your results to write down the smallest interval that must contain the optimal cost of Srinjoy's route.

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.

1. \(\begin{array} { l l l l l l l l l l l } 18 & 20 & 11 & 7 & 17 & 15 & 14 & 21 & 23 & 16 & 9 \end{array}\) The list of numbers shown above is to be sorted into ascending order. Apply quick sort to obtain the sorted list. You must make your pivots clear. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{7396d930-0143-4876-b019-a4d73e09b172-3_839_1275_614_395} \captionsetup{labelformat=empty} \caption{Figure 3}
   \end{figure} Figure 3 represents a network of paths in a park. The number on each arc represents the length of the path in metres.
2. Using your answer to part (a) and Kruskal's algorithm, find a minimum spanning tree for the network in Figure 3. You should list the arcs in the order in which you consider them and state whether you are adding it to your minimum spanning tree.
3. Find the total 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.

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

1. Use Kruskal's algorithm to find a minimum spanning tree for the network shown in Figure 2. 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)
2. Starting at A, use Prim's algorithm to find a minimum spanning tree for the network in Figure 2. You must clearly state the order in which you include the arcs in your tree.
   (3)
3. Draw a minimum spanning tree for the network in Figure 2 using the vertices given in Diagram 1 of the answer book. State the weight of the minimum spanning tree.
   (2) A new spanning tree is required which includes the arcs DI and HG, and which has the lowest possible total weight.
4. Explain which algorithm you would choose to complete the tree, and how the algorithm should be adapted. (You do not need to find the tree.)

1. \begin{figure}[h] \end{figure} Figure 1 represents the distances, in km, 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 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 you are adding the arc to your minimum spanning tree.
   (3)
2. Starting at A, use Prim's algorithm to find the minimum spanning tree. You must clearly state the order in which you selected the arcs of your tree.
   (3)
3. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book.
4. State the weight of the tree.
   (1)

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.

4. \begin{figure}[h] \end{figure} Figure 3 represents a network of tram tracks. The number on each edge represents the length, in miles, of the corresponding track. One day, Sarah wishes to travel from A to F. She wishes to minimise the distance she travels.

1. Use Dijkstra's algorithm to find the shortest path from A to F . State your path and its length. On another day, Sarah wishes to travel from A to F via J.
2. Find a route of minimal length that goes from A to F via J and state its length.
3. Use Prim's algorithm, starting at G , to find the minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree.
4. State the length, in miles, of the minimum spanning tree.

2. \begin{figure}[h] \end{figure} Figure 3 represents nine computer terminals, A, B, C, D, E, F, G, H and J, at Pearsonby School. The school wishes to connect them to form a single computer network. The number on each arc represents the cost, in pounds, of connecting the corresponding computer terminals.

1. Use Prim's algorithm, starting at B , to find the minimum spanning tree for the computer network. You must clearly state the order in which you select the arcs of your tree.
   (3)
2. State the minimum cost of connecting the nine computer terminals.
   (1) It is discovered that some computer terminals are already connected. There are already direct connections along BD and FJ, as shown in bold in Diagram 1 in the answer book. It is decided to use these connections.
3. Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BD and FJ. You must list the arcs in the order that you consider them. In each case, state whether or not you are adding the arcs to your spanning tree.
   (3)
   (Total 7 marks)

3. \begin{figure}[h] \end{figure} Figure 1 represents the distance, in metres, between eight data collection points, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\), G and H . The data collection points are to be linked by cables.

1. Listing the arcs in the order that you select them, find a minimum spanning tree for the network using
   1. Kruskal's algorithm, stating in addition any arcs you reject,
   2. Prim's algorithm, starting from A .
2. State the minimum amount of cable needed.
3. Draw your minimum spanning tree using the vertices given in Figure 1 in your answer book.

6. (a) Define the terms

1. tree,
2. spanning tree,
3. minimum spanning tree.
   (3)
   (b) State one difference between Kruskal's algorithm and Prim's algorithm, to find a minimum spanning tree.
   (1) \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-08_894_1529_920_322}
   \end{figure} (c) Use Kruskal's algorithm to find the minimum spanning tree for the network shown in Fig. 4. State the order in which you included the arcs. Draw the minimum spanning tree in Diagram 1 in the answer book and state its length.
   (4) \section*{Figure 5}
   \includegraphics[max width=\textwidth, alt={}]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-09_887_1536_342_258}
   Figure 5 models a car park. Currently there are two pay-stations, one at \(E\) and one at \(N\). These two are linked by a cable as shown. New pay-stations are to be installed at \(B , H , A , F\) and \(C\). The number on each arc represents the distance between the pay-stations in metres. All of the pay-stations need to be connected by cables, either directly or indirectly. The current cable between \(E\) and \(N\) must be included in the final network. The minimum amount of new cable is to be used.
   (d) Using your answer to part (c), or otherwise, determine the minimum amount of new cable needed. Use Diagram 2 to show where these cables should be installed. State the minimum amount of new cable needed.
   (3)

1. 55534345928373452334247

The list of eleven numbers shown above is to be sorted into ascending order.

1. Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify your pivots clearly.
   (4) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{c8134d3b-71cb-4b92-ac54-81a4ff8f3011-03_814_1545_614_260} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure}
2. Use Kruskal's algorithm to find the minimum spanning tree for the network in Figure 1. You should list the arcs in the order in which you consider them. For each arc, state whether or not you are adding it to your minimum spanning tree.
3. 1. Draw the minimum spanning tree on Diagram 1 in the answer book.
   2. State the total weight of the tree.
      

2. The table below represents a network of shortest distances, in miles, to travel between nine castles, A, B, C, D, E, F, G, H and J.

1. Use Prim's algorithm, starting at D , to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree.
2. State the weight of the minimum spanning tree found in part (a).
3. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. A historian needs to visit all of the castles, starting and finishing at the same castle, and wishes to minimise the total distance travelled.
4. Use your answer to part (b) to calculate an initial upper bound for the length of the historian's route.
5. 1. Use the nearest neighbour algorithm, starting at D , to find an upper bound for the length of the historian's route.
   2. Write down the route which gives this upper bound. Using the nearest neighbour algorithm, starting at F , an upper bound of length 352 miles was found.
6. State the best upper bound that can be obtained by using this information and your answers from parts (d) and (e). Give the reason for your answer.
7. By deleting A and all of its arcs, find a lower bound for the length of the historian's route.
   (2) By deleting J and all of its arcs, a lower bound of length 274 miles was found.
8. State the best lower bound that can be obtained by using this information and your answer to part (g). Give the reason for your answer.

3.

1. Explain clearly the difference between the classical travelling salesperson problem and the practical travelling salesperson problem.

   	A	B	C	D	E	F	G
   A	-	17	24	16	21	18	41
   B	17	-	35	25	30	31	\(x\)
   C	24	35	-	28	20	35	32
   D	16	25	28	-	29	19	45
   E	21	30	20	29	-	22	35
   F	18	31	35	19	22	-	37
   G	41	\(x\)	32	45	35	37	-

   The table shows the least distances, in km, by road between seven towns, A, B, C, D, E, F and G . The least distance between B and G is \(x \mathrm {~km}\), where \(x > 25\) Preety needs to visit each town at least once, starting and finishing at A. She wishes to minimise the total distance she travels.
2. Starting by deleting B and all of its arcs, find a lower bound for Preety's route. Preety found the nearest neighbour routes from each of A and C . Given that the sum of the lengths of these routes is 331 km ,
3. find \(x\), making your method clear.
4. Write down the smallest interval that you can be confident contains the optimal length of Preety's route. Give your answer as an inequality.