7.04d Travelling salesman lower bound: using minimum spanning tree

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.

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.
   

3 Answer this question on the insert provided. \includegraphics[max width=\textwidth, alt={}, center]{43fe5fd5-4b98-4c3a-90ca-a1bd5cf065fe-3_492_1006_356_568}

1. 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.
2. Use your answer to part (i) to find the weight of a minimum spanning tree for the network with vertex \(E\), and all the arcs joined to \(E\), removed. Hence find a lower bound for the travelling salesperson problem on the original network.
3. Show that the nearest neighbour method, starting from vertex \(A\), fails on the original network.
4. Apply the nearest neighbour method, starting from vertex \(B\), to find an upper bound for the travelling salesperson problem on the original network.
5. Apply Dijkstra's algorithm to the copy of the network in the insert to find the least weight path from \(A\) to \(G\). State the weight of the path and give its route.
6. The sum of the weights of all the arcs is 300 . Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. The weights of least weight paths from vertex \(A\) should be found using your answer to part (v); the weights of other such paths should be determined by inspection.

6 Answer this question on the insert provided. The table shows the distances, in miles, along the direct roads between six villages, \(A\) to \(F\). A dash ( - ) indicates that there is no direct road linking the villages.

1. On the table in the insert, use Prim's algorithm 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. Draw your minimum spanning tree and state its total weight.
2. By deleting vertex B and the arcs joined to vertex B, calculate a lower bound for the length of the shortest cycle through all the vertices.
3. A pply the nearest neighbour method to the table above, starting from \(F\), to find a cycle that passes through every vertex and use this to write down an upper bound for the length of the shortest cycle through all the vertices.
   {}

6 Answer this question on the insert provided. Four friends have decided to sponsor four birds at a bird sanctuary. They want to construct a route through the bird sanctuary, starting and ending at the entrance/exit, that enables them to visit the four birds in the shortest possible time. The table below shows the times, in minutes, that it takes to get between the different birds and the entrance/exit. The friends will spend the same amount of time with each bird, so this does not need to be included in the calculation. Let the stages be \(0,1,2,3,4,5\). Stage 0 represents arriving at the sanctuary entrance. Stage 1 represents visiting the first bird, stage 2 the second bird, and so on, with stage 5 representing leaving the sanctuary. Let the states be \(0,1,2,3,4\) representing the entrance/exit, kite, lark, moorhen and nightjar respectively.

1. Calculate how many minutes it takes to travel the route $$( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 4 ) - ( 5 ; 0 ) .$$ The friends then realise that if they try to find the quickest route using dynamic programming with this (stage; state) formulation, they will get the route \(( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )\), or this in reverse, taking 27 minutes.
2. Explain why the route \(( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )\) is not a solution to the friends' problem. Instead, the friends set up a dynamic programming tabulation with stages and states as described above, except that now the states also show, in brackets, any birds that have already been visited. So, for example, state \(1 ( 234 )\) means that they are currently visiting the kite and have already visited the other three birds in some order. The partially completed dynamic programming tabulation is shown opposite.
3. For the last completed row, i.e. stage 2, state 1(3), action 4(13), explain where the value 18 and the value 6 in the working column come from.
4. Complete the table in the insert and hence find the order in which the birds should be visited to give a quickest route and find the corresponding minimum journey time.

   Stage	State	Action	Working	Suboptimal minimum
   \multirow{4}{*}{4}	1(234)	0	10	10
   	2(134)	0	14	14
   	3(124)	0	12	12
   	4(123)	0	17	17
   \multirow{12}{*}{3}	1(23)	4(123)	\(17 + 6 = 23\)	23
   	1(24)	3(124)	\(12 + 2 = 14\)	14
   	1(34)	2(134)	\(14 + 3 = 17\)	17
   	2(13)	4(123)	\(17 + 4 = 21\)	21
   	2(14)	3(124)	\(12 + 2 = 14\)	14
   	2(34)	1(234)	\(10 + 3 = 13\)	13
   	3(12)	4(123)	\(17 + 3 = 20\)	20
   	3(14)	2(134)	\(14 + 2 = 16\)	16
   	3(24)	1(234)	\(10 + 2 = 12\)	12
   	4(12)	3(124)	\(12 + 3 = 15\)	15
   	4(13)	2(134)	\(14 + 4 = 18\)	18
   	4(23)	1(234)	\(10 + 6 = 16\)	16
   \multirow{12}{*}{2}	1(2)	3(12) 4(12)	\(20 + 2 = 22\)	21
   	1(3)	2(13) 4(13)	\(21 + 3 = 24 18 + 6 = 24\)	24
   	1(4)
   	2(1)
   	2(3)
   	2(4)
   	3(1)
   	3(2)
   	3(4)
   	4(1)
   	4(2)
   	4(3)
   \multirow{4}{*}{1}	1
   	2
   	3
   	4
   0	0	1 2 3 4

