EXM.2.AHL.TZ0.17

pestleMathematicsAIHLPaper 2EXM· ahl-3-16-tree-and-cycle-algorithms-chinese-postman-travelling-salesmansource ↗

A canal system divides a city into six land masses connected by fifteen bridges, as shown in the diagram below.

State with reasons whether or not this graph has

Draw a graph to represent this map.

[2]

Write down the adjacency matrix of the graph.

[2]

List the degrees of each of the vertices.

[2]

an Eulerian circuit.

[2]

d.i.

an Eulerian trail.

[2]

d.ii.

Find the number of walks of length 4 from E to F.

[2]

Markscheme / solution

[2 marks]

M = $\begin{array}{*{20}{c}} {} \\ {\text{A}} \\ {\text{B}} \\ {\text{C}} \\ {\text{D}} \\ {\text{E}} \\ {\text{F}} \end{array}\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\text{A}}&{\text{B}}&{\text{C}}&{\text{D}}&{\text{E}}&{\text{F}} \end{array}} \\ {\left( {\begin{array}{*{20}{c}} 0&1&2&1&2&2 \\ 1&0&0&0&1&2 \\ 2&0&0&1&0&1 \\ 1&0&1&0&1&0 \\ 2&1&0&1&0&1 \\ 2&2&1&0&1&0 \end{array}} \right)} \end{array}$ A2

Note: Award A1 for one error or omission, A0 for more than one error or omission. Two symmetrical errors count as one error.

[2 marks]

A B C D E F

(8, 4 4, 3 5, 6) A2

Note: Award no more than A1 for one error, A0 for more than one error.

[2 marks]

no, because there are odd vertices M1A1

[2 marks]

d.i.

yes, because there are exactly two odd vertices M1A1

[2 marks]

d.ii.

M⁴ = $\begin{array}{*{20}{c}} {} \\ {\text{A}} \\ {\text{B}} \\ {\text{C}} \\ {\text{D}} \\ {\text{E}} \\ {\text{F}} \end{array}\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\text{A}}&{}&{\text{B}}&{}&{\text{C}}&{}&{\text{D}}&{}&{\text{E}}&{}&{\text{F}} \end{array}} \\ {\left( {\begin{array}{*{20}{c}} {309\,}&{174}&{140}&{118}&{170}&{214} \\ {174}&{117}&{106}&{70}&{122}&{132} \\ {140\,}&{106}&{117}&{66}&{134}&{138} \\ {118}&{70}&{66}&{53}&{80}&{102} \\ {170}&{122}&{134}&{80}&{157}&{170} \\ {214}&{132}&{138}&{102}&{170}&{213} \end{array}} \right)} \end{array}$ (M1)A1

number of walks of length 4 is 170

Note: The complete matrix need not be shown. Only one of the FE has to be shown.

[2 marks]

Examiners’ report

[N/A]

d.i.

[N/A]

d.ii.

[N/A]