A2 June 2023 Q5

EdexcelCurrent spec13 marksMinimum Spanning TreesRoute InspectionTravelling Salesman

5.

Figure 5: network on A to J with arcs AB 34, AG 8, AF 20, AD 42, BE 50, BH 21, BC 17, GD 23, GF 48, FD 22, FE 65, CE 33, CJ 10, HJ 12, EJ 18
Figure 5

[The total weight of the network is 423]

Direct roads between nine towns, A, B, C, D, E, F, G, H and J, are represented in Figure 5. The number on each arc represents the length, in miles, of the corresponding road.

The table below shows the shortest distances, in miles, between the nine towns.

ABCDEFGHJ
A–345131792085561
B34–17654554422127
C5117–822871592210
D316582–8722238692
E79452887–65873018
F2054712265–287581
G84259238728–6369
H55212286307563–12
J6127109218816912–

Table of shortest distances

A route is needed that minimises the total distance required to traverse each road at least once.

The route must start at F and finish at J.

(a)
(i) By considering the pairings of all relevant nodes, find the roads that would need to be traversed twice.
(ii) State the total length of this route. (5)
(b) Starting at A, use Prim’s algorithm to find the minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree. (3)

Pete needs to visit all nine towns, starting and finishing in the same town, and wishes to minimise the total distance he travels.

(c) Starting at G, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Pete’s route. Write down the route that gives this upper bound. (2)
(d) By deleting G and all of its arcs, find a lower bound for the length of Pete’s route. (2)

Pete decides to take the route he found in (c).

(e) Interpret the route in terms of the actual towns visited. (1)
‹ Previous3 of 31 in Minimum Spanning TreesNext ›