IB Questionbank

User interface language: English | Español

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

Question

The adjacency matrix of the graph G, with vertices P, Q, R, S, T is given by:

$\begin{matrix} P Q R S T \end{matrix} \begin{matrix} \begin{matrix} P & Q & R & S & T \end{matrix} ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 0 & 2 & 1 & 1 & 0 2 & 1 & 1 & 1 & 0 1 & 1 & 1 & 0 & 2 1 & 1 & 0 & 0 & 0 0 & 0 & 2 & 0 & 0 \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ \end{matrix}$ $\begin{array}{*{20}{c}} {} \\ {\text{P}} \\ {\text{Q}} \\ {\text{R}} \\ {\text{S}} \\ {\text{T}} \end{array}\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\text{P}}&{\text{Q}}&{\text{R}}&{\text{S}}&{\text{T}} \end{array}} \\ {\left( {\begin{array}{*{20}{c}} 0&2&1&1&0 \\ 2&1&1&1&0 \\ 1&1&1&0&2 \\ 1&1&0&0&0 \\ 0&0&2&0&0 \end{array}} \right)} \end{array}$

Draw the graph of G.

[3]

Define an Eulerian circuit.

[1]

b.i.

Write down an Eulerian circuit in G starting at P.

[2]

b.ii.

Define a Hamiltonian cycle.

[2]

c.i.

Explain why it is not possible to have a Hamiltonian cycle in G.

[3]

c.ii.

Find the number of walks of length 5 from P to Q.

[4]

d.i.

Which pairs of distinct vertices have more than 15 walks of length 3 between them?

[4]

d.ii.

Markscheme

Note: Award A2 for one missing or misplaced edge,

A1 for two missing or misplaced edges.

[3 marks]

an Eulerian circuit is one that contains every edge of the graph exactly once A1

[1 mark]

b.i.

a possible Eulerian circuit is

P → Q → S → P → Q → Q → R → T → R → R → P A2

[2 marks]

b.ii.

a Hamiltonian cycle passes through each vertex of the graph A1

exactly once A1

[2 marks]

c.i.

to pass through T, you must have come from R and must return to R. R3

hence there is no Hamiltonian cycle

[3 marks]

c.ii.

using the adjacency matrix A = $⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 0 & 2 & 1 & 1 & 0 2 & 1 & 1 & 1 & 0 1 & 1 & 1 & 0 & 2 1 & 1 & 0 & 0 & 0 0 & 0 & 2 & 0 & 0 \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠$ ${\left( {\begin{array}{*{20}{c}} 0&2&1&1&0 \\ 2&1&1&1&0 \\ 1&1&1&0&2 \\ 1&1&0&0&0 \\ 0&0&2&0&0 \end{array}} \right)}$ , (M1)

we need the entry in the first row second column of the matrix A⁵ (M1)

A⁵ = $⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 245 & 309 & 274 & 143 & 126 309 & 363 & 322 & 168 & 156 274 & 322 & 295 & 141 & 164 143 & 168 & 141 & 77 & 72 126 & 156 & 164 & 72 & 72 \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠$ $\left( {\begin{array}{*{20}{c}} {245}&{309}&{274}&{143}&{126} \\ {309}&{363}&{322}&{168}&{156} \\ {274}&{322}&{295}&{141}&{164} \\ {143}&{168}&{141}&{77}&{72} \\ {126}&{156}&{164}&{72}&{72} \end{array}} \right)$ (A1)

hence there are 309 ways A1

[4 marks]

d.i.

A³ = $⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 13 & 21 & 17 & 10 & 6 21 & 22 & 19 & 11 & 8 17 & 19 & 18 & 7 & 14 10 & 11 & 7 & 5 & 4 6 & 8 & 14 & 4 & 4 \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠$ $\left( {\begin{array}{*{20}{c}} {13}&{21}&{17}&{10}&6 \\ {21}&{22}&{19}&{11}&8 \\ {17}&{19}&{18}&7&{14} \\ {10}&{11}&7&5&4 \\ 6&8&{14}&4&4 \end{array}} \right)$ (M1)