5 [Figure 3, printed on the insert, is provided for use in this question.]

1. James is solving a travelling salesperson problem.
   1. He finds the following upper bounds: \(43,40,43,41,55,43,43\). Write down the best upper bound.
   2. James finds the following lower bounds: 33, 40, 33, 38, 33, 38, 38 . Write down the best lower bound.
2. Karen is solving a different travelling salesperson problem and finds an upper bound of 55 and a lower bound of 45 . Write down an interpretation of these results.
3. The diagram below shows roads connecting 4 towns, \(A , B , C\) and \(D\). The numbers on the edges represent the lengths of the roads, in kilometres, between adjacent towns. \includegraphics[max width=\textwidth, alt={}, center]{92175666-ef7a-4dca-9cdb-ebde1b40b2c9-05_451_1034_1160_504} Xiong lives at town \(A\) and is to visit each of the other three towns before returning to town \(A\). She wishes to find a route that will minimise her travelling distance.
   1. Complete Figure 3, on the insert, to show the shortest distances, in kilometres, between all pairs of towns.
   2. Use the nearest neighbour algorithm on Figure 3 to find an upper bound for the minimum length of a tour of this network that starts and finishes at \(A\).
   3. Hence find the actual route that Xiong would take in order to achieve a tour of the same length as that found in part (c)(ii).

7 Liam is taking part in a treasure hunt. There are five clues to be solved and they are at the points \(A , B , C , D\) and \(E\). The table shows the distances between pairs of points. All of the distances are functions of \(x\), where \(\boldsymbol { x }\) is an integer. Liam must travel to all five points, starting and finishing at \(A\).

1. The nearest point to \(A\) is \(C\).
   1. By considering \(A C\) and \(A B\), show that \(x < 10\).
   2. Find two other inequalities in \(x\).
2. The nearest neighbour algorithm, starting from \(A\), gives a unique minimum tour \(A C D E B A\).
   1. By considering the fact that Liam's tour visits \(D\) immediately after \(C\), find two further inequalities in \(x\).
   2. Find the value of the integer \(x\).
   3. Hence find the total distance travelled by Liam if he uses this tour.

6 Mia is on holiday in Venice. There are five places she wishes to visit: Rialto \(( R )\), St Mark's \(( S )\), Murano ( \(M\) ), Burano ( \(B\) ) and Lido ( \(L\) ). Boat services connect the five places. The table shows the times, in minutes, to travel between the places. Mia wishes to keep her travelling time to a minimum.

1. 1. Find the length of the tour \(S R M B L S\).
   2. Find the length of the tour using the nearest neighbour algorithm starting from \(S\).
2. By deleting Burano ( \(B\) ), find a lower bound for the length of the minimum tour.
3. Sketch a network showing the edges that give the lower bound found in part (b) and comment on its significance.

5 [Figure 2, printed on the insert, is provided for use in this question.]

