7.04c Travelling salesman upper bound: nearest neighbour method

7 Rob delivers bread to six shops \(A , B , C , D , E\) and \(F\). Each day, Rob starts at shop \(A\), travels to each of the other shops before returning to shop \(A\). The table shows the distances, in miles, between the shops.

1. 1. Find the length of the tour \(A B C D E F A\).
   2. Find the length of the tour obtained by using the nearest neighbour algorithm starting from \(A\).
2. By deleting \(A\), find a lower bound for the length of a minimum tour.
3. By deleting \(F\), another lower bound of 45 miles is obtained for the length of a minimum tour. The length of a minimum tour is \(T\) miles. Write down the smallest interval for \(T\) which can be obtained from your answers to parts (a) and (b), and the information given in this part.
   (3 marks)

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

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

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

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

8 Tony delivers paper to five offices, \(A , B , C , D\) and \(E\). Tony starts his deliveries at office \(E\) and travels to each of the other offices once, before returning to office \(E\). Tony wishes to keep his travelling time to a minimum. The table shows the travelling times, in minutes, between the offices.

4 David, a tourist, wishes to visit five places in Rome: Basilica ( \(B\) ), Coliseum ( \(C\) ), Pantheon ( \(P\) ), Trevi Fountain ( \(T\) ) and Vatican ( \(V\) ). He is to start his tour at one of the places, visit each of the other places, before returning to his starting place. The table shows the times, in minutes, to travel between these places. David wishes to keep his travelling time to a minimum.

1. 1. Find the total travelling time for the tour TPVBCT.
   2. Find the total travelling time for David's tour using the nearest neighbour algorithm starting from \(T\).
   3. Explain why your answer to part (a)(ii) is an upper bound for David's minimum total travelling time.
2. 1. By deleting \(B\), find a lower bound for the total travelling time for the minimum tour.
   2. Explain why your answer to part (b)(i) is a lower bound for David's minimum total travelling time.
3. Sketch a network showing the edges that give the lower bound found in part (b)(i) and comment on its significance.

5 Angelo is visiting six famous places in Palermo: \(A , B , C , D , E\) and \(F\). He intends to travel from one place to the next until he has visited all of the places before returning to his starting place. Due to the traffic system, the time taken to travel between two places may be different dependent on the direction travelled. The table shows the times, in minutes, taken to travel between the six places.

1. Give an example of a Hamiltonian cycle in this context.
2. 1. Show that, if the nearest neighbour algorithm starting from \(F\) is used, the total travelling time for Angelo would be 95 minutes.
   2. Explain why your answer to part (b)(i) is an upper bound for the minimum travelling time for Angelo.
3. Angelo starts from \(F\) and visits \(E\) next. He also visits \(B\) before he visits \(D\). Find an improved upper bound for Angelo's total travelling time.
   
   \includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-11_2484_1709_223_153}

8 Mrs Jones is a spy who has to visit six locations, \(P , Q , R , S , T\) and \(U\), to collect information. She starts at location \(Q\), and travels to each of the other locations, before returning to \(Q\). She wishes to keep her travelling time to a minimum. The diagram represents roads connecting different locations. The number on each edge represents the travelling time, in minutes, along that road. \includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-16_524_866_612_587}

1. 1. Explain why the shortest time to travel from \(P\) to \(R\) is 40 minutes.
   2. Complete Table 1, on the opposite page, in which the entries are the shortest travelling times, in minutes, between pairs of locations.
2. 1. Use the nearest neighbour algorithm on Table 1, starting at \(Q\), to find an upper bound for the minimum travelling time for Mrs Jones's tour.
   2. Mrs Jones decides to follow the route given by the nearest neighbour algorithm. Write down her route, showing all the locations through which she passes.
3. By deleting \(Q\) from Table 1, find a lower bound for the travelling time for Mrs Jones's tour. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Table 1}

   	\(\boldsymbol { P }\)	\(Q\)	\(\boldsymbol { R }\)	\(\boldsymbol { S }\)	\(T\)	\(\boldsymbol { U }\)
   \(P\)	-	25
   \(Q\)	25	-	20	21	23	11
   \(\boldsymbol { R }\)		20	-
   \(\boldsymbol { S }\)		21		-
   \(T\)		23			-	12
   \(\boldsymbol { U }\)		11			12	-

   \end{table}
   \includegraphics[max width=\textwidth, alt={}]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-18_2486_1714_221_153}

7 Rupta, a sales representative, has to visit six shops, \(A , B , C , D , E\) and \(F\). Rupta starts at shop \(A\) and travels to each of the other shops once, before returning to shop \(A\). Rupta wishes to keep her travelling time to a minimum. The table shows the travelling times, in minutes, between the shops.

