7.04c Travelling salesman upper bound: nearest neighbour method

4. \begin{figure}[h] \end{figure} The network in Figure 3 shows the roads linking a depot, D, and three collection points \(\mathrm { A } , \mathrm { B }\) and C . The number on each arc represents the length, in miles, of the corresponding road. The road from B to D is a one-way road, as indicated by the arrow.

1. Explain clearly if Dijkstra's algorithm can be used to find a route from D to A . The initial distance and route tables for the network are given in the answer book.
2. Use Floyd's algorithm to find a table of least distances. You should show both the distance table and the route table after each iteration.
3. Explain how the final route table can be used to find the shortest route from D to B . State this route. There are items to collect at \(\mathrm { A } , \mathrm { B }\) and C . A van will leave D to make these collections in any order and then return to D. A minimum route is required. Using the final distance table and the Nearest Neighbour algorithm starting at D,
4. find a minimum route and state its length. Floyd's algorithm and Dijkstra's algorithm are applied to a network. Each will find the shortest distance between vertices of the network.
5. Describe how the results of these algorithms differ.

1. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network of pipes. The numbers in circles represent an initial flow from S to T . The other number on each arc represents the capacity, in litres per second, of the corresponding pipe.

1. 1. State the value of \(x\)
   2. State the value of \(y\)
2. State the value of the initial flow.
3. State the capacity of cut \(C _ { 1 }\)
4. Find, by inspection, a flow-augmenting route to increase the flow by four units. You must state your route. The flow-augmenting route from (d) is used to increase the flow from S to T .
5. Prove that the flow is now maximal. A vertex restriction is now applied so that no more than 12 litres per second can flow through E.
6. 1. Complete Diagram 1 in the answer book to show this restriction.
   2. State the value of the maximum flow through the network with this restriction.

6. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The number on each arc \(( x , y )\) represents the lower \(( x )\) capacity and upper \(( y )\) capacity of that arc.

1. Calculate the value of the cut \(C _ { 1 }\) and cut \(C _ { 2 }\)
2. Explain why the flow through the network must be at least 12 and at most 16
3. Explain why arcs DG, AG, EG and FG must all be at their lower capacities.
4. Determine a maximum flow pattern for this network and draw it on Diagram 1 in the answer book. You do not need to use the labelling procedure.
5. 1. State the value of the maximum flow through the network.
   2. Explain why the value of the maximum flow is equal to the value of the minimum flow through the network. Node E becomes blocked and no flow can pass through it. To maintain the maximum flow through the network the upper capacity of exactly one arc is increased.
6. Explain how it is possible to maintain the maximum flow found in (d).

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.

5 Answer this question on the insert provided. The network below represents a simplified map of a building. The arcs represent corridors and the weights on the arcs represent the lengths of the corridors, in metres. The sum of the weights on the arcs is 765 metres. \includegraphics[max width=\textwidth, alt={}, center]{dbf782dd-879c-4f0f-b532-246a0db9f130-5_1271_1539_584_303}

1. Janice is the cleaning supervisor in the building. She is at the position marked as J when she is called to attend a cleaning emergency at B. On the network in the insert, use Dijkstra's algorithm, starting from vertex J and continuing until B is given a permanent label, to find the shortest path from J to B and the length of this path.
2. In her job J anice has to walk along each of the corridors represented on the network. This requires finding a route that covers every arc at least once, starting and ending at J. Showing all your working, find the shortest distance that J anice must walk to check all the corridors. The labelled vertices represent 'cleaning stations'. J anice wants to visit every cleaning station using the shortest possible route. She produces a simplified network with no repeated arcs and no arc that joins a vertex to itself.
3. On the insert, complete Janice's simplified network. Which standard network problem does Janice need to solve to find the shortest distance that she must travel?

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

2 Answer this question on the insert provided. Fig. 2 shows a network in which the weights on the arcs represent distances. \begin{figure}[h] \end{figure}

1. Apply Floyd's algorithm on the insert provided to find the complete network of shortest distances.
2. Show how to use your final matrices to find the shortest route from vertex \(\mathbf { 1 }\) to vertex 3, together with the length of that route.
3. Use the nearest neighbour algorithm, starting at vertex 1, to find a Hamilton cycle in the complete network of shortest distances. Give the corresponding cycle in the original network, together with its length.

4 Tom is planning a day out walking. He wants to start from his sister's house ( S ), then visit three places \(\mathrm { A } , \mathrm { B }\) and C (once each, in any order) and then finish at his own house (T).

