EXM.1.AHL.TZ0.24

pestleMathematicsAIHLPaper 1EXM· ahl-3-15-adjacency-matrices-and-tables, ahl-3-16-tree-and-cycle-algorithms-chinese-postman-travelling-salesmansource ↗

The above diagram shows the weighted graph G.

Write down the adjacency matrix for G.

[1]

a.i.

Find the number of distinct walks of length 4 beginning and ending at A.

[3]

a.ii.

Starting at A, use Prim’s algorithm to find and draw the minimum spanning tree for G.

Your solution should indicate clearly the way in which the tree is constructed.

[5]

Markscheme / solution

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

[1 mark]

a.i.

We require the (A, A) element of M⁴ which is 13. M1A2

[3 marks]

a.ii.

A1A1A1A1A1

[5 marks]

Examiners’ report

[N/A]

a.i.

[N/A]

a.ii.

[N/A]