## Question

A graph *G* with vertices A, B, C, D, E has the following cost adjacency table.

\[\begin{array}{*{20}{c|ccccc}}

{}&{\text{A}}&{\text{B}}&{\text{C}}&{\text{D}}&{\text{E}} \\

\hline

{\text{A}}& – &{12}&{10}&{17}&{19} \\

{\text{B}}&{12}& – &{13}&{20}&{11} \\

{\text{C}}&{10}&{13}& – &{16}&{14} \\

{\text{D}}&{17}&{20}&{16}& – &{15} \\

{\text{E}}&{19}&{11}&{14}&{15}& –

\end{array}\]

(a) (i) Use Kruskal’s algorithm to find and draw the minimum spanning tree for *G*.

(ii) The graph *H* is formed from *G* by removing the vertex D and all the edges connected to D. Draw the minimum spanning tree for *H* and use it to find a lower bound for the travelling salesman problem for *G*.

(b) Show that 80 is an upper bound for this travelling salesman problem.

**Answer/Explanation**

## Markscheme

(a) (i) the edges are joined in the order

AC

BE

AB

ED *A2*

*A1*

**Note:** Final ** A1** independent of the previous

**.**

*A2*

(ii)

*A1*

the weight of this spanning tree is 33 *A1*

to find a lower bound for the travelling salesman problem, we add to that the two smallest weights of edges to D, *i.e.* 15 +16, giving 64 *M1A1*

*[7 marks]*

* *

(b) an upper bound is the weight of any Hamiltonian cycle, *e.g.* ABCDEA has weight 75 so 80 is certainly an upper bound *M1A1*

*[2 marks]*

*Total [9 marks]*

## Examiners report

Part (a) was well done by many candidates although some candidates simply drew the minimum spanning tree in (i) without indicating the use of Kruskal’s Algorithm. It is important to stress to candidates that, as indicated in the rubric at the top of Page 2, answers must be supported by working and/or explanations. Part (b) caused problems for some candidates who obtained the unhelpful upper bound of 96 by doubling the weight of the minimum spanning tree. It is useful to note that the weight of any Hamiltonian cycle is an upper bound and in this case it was fairly easy to find such a cycle with weight less than or equal to 80.

## Question

The complete graph *H* has the following cost adjacency matrix.

Consider the travelling salesman problem for *H* .

By first finding a minimum spanning tree on the subgraph of *H* formed by deleting vertex A and all edges connected to A, find a lower bound for this problem.

Find the total weight of the cycle ADCBEA.

What do you conclude from your results?

**Answer/Explanation**

## Markscheme

using any method, the minimum spanning tree is *(M1)*

* *

*A2*

**Note:** Accept MST = {BC, EC, DC} or {BC, EB, DC}

**Note:** In graph, line CE may be replaced by BE.

lower bound = weight of minimum spanning tree + 2 smallest weights connected to A *(M1)*

= 11 + 13 + 14 + 10 + 15 = 63 *A1*

*[5 marks]*

weight of ADCBEA = 10 + 14 + 11 + 13 + 15 = 63 *A1*

*[1 mark]*

the conclusion is that ADCBEA gives a solution to the travelling salesman problem *A1*

*[1 mark]*

## Examiners report

This question was generally well answered although some candidates failed to realise the significance of the equality of the upper and lower bounds.

This question was generally well answered although some candidates failed to realise the significance of the equality of the upper and lower bounds.

This question was generally well answered although some candidates failed to realise the significance of the equality of the upper and lower bounds.

## Question

The following diagram shows a weighted graph *G *with vertices A, B, C, D and E.

Show that graph \(G\) is Hamiltonian. Find the total number of Hamiltonian cycles in \(G\), giving reasons for your answer.

State an upper bound for the travelling salesman problem for graph \(G\).

Hence find a lower bound for the travelling salesman problem for \(G\).

Show that the lower bound found in (d) cannot be the length of an optimal solution for the travelling salesman problem for the graph \(G\).

**Answer/Explanation**

## Markscheme

*eg *the cycle \({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{D}} \to {\text{E}} \to {\text{A}}\) is Hamiltonian *A1*

starting from any vertex there are four choices

from the next vertex there are three choices, *etc *… *R1*

so the number of Hamiltonian cycles is \(4!{\text{ }}( = 24)\) *A1*

**Note: **Allow 12 distinct cycles (direction not considered) or 60 (if different starting points count as distinct). In any case, just award the second ** A1 **if

**is awarded.**

*R1**[3 marks]*

total weight of any Hamiltonian cycles stated

*eg* \({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{D}} \to {\text{E}} \to {\text{A}}\) has weight \(5 + 6 + 7 + 8 + 9 = 35\) *A1*

*[1 mark]*