4 Sarah is a mobile hairdresser based at \(A\). Her day's appointments are at five places: \(B , C , D , E\) and \(F\). She can arrange the appointments in any order. She intends to travel from one place to the next until she has visited all of the places, starting and finishing at \(A\). The following table shows the times, in minutes, that it takes to travel between the six places.

1. Sarah decides to visit the places in the order \(A B C D E F A\). Find the travelling time of this tour.
2. Explain why this answer can be considered as being an upper bound for the minimum travelling time of Sarah's tour.
3. Use the nearest neighbour algorithm, starting from \(A\), to find another upper bound for the minimum travelling time of Sarah's tour.
4. By deleting \(A\), find a lower bound for the minimum travelling time of Sarah's tour.
5. Sarah thinks that she can reduce her travelling time to 75 minutes. Explain why she is wrong.

3 The diagram shows a network. The weights on the arcs represent distances in miles. The direct path between any two adjacent vertices is never longer than any indirect path. \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-02_490_748_1372_699}

1. By deleting vertex \(U\) and all arcs connected to \(U\), find a lower bound for the length of the shortest cycle that visits every vertex of this network.
2. Find a vertex that can be used as the start vertex for the nearest neighbour method to give a cycle that passes through every vertex of this network. Give your cycle and its length.

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

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

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

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

4

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

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

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

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

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

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

3 This diagram shows a network. \includegraphics[max width=\textwidth, alt={}, center]{9aa57bb0-3d88-4858-a348-ff95592fa659-2_693_744_1307_694}

1. Obtain a minimum connector for this network. Draw your minimum connector, state the order in which the arcs were chosen and give their total weight.
2. Use the nearest neighbour method, starting from vertex \(A\), to find a cycle that passes through every vertex. The network represents a cubical die, with vertices labelled \(A\) to \(H\), and faces numbered from 1 to 6 in such a way that the numbers on each pair of opposite faces add up to 7 . When two faces meet in an edge, the sum of the numbers on the two faces is recorded as the weight on that edge.
3. (a) List the vertices of each of the two faces that meet in the edge \(A G\).
   (b) What number is on the face \(A C E G\) ?
   (c) Which face is numbered 3?

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

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

6 The arcs in the network represent the tracks in a forest. The weights on the arcs represent distances in km . \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-7_535_1267_395_440} Richard wants to walk along every track in the forest. The total weight of the arcs is \(26.7 + x\).

1. Find, in terms of \(x\), the length of the shortest route that Richard could use to walk along every track, starting at \(A\) and ending at \(G\). Show all of your working.
2. Now suppose that Richard wants to find the length of the shortest route that he could use to walk along every track, starting and ending at \(A\). Show that for \(x \leqslant 1.8\) this route has length \(( 32.4 + 2 x ) \mathrm { km }\), and for \(x \geqslant 1.8\) it has length \(( 34.2 + x ) \mathrm { km }\). Whenever two tracks join there is an information board for visitors to the forest. Shauna wants to check that the information boards have not been vandalised. She wants to find the length of the shortest possible route that starts and ends at \(A\), passing through every vertex at least once. Consider first the case when \(x\) is less than 3.2.
3. (a) Apply Prim's algorithm to the network, starting from vertex \(A\), to find a minimum spanning tree. Draw the minimum spanning tree and state its total weight. Explain why the solution to Shauna's problem must be longer than this.
   (b) Use the nearest neighbour strategy, starting from vertex \(A\), and show that it stalls before it has visited every vertex. Now consider the case when \(x\) is greater than 3.2 but less than 4.6.
4. (a) Draw the minimum spanning tree and state its total weight.
   (b) Use the nearest neighbour strategy, starting from vertex \(A\), to find a route from \(A\) to \(G\) passing through each vertex once. Write down the route obtained and its total weight. Show how a shortcut can give a shorter route from \(A\) to \(G\) passing through each vertex. Hence, explaining your method, find an upper bound for Shauna's problem.

5 Jess and Henry are out shopping. The network represents the main routes between shops in a shopping arcade. The arcs represent pathways and escalators, the vertices represent some of the shops and the weights on the arcs represent distances in metres. \includegraphics[max width=\textwidth, alt={}, center]{ccb12789-cd5f-40dc-9f10-f8bb45399580-6_586_1084_367_495} The total weight of all the arcs is 1200 metres.
The table below shows the shortest distances between vertices; some of these are indirect distances.