1. Complete the graph in the Printed Answer Booklet showing all possible arcs that could be used to plan Tom's walk. Tom needs to keep the total distance that he walks to a minimum, so he weights his graph.
2. (a) Why would finding the shortest path from S to T , on Tom's network, not necessarily solve Tom's problem?
   (b) Why would finding a minimum spanning tree, on Tom's network, not necessarily solve Tom's problem? The distance matrix below shows the direct distances, in km , between places.

   	S	A	B	C	T
   n S	0	3	2	5	4
   nA	3	0	2	2.5	2
   nB	2	2	0	3.2	2.5
   n	5	2.5	3.2	0	2
   \cline { 2 - 6 } T	4	2	2.5	2	0
   \cline { 2 - 6 }
   \cline { 2 - 6 }

3. - Use an appropriate algorithm to find a minimum spanning tree for Tom's network.

5 Consider the problem given below: $$\begin{array} { l l } \text { Minimise } & 4 \mathrm { AB } + 7 \mathrm { AC } + 8 \mathrm { BD } + 5 \mathrm { CD } + 5 \mathrm { CE } + 6 \mathrm { DF } + 3 \mathrm { EF } \\ \text { subject to } & \mathrm { AB } , \mathrm { AC } , \mathrm { BD } , \mathrm { CD } , \mathrm { CE } , \mathrm { DF } \text { and } \mathrm { EF } \text { are each either } 0 \text { or } 1 \\ & \mathrm { AB } + \mathrm { AC } + \mathrm { BD } + \mathrm { CD } + \mathrm { CE } + \mathrm { DF } + \mathrm { EF } = 5 \\ & \mathrm { AB } + \mathrm { AC } \geqslant 1 , \quad \mathrm { AB } + \mathrm { BD } \geqslant 1 , \quad \mathrm { AC } + \mathrm { CD } + \mathrm { CE } \geqslant 1 , \\ & \mathrm { BD } + \mathrm { CD } + \mathrm { DF } \geqslant 1 , \quad \mathrm { CE } + \mathrm { EF } \geqslant 1 , \quad \mathrm { DF } + \mathrm { EF } \geqslant 1 \end{array}$$

1. Explain why this is not a standard LP formulation that could be set up as a Simplex tabulation. The variables \(\mathrm { AB } , \mathrm { AC } , \ldots\) correspond to arcs in a network. The weight on each arc is the coefficient of the corresponding variable in the objective function.
2. Draw the network on the vertices in the Printed Answer Booklet. A variable that takes the value 1 corresponds to an arc that is used in the solution and a variable with the value 0 corresponds to an arc that is not used in the solution.
3. Explain what is ensured by the constraint \(\mathrm { AB } + \mathrm { AC } \geqslant 1\). Julie claims that the solution to the problem will give the minimum spanning tree for the network.
4. Find the minimum spanning tree for the network.
   Kim has a different network, exactly one of the arcs in this network is a directed arc.
   Kim wants to find a minimum weight set of arcs such that it is possible to get from any vertex to any other vertex.
5. Explain why, if Kim's problem has a solution, the directed arc cannot be part of it.

10. & Freya
A binary search is to be performed on the names in the list above to locate the name Kim.

