User interface language: English | Español

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

Question

Let G be a weighted graph with 6 vertices L, M, N, P, Q, and R. The weight of the edges joining the vertices is given in the table below:

For example the weight of the edge joining the vertices L and N is 3.

Use Prim’s algorithm to draw a minimum spanning tree starting at M.

[5]
a.

What is the total weight of the tree?

[1]
b.

Markscheme

M → Q         (M1)

Q → L          (A1)

M → P          (A1)

P → N → R    (A1)

          (A1)

Note: There are other correct answers.

[5 marks]

a.

The total weight is 2 + 1 + 3 + 2 + 3 = 11.   (A1)

[1 mark]

b.

Examiners report

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

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