1. Use a standard algorithm to find the shortest distance that Jess must travel to cover every arc in the original network, starting and ending at \(M\).
2. Find the shortest distance that Jess must travel if she just wants to cover every arc, but does not mind where she starts and where she finishes. Which two points are her start and finish? Henry suggests that Jess only needs to visit each shop.
3. Apply the nearest neighbour method to the network, starting at \(M\), to write down a closed tour through all the vertices. Calculate the weight of this tour. What does this value tell you about the length of the shortest closed route that passes through every vertex? Henry thinks that Jess does not need to visit shop \(W\). He uses the table of shortest distances to list all the possible connections between \(M , N , P , R , S\) and \(V\) by increasing order of weight. Henry's list is given in your answer book.
4. Use Kruskal's algorithm on Henry's list to find a minimum spanning tree for \(M , N , P , R , S , T\) and \(V\). Draw the tree and calculate its total weight. Jess insists that they must include shop \(W\).
5. Use the weight of the minimum spanning tree for \(M , N , P , R , S , T\) and \(V\), and the table of shortest distances, to find a lower bound for the length of the shortest closed route that passes through all eight vertices.

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

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

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

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

2

1. A minimum spanning tree is constructed for a network. A vertex and all arcs joined to it are then deleted from the network. Under what circumstances will the remaining arcs of the minimum spanning tree form a minimum spanning tree for the reduced network? Joseph wants to use Kruskal's algorithm to find the minimum spanning tree for a network. He has sorted the arcs in the network by increasing order of weight. $$\begin{array} { l l l l l l l } B D = 5 & F G = 5 & D E = 6 & D F = 7 & E H = 7 & B C = 8 & D G = 8 \\ G H = 8 & A D = 9 & C D = 9 & E G = 9 & A B = 10 & A E = 10 & C F = 10 \end{array}$$
2. Use Kruskal's algorithm on the list in your answer book, crossing out arcs that are not used. Draw your minimum spanning tree and give its total weight.
3. By considering the minimum spanning tree for the reduced network formed when vertex \(A\) and all arcs joined to \(A\) are deleted, find a lower bound for the shortest closed cycle through every vertex on the original network. The table shows the arc weights for the same network.

   	A	\(B\)	C	D	E	\(F\)	G	\(H\)
   A	-	10	-	9	10	-	-	-
   B	10	-	8	5	-	-	-	-
   C	-	8	-	9	-	10	-	-
   D	9	5	9	-	6	7	8	-
   E	10	-	-	6	-	一	9	7
   F	-	-	10	7	-	-	5	-
   G	-	-	-	8	9	5	-	8
   H	-	-	-	-	7	-	8	-

4. Apply the nearest neighbour method, starting at \(A\), to find a cycle through every vertex. Hence write down an upper bound for the shortest closed cycle through every vertex on the network.

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

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

5 [Answer this question on the insert provided.] \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-3_659_1002_324_609} In this network the vertices represent towns, the arcs represent roads and the weights on the arcs show the shortest distances in kilometres.

1. The diagram on the insert shows the result of deleting vertex \(F\) and all the arcs joined to \(F\). Show that a lower bound for the length of the travelling salesperson problem on the original network is 38 km . The corresponding lower bounds by deleting each of the other vertices are: $$A : 40 \mathrm {~km} , \quad B : 39 \mathrm {~km} , \quad C : 35 \mathrm {~km} , \quad D : 37 \mathrm {~km} , \quad E : 35 \mathrm {~km} \text {. }$$ The route \(A - B - C - D - E - F - A\) has length 47 km .
2. Using only this information, what are the best upper and lower bounds for the length of the solution to the travelling salesperson problem on the network?
3. By considering the orders in which vertices \(C , D\) and \(E\) can be visited, find the best upper bound given by a route of the form \(A - B - \ldots - F - A\).

6 [Answer part (i) of this question on the insert provided.]
The diagram shows a simplified version of an orienteering course. The vertices represent checkpoints and the weights on the arcs show the travel times between checkpoints, in minutes. \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-4_483_931_461_630}

1. Use Dijkstra's algorithm, starting from checkpoint \(\boldsymbol { A }\), to find the least travel time from \(A\) to \(D\). You must show your working, including temporary labels, permanent labels and the order in which permanent labels were assigned. Give the route that takes the least time from \(A\) to \(D\).
2. By using an appropriate algorithm, find the least time needed to travel every arc in the diagram starting and ending at \(A\). You should show your method clearly.
3. Starting from \(A\), apply the nearest neighbour algorithm to the diagram to find a cycle that visits every checkpoint. Use your solution to find a path that visits every checkpoint, starting from \(A\) and finishing at \(D\).

6 The diagram shows routes between points in a town. The distances are in kilometres. \includegraphics[max width=\textwidth, alt={}, center]{dfe6db33-33d0-4dff-95f7-fbf097e3963e-6_817_1219_319_422}

1. Use an appropriate algorithm to find a set of connecting arcs of minimum total length. Indicate your connecting arcs on the copy of the diagram in your answer book, and give their total length.
2. Give the name of the algorithm you have used, and describe it briefly.
3. Using the second diagram in your answer book, apply Dijkstra's algorithm to find the shortest distances from A to each of the other points. List the connections that are used, and give their total length.