Find $\text{AF}$.

Find the cost per metre of installing this cable.

State why the cost for installing the cable between $\text{A}$ and $\text{F}$ would be higher than between the other buildings.

By using Kruskal’s algorithm, find the minimum spanning tree for $S$, showing clearly the order in which edges are added.

Hence find the minimum installation cost for the cables that would allow all the buildings to be part of the computer network.

State why a path that forms a Hamiltonian cycle does not always form an Eulerian circuit.

Starting at $\text{D}$, use the nearest neighbour algorithm to find the upper bound for the installation cost of a computer network in the form of a Hamiltonian cycle.

Note: Although the graph is not complete, in this instance it is not necessary to form a table of least distances.

By deleting $\text{D}$, use the deleted vertex algorithm to find the lower bound for the installation cost of the cycle.

Show that Jonas’s network satisfies the requirement of there being less than a $2\%$ probability of the network failing after a power surge.

${\text{AF}}^2=89.2^2+104.9^2-2\left(89.2\right)\left(104.9\right)\cos 83$         (M1)(A1)

Note: Award (M1) for substitution into the cosine rule and (A1) for correct substitution.

$\text{AF}=129 \text{m} \left(129.150\dots \right)$           A1

[3 marks]

$21310÷129.150\dots$         (M1)

$\$165$           A1

[2 marks]

any reasonable statement referring to the lake         R1

(eg. there is a lake between $\text{A}$ and $\text{F}$, the cables would need to be installed under/over/around the lake, special waterproof cables are needed for lake, etc.)

[1 mark]

edges (or weights) are chosen in the order

$\text{CE} \left(8239\right)$
$\text{DG} \left(8668\right)$
$\text{BD } \left(8778\right)$
$\text{AB} \left(8811\right)$
$\text{DE } \left(8833\right)$
$\text{EH} \left(9251\right)$
$\text{DF} \left(11 539\right)$               A1A1A1

Note: Award A1 for the first two edges chosen in the correct order. Award A1A1 for the first six edges chosen in the correct order. Award A1A1A1 for all seven edges chosen in the correct order. Accept a diagram as an answer, provided the order of edges is communicated.

[3 marks]

Finding the sum of the weights of their edges               (M1)
$8239+8668+8778+8811+8833+9251+11539$

total cost $=\$64119$               A1

[2 marks]

a Hamiltonian cycle is not always an Eulerian circuit as it does not have to include all edges of the graph (only all vertices)             R1

[1 mark]

edges (or weights) are chosen in the order

$\text{DG} \left(8668\right)$
$\text{GH} \left(9603\right)$
$\text{HE} \left(9251\right)$
$\text{EC} \left(8239\right)$
$\text{CB} \left(13 156\right)$
$\text{BA} \left(8811\right)$
$\text{AF} \left(21 310\right)$
$\text{FD} \left(11 539\right)$              A1A1A1

Note: Award A1 for the first two edges chosen in the correct order. Award A1A1 for the first five edges chosen in the correct order. Award A1A1A1 for all eight edges chosen in the correct order. Accept a diagram as an answer, provided the order of edges is communicated.

finding the sum of the weights of their edges                (M1)
$8668+9603+9251+8239+13156+8811+21310+11539$

upper bound $=\$90 577$              A1

[5 marks]

attempt to find MST after deleting vertex D         (M1)
these edges (or weights) (in any order)

$\text{CE} \left(8239\right)$
$\text{AB} \left(8811\right)$
$\text{EH} \left(9251\right)$
$\text{GH} \left(9603\right)$
$\text{BE} \left(10 153\right)$
$\text{FG} \left(12 606\right)$              A1

Note: Prim’s or Kruskal’s algorithm could be used at this stage.

reconnect $\text{D}$ to MST with two different edges         (M1)

$\text{DG} \left(8668\right)$
$\text{BD} \left(8778\right)$              A1

Note: This A1 is independent of the first A mark and can be awarded if both $\text{DG}$ and $\text{BD}$ are chosen to reconnect $\text{D}$ to the MST, even if the MST is incorrect.

finding the sum of the weights of their edges              (M1)
$8239+8811+9251+9603+10153+12606+8668+8778$

Note: For candidates with an incorrect MST or no MST, the weights of at least seven of the edges being summed (two of which must connect to $\text{D}$) must be shown to award this (M1).

lower bound $=\$76 109$              A1

[6 marks]

METHOD 1

recognition of a binomial distribution         (M1)
$X~\text{B}\left(2, 0.014\right)$

finding the probability that a cable fails (at least one of its connections fails)
$\text{P}\left(X>0\right)=0.027804$  OR  $1-\text{P}\left(X=0\right)=0.027804$             A1

