User interface language: English | Español

Date May 2012 Marks available 3 Reference code 12M.3dm.hl.TZ0.3
Level HL only Paper Paper 3 Discrete mathematics Time zone TZ0
Command term List Question number 3 Adapted from N/A

Question

The graph G has adjacency matrix M given below.


Draw the graph G .

[2]
a.

What information about G is contained in the diagonal elements of M\(^2\) ?

[1]
b.

List the trails of length 4 starting at A and ending at C.

[3]
d.

Markscheme

     A2

 

Note: Award A1 if only one error, A0 for two or more.

 

[2 marks]

a.

the (k, k) element of M\(^2\) is the number of vertices directly connected to vertex k     A1 

Note: Accept comment about the number of walks of length 2, in which the initial and final vertices coincide.

 

[1 mark]

b.

the trails of length 4 are ABEDC, AFEDC, AFEBC     A1A1A1 

Note: A1A1A1 for three correct with no additions; A1A1A0 for all correct, but with additions; A1A0A0 for two correct with or without additions.

 

[3 marks]

d.

Examiners report

Parts (a) and (c) were generally correctly answered. In part (b), a minority of candidates failed to mention that the starting and end points had to coincide. A large number of candidates gave all walks (trails were asked for) – an unnecessary loss of marks.

a.

Parts (a) and (c) were generally correctly answered. In part (b), a minority of candidates failed to mention that the starting and end points had to coincide. A large number of candidates gave all walks (trails were asked for) – an unnecessary loss of marks.

b.

Parts (a) and (c) were generally correctly answered. In part (b), a minority of candidates failed to mention that the starting and end points had to coincide. A large number of candidates gave all walks (trails were asked for) – an unnecessary loss of marks.

d.

Syllabus sections

Topic 10 - Option: Discrete mathematics » 10.8 » Walks, trails, paths, circuits, cycles.

View options