1. Gill is solving a travelling salesperson problem.
   1. She finds the following upper bounds: 7.5, 8, 7, 7.5, 8.5. Write down the best upper bound.
   2. She finds the following lower bounds: \(6.5,7,6.5,5,7\). Write down the best lower bound.
2. George is travelling by plane to a number of cities. He is to start at \(F\) and visit each of the other cities at least once before returning to \(F\). The diagram shows the times of flights, in hours, between cities. Where no time is shown, there is no direct flight available. \includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-05_936_826_1162_589}
   1. Complete Figure 2 to show the minimum times to travel between all pairs of cities.
   2. Find an upper bound for the minimum total flying time by using the route FTPOMF.
   3. Using the nearest neighbour algorithm starting from \(F\), find an upper bound for the minimum total flying time.
   4. By deleting \(F\), find a lower bound for the minimum total flying time.

6

1. Mark is staying at the Grand Hotel ( \(G\) ) in Oslo. He is going to visit four famous places in Oslo: Aker Brygge ( \(A\) ), the National Theatre ( \(N\) ), Parliament House ( \(P\) ) and the Royal Palace ( \(R\) ). The figures in the table represent the walking times, in seconds, between the places.

   	Grand Hotel ( \(G\) )	Aker Brygge (A)	National Theatre ( \(N\) )	Parliament House (P)	Royal Palace (R)
   Grand Hotel ( \(G\) )	-	165	185	65	160
   Aker Brygge (A)	165	-	155	115	275
   National Theatre ( \(N\) )	185	155	-	205	125
   Parliament House (P)	65	115	205	-	225
   Royal Palace (R)	160	275	125	225	-

   Mark is to start his tour from the Grand Hotel, visiting each place once before returning to the Grand Hotel. Mark wishes to keep his walking time to a minimum.
   1. Use the nearest neighbour algorithm, starting from the Grand Hotel, to find an upper bound for the walking time for Mark's tour.
   2. By deleting the Grand Hotel, find a lower bound for the walking time for Mark's tour.
   3. The walking time for an optimal tour is \(T\) seconds. Use your answers to parts (a)(i) and (a)(ii) to write down a conclusion about \(T\).
2. Mark then intends to start from the Grand Hotel ( \(G\) ), visit three museums, Ibsen ( \(I\) ), Munch ( \(M\) ) and Viking ( \(V\) ), and return to the Grand Hotel. He uses public transport. The table shows the minimum travelling times, in minutes, between the places.

   \backslashbox{From}{To}	Grand Hotel ( \(G\) )	Ibsen (I)	Munch ( \(M\) )	Viking ( \(\boldsymbol { V }\) )
   Grand Hotel ( \(\boldsymbol { G }\) )	-	20	17	30
   Ibsen (I)	15	-	32	16
   Munch (M)	26	18	-	21
   Viking ( \(\boldsymbol { V }\) )	19	27	24	-

   1. Find the length of the tour \(G I M V G\).
   2. Find the length of the tour GVMIG.
   3. Find the number of different possible tours for Mark.
   4. Write down the number of different possible tours for Mark if he were to visit \(n\) museums, starting and finishing at the Grand Hotel.

6

1. Sarah is solving a travelling-salesman problem.
   1. She finds the following upper bounds: \(32,33,32,32,30,32,32\). Write down the best upper bound.
   2. She finds the following lower bounds: 17, 18, 17, 20, 18, 17, 20. Write down the best lower bound.