a lower bound for the travelling salesman problem is then obtained by adding the weights of CA and CB to the weight of the minimum spanning tree *(M1)*

a lower bound is then \(14 + 6 + 6 = 26\) *A1*

*[2 marks]*

**METHOD 1**

*eg *eliminating A from *G, *a minimum spanning tree of weight 18 is *(M1)*

*A1*

adding AD and AB to the spanning tree gives a lower bound of \(18 + 4 + 5 = 27 > 26\) *A1*

so 26 is not the best lower bound *AG*

**Note: **Candidates may delete other vertices and the lower bounds obtained are B-28, D-27 and E-28.

**METHOD 2**

there are 12 distinct cycles (ignoring direction) with the following lengths

Cycle Length

ABCDEA 35 *M1*

ABCEDA 33

ABDCEA 39

ABDECA 37

ABECDA 31

ABEDCA 31

ACBDEA 37

**ACBEDA** **29**

ACDBEA 35

ACEBDA 33

AEBCDA 31

AECBDA 37 *A1*

as the optimal solution has length 29 *A1*

26 is not the best possible lower bound *AG*

**Note: **Allow answers where candidates list the 24 cycles obtained by allowing both directions.

*[3 marks]*

## Examiners report

Part (a) was generally well answered, with a variety of interpretations accepted.

Part (b) also had a number of acceptable possibilities.

Part (d) was generally well answered, but there were few good attempts at part (e).

Part (d) was generally well answered, but there were few good attempts at part (e).

## Question

The weighted graph *K*, representing the travelling costs between five customers, has the following adjacency table.

Draw the graph \(K\).

Starting from customer D, use the nearest-neighbour algorithm, to determine an upper bound to the travelling salesman problem for *K*.

By removing customer A, use the method of vertex deletion, to determine a lower bound to the travelling salesman problem for *K*.

**Answer/Explanation**

## Markscheme

complete graph on five vertices *A1*

weights correctly marked on graph *A1*

*[2 marks]*

clear indication that the nearest-neighbour algorithm has been applied *M1*

DA (or 7) *A1*

AB (or 1) BC (or 9) *A1*

CE (or 3), ED (or 12), giving UB = 32 *A1*

*[4 marks]*

attempt to use the vertex deletion method *M1*

minimum spanning tree is ECBD *A1*

(EC 3, BD 8, BC 9 total 20)

reconnect A with the two edges of least weight, namely AB (1) and AE (4) *M1*

lower bound is 25 *A1*

*[4 marks]*

## Examiners report

[N/A]

[N/A]

[N/A]

## Question

The weights of the edges of a graph \(H\) are given in the following table.

(i) Draw the weighted graph \(H\).

(ii) Use Kruskal’s algorithm to find the minimum spanning tree of \(H\). Your solution should indicate the order in which the edges are added.

(iii) State the weight of the minimum spanning tree.

Consider the following weighted graph.

(i) Write down a solution to the Chinese postman problem for this graph.

(ii) Calculate the total weight of the solution.

(i) State the travelling salesman problem.

(ii) Explain why there is no solution to the travelling salesman problem for this graph.

**Answer/Explanation**

## Markscheme

(i) *A2*

**Note: **Award ** A1 **if one edge is missing. Award

**if the edge weights are not labelled.**

*A1*(ii) the edges are added in the order:

\(FG{\rm{ }}1\) *M1A1*

\(CE{\rm{ }}2\) *A1*

\(ED{\rm{ }}3\)

\(EG{\rm{ }}4\) *A1*

\(AC{\rm{ }}4\)

**Note: **\(EG\) and \(AC\) can be added in either order.

(Reject \(EF\))

(Reject \(CD\))

\(EB5\) **OR **\(AB5\) *A1*

**Notes: **The minimum spanning tree does not have to be seen.

If only a tree is seen, the order by which edges are added must be clearly indicated.

(iii) \(19\) *A1*

*[8 marks]*

(i) *eg*, \(PQRSRTSTQP\) **OR **\(PQTSTRSRQP\) *M1A1*

**Note: **Award ** M1 **if in either (i) or (ii), it is recognised that edge \(PQ\) is needed twice.

(ii) total weight \( = 34\) *A1*

*[3 marks]*

(i) to determine a cycle where each vertex is visited once only (Hamiltonian cycle) *A1*

of least total weight *A1*

(ii) **EITHER**

to reach \(P\), \(Q\) must be visited twice which contradicts the definition of the \(TSP\) *R1*

**OR**

the graph is not a complete graph and hence there is no solution to the \(TSP\) *R1 *

*[3 marks]*

*Total [14 marks]*

## Examiners report

Part (a) was generally very well answered. Most candidates were able to correctly sketch the graph of \(H\) and apply Kruskal’s algorithm to determine the minimum spanning tree of \(H\). A few candidates used Prim’s algorithm (which is no longer part of the syllabus).

