22M.1.AHL.TZ2.6

pestleMathematicsAIHLPaper 122M· ahl-3-15-adjacency-matrices-and-tablessource ↗

Consider the following directed network.

Write down the adjacency matrix for this network.

[2]

Determine the number of different walks of length $5$ that start and end at the same vertex.

[3]

Markscheme / solution

$(\begin{matrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \end{matrix})$ A2

Note: Award A2 for the transposed matrix. Presentation in markscheme assumes columns/rows ordered A-E; accept a matrix with rows and/or columns in a different order only if appropriately communicated. Do not FT from part (a) into part (b).

[2 marks]

raising their matrix to a power of $5$ (M1)

$M^{5} = (\begin{matrix} 17 & 9 & 2 & 3 & 5 \\ 17 & 10 & 3 & 4 & 4 \\ 13 & 6 & 2 & 2 & 4 \\ 8 & 5 & 1 & 2 & 2 \\ 18 & 11 & 2 & 4 & 5 \end{matrix})$ (A1)

Note: The numbers along the diagonal are sufficient to award M1A1.

(the required number is $17 + 10 + 2 + 2 + 5 =$ ) $36$ A1

[3 marks]

Examiners’ report

This was well answered by the majority of candidates with most writing down the correct adjacency matrix and then raising it to the power 5.

[N/A]