recognition that two cables must fail for the network to go offline         M1

recognition of binomial distribution for network, $Y~\text{B}\left(8, 0.027804\right)$         (M1)

$\text{P}\left(Y\ge 2\right)=0.0194 \left(0.0193602\dots \right)$  OR  $1-\text{P}\left(Y<2\right)=0.0194 \left(0.0193602\dots \right)$             A1

therefore, the diagram satisfies the requirement since $1.94\%<2\%$             AG

Note: Evidence of binomial distribution may be seen as combinations.

METHOD 2

recognition of a binomial distribution          (M1)
$X~\text{B}\left(16, 0.014\right)$

finding the probability that at least two connections fail
$\text{P}\left(X\ge 2\right)=0.0206473\dots$  OR  $1-\text{P}\left(X<2\right)=0.0206473\dots$             A1

recognition that the previous answer is an overestimate          M1

finding probability of two ends of the same cable failing, $F~\text{B}\left(2, 0.014\right)$,
and the ends of the other $14$ cables not failing, $S~\text{B}\left(14, 0.014\right)$
$\text{P}\left(F=2\right)\times \text{P}\left(S=0\right)=0.0000160891\dots$             (A1)

$0.0000160891\dots \times 8=0.00128713...$

$0.0206473\dots -0.00128713\dots =0.0194 \left(0.0193602\dots \right)$             A1

therefore, the diagram satisfies the requirement since $1.94\%<2\%$             AG

METHOD 3

recognition of a binomial distribution          M1
$X~\text{B}\left(16, 0.014\right)$

finding the probability that the network remains secure if $0$ or $1$ connections fail or if $2$ connections fail provided that the second failed connection occurs at the other end of the cable with the first failure         (M1)

$\text{P}$(remains secure) $=\text{P}\left(X\le 1\right)+\frac{1}{15}\times \text{P}\left(X=2\right)$             A1

$=0.9806397625$             A1

$\text{P}$(network fails) $=1-0.9806397625=0.0194 \left(0.0193602\dots \right)$              A1

therefore, the diagram satisfies the requirement since $1.94\%<2\%$             AG

METHOD 4

$\text{P}$(network failing)

$=1-\text{P}\left(0 \text{connections failing}\right)-\text{P}\left(1 \text{connection failing}\right)-\text{P}\left(2 \text{connections on the same cable failing}\right)$          M1

$=1-0.{986}^{16}-{}_{16}C_1\times 0.014\times 0.{986}^{15}-{}_{8}C_1\times 0.{014}^2\times 0.{986}^{14}$              A1A1A1

Note: Award A1 for each of 2^nd, 3^rd and last terms.

$=0.0194 \left(0.0193602\dots \right)$              A1

therefore, the diagram satisfies the requirement since $1.94\%<2\%$             AG

[5 marks]

This question part was intended to be an easy introduction to help candidates begin working with the larger story and most candidates handled it well. However, it was surprisingly common for a candidate to correctly choose the cosine rule and to make the correct substitutions into the formula but then arrive at an incorrect answer. The frequency of this mistake suggests that candidates were either making simple entry mistakes into their GDC or forgetting to ensure that their GDC was set to degrees rather than radians.

(b) and (c) Most candidates were able to gain the three marks available.

(d), (f) and (g) These three question parts required candidates to demonstrate their ability to carry out graph theory algorithms. Kruskal’s algorithm was split into two different question parts to guide candidates to show their work. As a result, many were able to score well in part (d)(ii) either from having the correct MST or from “follow through” marks from an incorrect MST. However, without this guidance in 2(f) and 2(g), many candidates did a poor job of showing the process they were using to apply the algorithms. The candidates that scored well were detailed in showing the order of how edges were selected and how they were being summed to arrive at the final answers. Although “follow through” within the problem was not available for the final answer in parts 2(f) and 2(g), many candidates missed the opportunity to gain the final method mark in both parts by not fully showing the process they used.

Many candidates were able to state the definitions of Hamiltonian cycles and Eulerian circuits. However, the question was not asking for definitions but rather a distinct conclusion of why a Hamiltonian cycle is not always an Eulerian circuit. Disappointingly, many incorrect answers contained five or more lines or writing that may have used up exam time that could have been devoted to other question parts. Another common mistake seen here was candidates incorrectly trying to state a reason based on the number of odd vertices.

This question was very challenging for almost all the candidates. Although there were several different methods that candidates could have used to answer this question, most candidates were only able to gain one or two marks here. Many candidates did recognize that something binomial was needed, but few knew how to setup the correct parameters for the distribution.