Write down a Hamiltonian cycle in $W$.

Use Prim’s algorithm, starting at vertex $\text{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.

Hence, for the case where $x<9$, find a lower bound for Daniel’s travel time, in terms of $x$.

$p$.

$q$.

$r$.

Use the nearest neighbour algorithm to find two possible cycles.

Find the best upper bound for Daniel’s travel time.

Find the least value of $x$ for which the edge $\text{AF}$ will definitely not be used by Daniel.

Hence state the value of the upper bound for Daniel’s travel time for the value of $x$ found in part (e)(i).

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 $\text{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.

e.g. $\text{ABCDEGHFA}$            A1

Note: Accept any other correct answers starting at any vertex.

[1 mark]

$7$ vertices, so $6$ edges required for MST                       (M1)

Note: To award (M1), their $6$ edges should not form a cycle.

            M1A1A1

Note: Award M1 for the first three edges in correct order, A1 for $\text{BH}$ in correct order and A1 for all of the edges correct.

weight of MST $=33$            A1

Note: The final A1 can be awarded independently of previous marks.

[5 marks]

lower bound $=33+3+x$                      (M1)

$=36+x$            A1

[2 marks]

$p=13$           A1

[1 mark]

$q=17$           A1

[1 mark]

$r=14$           A1

[1 mark]

attempt to use nearest neighbour algorithm                      (M1)

any two correct cycles from
$\text{ABCDEGHFA, AFGHBCDE(F)A, AB(A)FGHCDE(F)A}$           A1A1

Note: Bracketed vertices may be omitted in candidate’s answer.
Award M1A0A1 for candidates who list two correct sequences of vertices, but omit the final vertex $\text{A}$.

[3 marks]

use $\text{ABCDEGHFA}$  OR  their shortest cycle from (d)(i)                   (M1)

upper bound $=43$           A1

[2 marks]

cycle starts: $\text{ABCDEGHF}$

return to $\text{A}$ has two options, $\text{FA}=18$ or $x$                   (M1)

hence least value of $x=19$           A1

[2 marks]

upper bound $=58$           A2

[2 marks]

recognition that edges will be repeated / there are odd vertices           (M1)

$\text{BH}+\text{DG}=21, \text{BD}+\text{GH}=15, \text{BG}+\text{DH}=21$  OR  $18+x$           A1

recognizing $\text{BD}$ and $\text{GH}$ is lowest weight and is repeated           (M1)

solution to CPP $=107+x$           A1

$x=13$           A1

Note: Award M1A0M0A1A1 if only pairing $\text{BD}$ and $\text{GH}$ is considered, leading to a correct answer.

[5 marks]

Mostly well done, although some candidates wrote down a path instead of a cycle and some candidates wrote a cycle that did not include all the vertices.

Many candidates could apply the algorithm correctly to find the weight of the minimum spanning tree. A common misconception was selecting the shortest edge adjacent to the previous vertex, instead of selecting the shortest edge adjacent to the existing tree. This approach will not necessarily find the minimum spanning tree. A small number of candidates found the correct minimum spanning tree, but did not show evidence of using Prim’s algorithm, which only received partial credit; where a method/algorithm is explicit in the question, working must be seen to demonstrate that approach. Part (b)(ii) was also answered reasonably well, however several candidates did not read the instruction to give their answer in terms of $\mathrm{x}$, instead choosing a specific value.

Many candidates could apply the algorithm correctly to find the weight of the minimum spanning tree. A common misconception was selecting the shortest edge adjacent to the previous vertex, instead of selecting the shortest edge adjacent to the existing tree. This approach will not necessarily find the minimum spanning tree. A small number of candidates found the correct minimum spanning tree, but did not show evidence of using Prim’s algorithm, which only received partial credit; where a method/algorithm is explicit in the question, working must be seen to demonstrate that approach. Part (b)(ii) was also answered reasonably well, however several candidates did not read the instruction to give their answer in terms of $\mathrm{x}$, instead choosing a specific value.

Mostly well-answered.

Mostly well-answered.

Mostly well-answered.

Many candidates could successfully apply the nearest neighbour algorithm to find a correct cycle, but some made errors finding a second one. Part (ii) was done reasonably well, with many candidates either giving the correct answer or gaining follow-through marks for selecting their shortest cycle from part (d)(i). A small number of candidates incorrectly chose their longest cycle.

Many candidates could successfully apply the nearest neighbour algorithm to find a correct cycle, but some made errors finding a second one. Part (ii) was done reasonably well, with many candidates either giving the correct answer or gaining follow-through marks for selecting their shortest cycle from part (d)(i). A small number of candidates incorrectly chose their longest cycle.

This question had a mixed response. Some candidates used the table or the graph to realize that the two choices to get from $\mathrm{A}$ to $\mathrm{F}$ are either $18$ or $\mathrm{x}$. Some incorrectly stated $\mathrm{x}=18$. These candidates often achieved success in part (e)(ii), making the connection to their previous answer in part (d).

This question had a mixed response. Some candidates used the table or the graph to realize that the two choices to get from $\mathrm{A}$ to $\mathrm{F}$ are either $18$ or $\mathrm{x}$. Some incorrectly stated $\mathrm{x}=18$. These candidates often achieved success in part (e)(ii), making the connection to their previous answer in part (d).

A surprising number of candidates did not seem to realize this was an application of the Chinese Postman Problem and simply equated the given total weight to $120$ minutes. Not only does this show a lack of understanding of the problem, but it also showed a lack of appreciation of the amount of work required to answer a 5 mark question. Out of the many candidates who recognized the need to repeat edges connecting the odd vertices, some did not show complete working to explain why they chose to connect $\mathrm{BD}$ and $\mathrm{GH}$, only gaining partial credit.