D2 June 2010 Q1

EdexcelOld spec11 marksTravelling Salesman

1. The table below shows the least costs, in pounds, of travelling between six cities, A, B, C, D, E and F.

Vicky must visit each city at least once. She will start and finish at A and wishes to minimise the total cost.

(a) Use Prim’s algorithm, starting at A, to find a minimum spanning tree for this network. (2)

(b) Use your answer to part (a) to help you calculate an initial upper bound for the length of Vicky’s route. (1)

(c) Show that there are two nearest neighbour routes that start from A. You must make your routes and their lengths clear. (3)

(d) State the best upper bound from your answers to (b) and (c). (1)

(e) Starting by deleting A, and all of its arcs, find a lower bound for the route length. (4)

Scheme	Marks
	M1 A1
	(2)

Scheme	Marks
Minimum Spanning tree length 93, so upper bound is £186	B1ft
	(1)

Mark scheme (c)

1M1: One Nearest Neighbour each vertex visited at least once (condone lack of return to start)

1A1: One correct route and length CAO – must return to start.

2A1: Second correct route and length CAO – must return to start.