2. Rob is travelling by train to a number of cities. He is to start at \(M\) and visit each other city at least once before returning to \(M\). The diagram shows the travelling times, in minutes, between cities. Where no time is shown, there is no direct journey available. \includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-16_959_1122_1059_443} The table below shows the minimum travelling times between all pairs of cities.

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	\(\boldsymbol { B }\)	\(\boldsymbol { E }\)	\(\boldsymbol { L }\)	\(\boldsymbol { M }\)	\(\boldsymbol { N }\)
   \(\boldsymbol { B }\)	-	230	82	102	192
   \(\boldsymbol { E }\)	230	-	148	244	258
   \(\boldsymbol { L }\)	82	148	-	126	110
   \(\boldsymbol { M }\)	102	244	126	-	236
   \(\boldsymbol { N }\)	192	258	110	236	-

   1. Explain why the minimum travelling time from \(M\) to \(N\) is not 283 .
   2. Find an upper bound for the minimum travelling time by using the tour \(M N B E L M\).
   3. Write down the actual route corresponding to the tour \(M N B E L M\).
   4. Use the nearest-neighbour algorithm, starting from \(M\), to find another upper bound for the minimum travelling time of Rob's tour.
      [0pt] [4 marks] QUESTION
      1. (i) The best upper bound is \(\_\_\_\_\) (ii) The best lower bound is \(\_\_\_\_\)

6 The network shows the roads linking a warehouse at \(A\) and five shops, \(B , C , D , E\) and \(F\). The numbers on the edges show the lengths, in miles, of the roads. A delivery van leaves the warehouse, delivers to each of the shops and returns to the warehouse. \includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-12_1241_1239_484_402}

1. Complete the table, on the page opposite, showing the shortest distances between the vertices.
2. 1. Find the total distance travelled if the van follows the cycle \(A E F B C D A\).
   2. Explain why your answer to part (b)(i) provides an upper bound for the minimum journey length.
3. Use the nearest neighbour algorithm starting from \(D\) to find a second upper bound.
4. By deleting \(A\), find a lower bound for the minimum journey length.
5. Given that the minimum journey length is \(T\), write down the best inequality for \(T\) that can be obtained from your answers to parts (b), (c) and (d).
   [0pt] [1 mark] \section*{Answer space for question 6} REFERENCE

   1. 	\(\boldsymbol { A }\)	\(\boldsymbol { B }\)	\(\boldsymbol { C }\)	\(\boldsymbol { D }\)	\(\boldsymbol { E }\)	\(\boldsymbol { F }\)
      \(\boldsymbol { A }\)	-	7
      \(\boldsymbol { B }\)	7	-	5
      \(\boldsymbol { C }\)		5	-	4
      \(\boldsymbol { D }\)			4	-	6
      \(\boldsymbol { E }\)				6	-	10
      \(\boldsymbol { F }\)					10	-

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}

1. The table above shows the least distances, in km , between six towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .

1. Starting at A, and making your working clear, find an initial upper bound for the travelling salesperson problem for this network, using
   1. the minimum spanning tree method,
   2. the nearest neighbour algorithm.
      (5) By deleting A, and all of its arcs, a lower bound for the travelling salesperson problem for this network is found to be 500 km . By deleting B, and all of its arcs, the corresponding lower bound is found to be 474 km .
2. Using the results from (a) and the given lower bounds, write down the smallest interval that you can be confident contains the solution to the travelling salesperson problem for this network.
   (2)

1. The table above shows the least distances, in km, between six towns, A, B, C, D, E and F. Jas needs to visit each town, starting and finishing at D , and wishes to minimise the total distance she travels.

1. Starting at D , use the nearest neighbour algorithm to obtain an upper bound for the length of the route. You must state your route and its length.
2. Starting by deleting D , and all of its arcs, find a lower bound for the route length.

6 The diagram shows a nature reserve which has its entrance at \(A\), eight information signs at \(B , C , \ldots , I\), and fifteen grass paths. The length of each grass path is given in metres.
The total length of the grass paths is 1465 metres. \includegraphics[max width=\textwidth, alt={}, center]{dcf97b92-d067-41d4-89a6-ea5bab9ea4ff-10_812_1192_584_424} To cut the grass, Ashley starts at the entrance and drives a mower along every grass path in the nature reserve. The mower moves at 7 kilometres per hour. 6

1. Find the least possible time that it takes for Ashley to cut the grass on all fifteen paths in the nature reserve and return to the entrance. Fully justify your answer.
   6
