User interface language: English | Español

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

Question

The cost adjacency matrix for the complete graph K6 is given below.

It represents the distances in kilometres along dusty tracks connecting villages on an island. Find the minimum spanning tree for this graph; in all 3 cases state the order in which the edges are added.

It is desired to tarmac some of these tracks so that it is possible to walk from any village to any other village walking entirely on tarmac.

Briefly explain the two differences in the application of Prim’s and Kruskal’s algorithms for finding a minimum spanning tree in a weighted connected graph.

[2]
a.

Using Kruskal’s algorithm.

[2]
b.i.

Using Prim’s algorithm starting at vertex A.

[2]
b.ii.

Using Prim’s algorithm starting at vertex F.

[2]
b.iii.

State the total minimum length of the tracks that have to be tarmacked.

[2]
c.i.

Sketch the tracks that are to be tarmacked.

[2]
c.ii.

Markscheme

In Prim’s algorithm you start at a particular (given) vertex, whereas in Kruskal’s you start with the smallest edge.        A1

In Prim’s as smallest edges are added (never creating a circuit) the created graph always remains connected, whereas in Kruskal’s this requirement to always be connected is not necessary.        A1

[2 marks]

a.

Edges added in the order

AB    EF    AC    AD    AE                  A1A1

[note A1 for the first 2 edges A1 for other 3]

[2 marks]

b.i.

Edges added in the order

AB    AC    AD    AE    EF                  A1A1

[note A1 for the first 2 edges A1 for other 3]

[2 marks]

b.ii.

Edges added in the order

FE    AE    AB    AC    AD                  A1A1

[note A1 for the first 2 edges A1 for other 3]

[2 marks]

b.iii.

1 + 2 + 3 + 4 + 5 = 15                  M1A1

[2 marks]

c.i.

               A2

[2 marks]

c.ii.

Examiners report

[N/A]
a.
[N/A]
b.i.
[N/A]
b.ii.
[N/A]
b.iii.
[N/A]
c.i.
[N/A]
c.ii.

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