User interface language: English | Español

Date May Example question Marks available 2 Reference code EXM.1.AHL.TZ0.1
Level Additional Higher Level Paper Paper 1 Time zone Time zone 0
Command term Find Question number 1 Adapted from N/A

Question

The cost adjacency matrix below represents the distance in kilometres, along routes between bus stations.

All the values in the matrix are positive, distinct integers.

It is decided to electrify some of the routes, so that it will be possible to travel from any station to any other station solely on electrified routes. In order to achieve this with a minimal total length of electrified routes, Prim’s algorithm for a minimal spanning tree is used, starting at vertex A.

The algorithm adds the edges in the following order:

AB    AC    CD    DE.

There is only one minimal spanning tree.

Find with a reason, the value of x .

[2]
a.

If the total length of the minimal spanning tree is 14, find the value of s .

[2]
b.

Hence, state, with a reason, what can be deduced about the values of p , q , r .

[2]
c.

Markscheme

AB must be the length of the smallest edge from A so  x = 1 .      R1A1

[2 marks]

a.

1 + 2 + 3 + s = 14 s = 8      M1A1

[2 marks]

b.

The last minimal edge chosen must connect to E , so since s = 8 each of  p q r must be ≥ 9.    R1A1

[2 marks]

c.

Examiners report

[N/A]
a.
[N/A]
b.
[N/A]
c.

Syllabus sections

Topic 3—Geometry and trigonometry » AHL 3.16—Tree and cycle algorithms, Chinese postman, travelling salesman
Show 87 related questions
Topic 3—Geometry and trigonometry

View options