2. Brook visits every information sign in the nature reserve to update them, starting and finishing at the entrance. For the eight information signs, the minimum connecting distance of the grass paths is 510 metres. 6 (b)
   1. Determine a lower bound for the distance Brook walks to visit every information sign.
      Fully justify your answer.
      [0pt] [2 marks]
      6
   2. Using the nearest neighbour algorithm starting from the entrance, determine an upper bound for the distance Brook walks to visit every information sign.
      [0pt] [2 marks]
      6
   3. Brook takes one minute to update the information at one information sign. Brook walks on the grass paths at an average speed of 5 kilometres per hour. Ashley and Brook start from the entrance at the same time.
   6 (c) (i) Use your answers from parts (a) and (b) to show that Ashley and Brook will return to the entrance at approximately the same time. Fully justify your answer.
   6 (c) (ii) State an assumption that you have used in part (c)(i). \includegraphics[max width=\textwidth, alt={}, center]{dcf97b92-d067-41d4-89a6-ea5bab9ea4ff-13_2488_1716_219_153} \(7 \quad\) Ali and Bex play a zero-sum game. The game is represented by the following pay-off matrix for Ali.

   \multirow{2}{*}{}	Bex
   	Strategy	\(\mathbf { B } _ { \mathbf { 1 } }\)	\(\mathbf { B } _ { \mathbf { 2 } }\)	\(\mathbf { B } _ { \mathbf { 3 } }\)
   \multirow{4}{*}{Ali}	\(\mathbf { A } _ { \mathbf { 1 } }\)	2	-1	3
   	\(\mathbf { A } _ { \mathbf { 2 } }\)	-4	-2	2
   	\(\mathbf { A } _ { \mathbf { 3 } }\)	0	1	1
   	\(\mathrm { A } _ { 4 }\)	-3	2	-2

5 Charlotte is visiting a city and plans to visit its five monuments: \(A , B , C , D\) and \(E\).
The network shows the time, in minutes, that a typical tourist would take to walk between the monuments on a busy weekday morning. \includegraphics[max width=\textwidth, alt={}, center]{ba9e9840-ce27-4ca7-ab05-50461d135445-06_902_1134_529_543} Charlotte intends to walk from one monument to another until she has visited them all, before returning to her starting place. 5

1. Use the nearest neighbour algorithm, starting from \(A\), to find an upper bound for the minimum time for Charlotte's tour.
   5
2. By deleting vertex \(B\), find a lower bound for the minimum time for Charlotte's tour.
   [0pt] [3 marks]
   5
3. Charlotte wants to complete the tour in 52 minutes. Use your answers to parts (a) and (b) to comment on whether this could be possible.
   5
4. Charlotte takes 58 minutes to complete the tour. Evaluate your answers to part (a) and part (b) given this information.
   5
5. Explain how this model for a typical tourist's tour may not be applicable if the tourist walked between the monuments during the evening.

4 Joe, a courier, is required to deliver parcels to six different locations, \(A , B , C , D , E\) and \(F\). Joe needs to start and finish his journey at the depot.
The distances, in miles, between the depot and the six different locations are shown in the table below. The minimum total distance that Joe can travel in order to make all six deliveries, starting and finishing at the depot, is \(L\) miles. 4

1. Using the nearest neighbour algorithm starting from the depot, find an upper bound for \(L\).
   4
2. By deleting the depot, find a lower bound for \(L\).
   4
3. Joe starts from the depot, delivers parcels to all six different locations and arrives back at the depot, covering 134 miles in the process. Joe claims that this is the minimum total distance that is possible for the journey. Comment on Joe's claim.

The table shows the least distances, in km, between six towns, A, B, C, D, E and F. Liz must visit each town at least once. She will start and finish at A and wishes to minimise the total distance she will travel.