Most candidates understood the Chinese Postman Problem in part (b) and knew to add the weight of \(PQ\) to the total weight of \(H\). Some candidates, however, did not specify a solution to the Chinese Postman Problem while other candidates missed the fact that a return to the initial vertex is required.

In part (c), many candidates had trouble succinctly stating the Travelling Salesman Problem. Many candidates used an ‘edge’ argument rather than simply stating that the Travelling Salesman Problem could not be solved because to reach vertex \(P\), vertex \(Q\) had to be visited twice.

## Question

Mathilde delivers books to five libraries, A, B, C, D and E. She starts her deliveries at library D and travels to each of the other libraries once, before returning to library D. Mathilde wishes to keep her travelling distance to a minimum.

The weighted graph \(H\), representing the distances, measured in kilometres, between the five libraries, has the following table.

Draw the weighted graph \(H\).

Starting at library D use the nearest-neighbour algorithm, to find an upper bound for Mathilde’s minimum travelling distance. Indicate clearly the order in which the edges are selected.

By first removing library C, use the deleted vertex algorithm, to find a lower bound for Mathilde’s minimum travelling distance.

**Answer/Explanation**

## Markscheme

complete graph on 5 vertices *A1*

weights correctly marked on graph *A1*

*[2 marks]*

clear indication that the nearest-neighbour algorithm has been applied *M1*

DA (or 16) *A1*

AB (or 18) then BC (or 15) *A1*

CE (or 17) then ED (or 19) *A1*

\({\text{UB}} = 85\) *A1*

*[5 marks]*

an attempt to find the minimum spanning tree *(M1)*

DA (16) then BE (17) then AB (18) (total 51) *A1*

reconnect C with the two edges of least weight, namely CB (15) and CE (17) *M1*

\({\text{LB}} = 83\) *A1*

*[4 marks]*

## Examiners report

[N/A]

[N/A]

[N/A]

## Question

Consider the following weighted graph *G*.

State what feature of *G* ensures that *G* has an Eulerian trail.

State what feature of *G* ensures that *G* does not have an Eulerian circuit.

Write down an Eulerian trail in *G*.

State the Chinese postman problem.

Starting and finishing at B, find a solution to the Chinese postman problem for* G*.

Calculate the total weight of the solution.

**Answer/Explanation**

## Markscheme

*G* has an Eulerian trail because it has (exactly) two vertices (B and F) of odd degree **R1**

**[1 mark]**

*G* does not have an Eulerian circuit because not all vertices are of even degree **R1**

**[1 mark]**

for example BAEBCEFCDF **A1A1**

**Note:** Award * A1 *for start/finish at B/F,

*for the middle vertices.*

**A1****[2 marks]**

to determine the shortest route (walk) around a weighted graph **A1**

using each edge (at least once, returning to the starting vertex) **A1**

**Note:** Correct terminology must be seen. Do not accept trail, path, cycle or circuit.

**[2 marks]**

we require the Eulerian trail in (b), (weight = 65) **(M1)**

and the minimum walk FEB (15) **A1**

for example BAEBCEFCDFEB **A1**

**Note:** Accept EB added to the end or FE added to the start of their answer in (b) in particular for follow through.

**[3 marks]**

total weight is (65 + 15=)80 ** A1**

**[1 mark]**

## Examiners report

[N/A]

[N/A]

[N/A]

[N/A]

[N/A]

[N/A]

## Question

The weights of the edges of a graph *G* with vertices A, B, C, D and E are given in the following table.

Starting at A, use the nearest neighbour algorithm to find an upper bound for the travelling salesman problem for *G* .

(i) Use Kruskal’s algorithm to find and draw a minimum spanning tree for the subgraph obtained by removing the vertex A from *G* .

(ii) Hence use the deleted vertex algorithm to find a lower bound for the travelling salesman problem for *G* .

**Answer/Explanation**

## Markscheme

using the nearest neighbour algorithm, starting with A,

\({\text{A}} \to {\text{E, E}} \to {\text{C}}\) *A1*

\({\text{C}} \to {\text{D, D}} \to {\text{B}}\) *A1*

\({\text{B}} \to {\text{A}}\) *A1*

the upper bound is therefore 9 + 10 + 16 + 13 + 11 = 59 *A1*

*[4 marks]*

(i) the edges are added in the order CE *A1*

BD *A1*

BE *A1*

*A1*

(ii) the weight of the minimum spanning tree is 37 *(A1)*

we now reconnect A with the 2 edges of least weight *(M1)*

*i.e.* AE and AB *A1*

the lower bound is therefore 37 + 9 + 11 = 57 *A1*

*[8 marks]*

## Examiners report

[N/A]

[N/A]