IB Questionbank

User interface language: English | Español

Date	May 2022	Marks available	2	Reference code	22M.1.AHL.TZ2.6
Level	Additional Higher Level	Paper	Paper 1	Time zone	Time zone 2
Command term	Write down	Question number	6	Adapted from	N/A

Question

Consider the following directed network.

Write down the adjacency matrix for this network.

[2]

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

[3]

Markscheme

$⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ \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} ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠$ $(\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$ $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]

Syllabus sections

Topic 3—Geometry and trigonometry » AHL 3.15—Adjacency matrices and tables

22M.3.AHL.TZ1.2f.i:
Find which town is last to be polluted. Justify your answer.
22M.3.AHL.TZ1.2f.ii:
Write down the number of days it takes for the pollution to reach the last town.
22M.1.AHL.TZ2.6b:
Determine the number of different walks of length $5$ that start and end at the same vertex.
21N.3.AHL.TZ0.1c.ii:
$q$ .
21N.3.AHL.TZ0.1c.i:
$p$ .
21N.3.AHL.TZ0.1d.i:
Use the nearest neighbour algorithm to find two possible cycles.
21N.3.AHL.TZ0.1e.ii:
Hence state the value of the upper bound for Daniel’s travel time for the value of $x$ found in part (e)(i).
21N.3.AHL.TZ0.1b.i:
Use Prim’s algorithm, starting at vertex $B$ , to find the weight of the minimum spanning tree of the remaining graph. You should indicate clearly the order in which the algorithm selects each edge.
21N.3.AHL.TZ0.1e.i:
Find the least value of $x$ for which the edge $AF$ will definitely not be used by Daniel.
21N.3.AHL.TZ0.1b.ii:
Hence, for the case where $x < 9$ , find a lower bound for Daniel’s travel time, in terms of $x$ .
EXM.1.AHL.TZ0.24a.ii:
Find the number of distinct walks of length 4 beginning and ending at A.
EXM.1.AHL.TZ0.24a.i:
Write down the adjacency matrix for G.
21M.1.AHL.TZ1.16a:
Write down the adjacency matrix, $M$ , for this graph.
21M.1.AHL.TZ1.16b:
Find the number of ways that the ant can start at the vertex $A$ , and walk along exactly $6$ edges to return to $A$ .
21N.3.AHL.TZ0.1c.iii:
$r$ .
21N.3.AHL.TZ0.1d.ii:
Find the best upper bound for Daniel’s travel time.
21N.3.AHL.TZ0.1a:
Write down a Hamiltonian cycle in $W$ .
21N.3.AHL.TZ0.1f:
The tourist office in the city has received complaints about the lack of cleanliness of some routes between the attractions. Corinne, the office manager, decides to inspect all the routes between all the attractions, starting and finishing at $H$ . The sum of the weights of all the edges in graph $W$ is $(92 + x)$ .

Corinne inspects all the routes as quickly as possible and takes $2$ hours.

Find the value of $x$ during Corinne’s inspection.

Topic 3—Geometry and trigonometry

Question

Markscheme

Examiners report

Syllabus sections

View options