1. Starting with the minimum spanning tree given in your answer book, use the shortcut method to find an upper bound below 810 km for Liz's route. You must state the shortcut(s) you use and the length of your upper bound. \hfill [2]
2. Use the nearest neighbour algorithm, starting at A, to find another upper bound for the length of Liz's route. \hfill [2]
3. Starting by deleting F, and all of its arcs, find a lower bound for the length of Liz's route. \hfill [3]
4. Use your results to write down the smallest interval which you are confident contains the optimal length of the route. \hfill [1]

Fred delivers bread to five shops, \(A\), \(B\), \(C\), \(D\) and \(E\). Fred starts his deliveries at shop \(B\), and travels to each of the other shops once before returning to shop \(B\). Fred wishes to keep his travelling time to a minimum. The table shows the travelling times, in minutes, between the shops. $$\begin{array}{c|ccccc} & A & B & C & D & E \\ \hline A & - & 3 & 11 & 15 & 5 \\ B & 3 & - & 18 & 12 & 4 \\ C & 11 & 18 & - & 5 & 16 \\ D & 15 & 12 & 5 & - & 10 \\ E & 5 & 4 & 16 & 10 & - \end{array}$$

1. Find the travelling time for the tour \(BACDEB\). [1]
2. Use the nearest neighbour algorithm, starting at \(B\), to find another upper bound for the travelling time for Fred's tour. [3]
3. By deleting \(C\), find a lower bound for the travelling time for Fred's tour. [4]
4. Sketch a network showing the edges that give you the lower bound in part (c) and comment on its significance. [2]

Phil, a squash coach, wishes to buy some equipment for his club. In a town centre, there are six shops, \(G\), \(I\), \(N\), \(R\), \(S\) and \(T\), that sell the equipment. The time, in seconds, to walk between each pair of shops is shown in the table. Phil intends to check prices by visiting each of the six shops before returning to his starting point. $$\begin{array}{c|cccccc} & G & I & N & R & S & T \\ \hline G & - & 81 & 82 & 86 & 72 & 76 \\ I & 81 & - & 80 & 82 & 68 & 73 \\ N & 82 & 80 & - & 84 & 70 & 74 \\ R & 86 & 82 & 84 & - & 74 & 70 \\ S & 72 & 68 & 70 & 74 & - & 64 \\ T & 76 & 73 & 74 & 70 & 64 & - \\ \end{array}$$

1. Use the nearest neighbour algorithm starting from \(S\) to find an upper bound for Phil's minimum walking time. [4 marks]
2. Write down a tour starting from \(N\) which has a total walking time equal to your answer to part (a). [1 mark]
3. By deleting \(S\), find a lower bound for Phil's minimum walking time. [5 marks]

Answer this question on the insert provided. \includegraphics{figure_2}

1. 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. [5]
2. Use your answer to part (i) to find the weight of a minimum spanning tree for the network with vertex \(G\), and all the arcs joined to \(G\), removed. Hence find a lower bound for the travelling salesperson problem on the original network. [3]
3. Apply the nearest neighbour method, starting from vertex \(A\), to find an upper bound for the travelling salesperson problem on the original network. [3]

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]

\includegraphics{figure_1} Figure 1 shows a network of roads connecting six villages \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\). The lengths of the roads are given in km.

1. Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection. [2] The table can now be taken to represent a complete network.
2. Use the nearest-neighbour algorithm, starting at \(A\), on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at \(A\) and visits every village exactly once. [3]
3. Interpret your answer in part (b) in terms of the original network of roads connecting the six villages. [1]
4. By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length. [2]

\includegraphics{figure_2} The network in Fig. 2 shows possible routes that an aircraft can take from \(S\) to \(T\). The numbers on the directed arcs give the amount of fuel used on that part of the route, in appropriate units. The airline wishes to choose the route for which the maximum amount of fuel used on any part of the route is as small as possible. This is the minimax route.

1. Complete the table in the answer booklet. [8]
2. Hence obtain the minimax route from \(S\) to \(T\) and state the maximum amount of fuel used on any part of this route. [2]