1. Explain why a binary search cannot be performed with the list in its present form.
2. Using an appropriate algorithm, alter the list so that a binary search can be performed, showing the state of the list after each complete iteration. State the name of the algorithm you have used.
3. Use the binary search algorithm to locate the name Kim in the list you obtained in (b). You must make your method clear.
   2. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-3_858_1169_244_447} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure}
   1. Define the terms
      1. tree,
      2. minimum spanning tree.
         (3)
      3. Use Kruskal's algorithm to find a minimum spanning tree for the network shown in Figure 1. 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)
      4. Draw your minimum spanning tree using the vertices given in Diagram 1 in the answer book.
   2. State whether your minimum spanning tree is unique. Justify your answer.
      (1)
      3. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-4_1492_1298_210_379} \captionsetup{labelformat=empty} \caption{Figure 2}
      \end{figure} Figure 2 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region.
   3. Write down the inequalities that form region \(R\). The objective is to maximise \(3 x + y\).
   4. Find the optimal values of \(x\) and \(y\). You must make your method clear.
   5. Obtain the optimal value of the objective function. Given that integer values of \(x\) and \(y\) are now required,
   6. write down the optimal values of \(x\) and \(y\).
      4. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-5_623_577_287_383} \captionsetup{labelformat=empty} \caption{Figure 3}
      \end{figure} \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-5_620_582_287_1098} \captionsetup{labelformat=empty} \caption{Figure 4}
      \end{figure} Figure 3 shows the possible allocations of five workers, Adam (A), Catherine (C), Harriet (H), Josh (J) and Richard (R) to five tasks, 1, 2, 3, 4 and 5. Figure 4 shows an initial matching.
      There are three possible alternating paths that start at A .
      One of them is $$A - 3 = R - 4 = C - 5$$
   7. Find the other two alternating paths that start at A .
   8. List the improved matching generated by using the alternating path \(\mathrm { A } - 3 = \mathrm { R } - 4 = \mathrm { C } - 5\).
   9. Starting from the improved matching found in (b), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path used and your final matching.
      5. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-6_835_913_219_575} \captionsetup{labelformat=empty} \caption{Figure 5
      [0pt] [The total weight of the network is 98 km ]}
      \end{figure} Figure 5 models a network of gas pipes that have to be inspected. The number on each arc represents the length, in km, of that pipe. A route of minimum length that traverses each pipe at least once and starts and finishes at A needs to be found.
   10. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
   11. Write down a possible shortest inspection route, giving its length. It is now decided to start the inspection route at D . The route must still traverse each pipe at least once but may finish at any node.
   12. Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of your route.
       6. \begin{figure}[h]
       \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-7_823_1374_226_347} \captionsetup{labelformat=empty} \caption{Figure 6}
       \end{figure} Figure 6 shows a network of cycle tracks. The number on each arc gives the length, in km, of that track.
   13. Use Dijkstra's algorithm to find the shortest route from A to H. State your shortest route and its length.
   14. Explain how you determined your shortest route from your labelled diagram. The track between E and F is now closed for resurfacing and cannot be used.
   15. Find the shortest route from A to H and state its length.
       (2)
       7. \begin{figure}[h]
       \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-8_798_1497_258_283} \captionsetup{labelformat=empty} \caption{Figure 7}
       \end{figure} A project is modelled by the activity network shown in Figure 7. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
   16. Complete the precedence table in the answer book.
       (3)
   17. Complete Diagram 1 in the answer book, to show the early event times and late event times.
   18. State the critical activities.
   19. On the grid in your answer book, draw a cascade (Gantt) chart for this project.
   20. By considering the activities that must take place between time 7 and time 16, explain why it is not possible to complete this project with just 3 workers in the minimum time.
       8. A firm is planning to produce two types of radio, type A and type B. Market research suggests that, each week:
       Each type A radio requires 3 switches and each type B radio requires 2 switches. The firm can only buy 200 switches each week. The profit on each type A radio is \(\pounds 15\).
       The profit on each type B radio is \(\pounds 12\).
       The firm wishes to maximise its weekly profit.
       Formulate this situation as a linear programming problem, defining your variables.
       (Total 7 marks)

8 Salvadore is visiting six famous places in Barcelona: La Pedrera \(( L )\), Nou Camp \(( N )\), Olympic Village \(( O )\), Park Guell \(( P )\), Ramblas \(( R )\) and Sagrada Familia \(( S )\). Owing to the traffic system the time taken to travel between two places may vary according to the direction of travel. The table shows the times, in minutes, that it will take to travel between the six places.

1. Find the total travelling time for:
   1. the route \(L N O L\);
   2. the route \(L O N L\).
2. Give an example of a Hamiltonian cycle in the context of the above situation.
3. Salvadore intends to travel from one place to another until he has visited all of the places before returning to his starting place.
   1. Show that, using the nearest neighbour algorithm starting from Sagrada Familia \(( S )\), the total travelling time for Salvadore is 145 minutes.
   2. Explain why your answer to part (c)(i) is an upper bound for the minimum travelling time for Salvadore.
   3. Salvadore starts from Sagrada Familia ( \(S\) ) and then visits Ramblas ( \(R\) ). Given that he visits Nou Camp \(( N )\) before Park Guell \(( P )\), find an improved upper bound for the total travelling time for Salvadore.

3 Mark is driving around the one-way system in Leicester. The following table shows the times, in minutes, for Mark to drive between four places: \(A , B , C\) and \(D\). Mark decides to start from \(A\), drive to the other three places and then return to \(A\). Mark wants to keep his driving time to a minimum.

1. Find the length of the tour \(A B C D A\).
2. Find the length of the tour \(A D C B A\).
3. Find the length of the tour using the nearest neighbour algorithm starting from \(A\).
4. Write down which of your answers to parts (a), (b) and (c) gives the best upper bound for Mark's driving time.

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.

5 There is a one-way system in Manchester. Mia is parked at her base, \(B\), in Manchester and intends to visit four other places, \(A , C , D\) and \(E\), before returning to her base. The following table shows the distances, in kilometres, for Mia to drive between the five places \(A , B , C , D\) and \(E\). Mia wants to keep the total distance that she drives to a minimum.

1. Find the length of the tour \(B E C D A B\).
2. Find the length of the tour obtained by using the nearest neighbour algorithm starting from \(B\).
3. Write down which of your answers to parts (a) and (b) would be the better upper bound for the total distance that Mia drives.
4. On a particular day, the council decides to reverse the one-way system. For this day, find the length of the tour obtained by using the nearest neighbour algorithm starting from \(B\).

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

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.