SPM.2.AHL.TZ0.5

pestleMathematicsAIHLPaper 2SPM· ahl-3-16-tree-and-cycle-algorithms-chinese-postman-travelling-salesmansource ↗

The following table shows the costs in US dollars (US$) of direct flights between six cities. Blank cells indicate no direct flights. The rows represent the departure cities. The columns represent the destination cities.

The following table shows the least cost to travel between the cities.

A travelling salesman has to visit each of the cities, starting and finishing at city A.

Show the direct flights between the cities as a graph.

[2]

Write down the adjacency matrix for this graph.

[2]

Using your answer to part (b), find the number of different ways to travel from and return to city A in exactly 6 flights.

[2]

State whether or not it is possible to travel from and return to city A in exactly 6 flights, having visited each of the other 5 cities exactly once. Justify your answer.

[2]

Find the values of $a$ and $b$ .

[2]

Use the nearest neighbour algorithm to find an upper bound for the cost of the trip.

[3]

By deleting vertex A, use the deleted vertex algorithm to find a lower bound for the cost of the trip.

[4]

Markscheme / solution

[2 marks]

attempt to form an adjacency matrix M1

$\left( {\begin{array}{*{20}{c}} 0&1&1&0&0&0 \\ 1&0&1&1&1&0 \\ 1&1&0&0&0&0 \\ 0&1&0&0&1&1 \\ 0&1&0&1&0&1 \\ 0&0&0&1&1&0 \end{array}} \right)$ A1

[2 marks]

raising the matrix to the power six (M1)

50 A1

[2 marks]

not possible A1

because you must pass through B twice R1

Note: Do not award A1R0.

[2 marks]

$a = 230$ , $b = 340$ A1A1

[2 marks]

A → B → D → E → F → C → A (M1)

90 + 70 + 100 + 210 + 330 + 150 (A1)

(US$) 950 A1

[3 marks]

finding weight of minimum spanning tree M1

70 + 80 + 100 + 180 = (US$) 430 A1

adding in two edges of minimum weight M1

430 + 90 + 150 = (US$) 670 A1

[4 marks]

Examiners’ report

[N/A]