# IB DP Maths Topic 10.10 Travelling salesman problem. HL Paper 3

## 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.

## 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.


a.

Find the total weight of the cycle ADCBEA.


b.

What do you conclude from your results?


c.

## 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]

a.

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

[1 mark]

b.

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

[1 mark]

c.

## 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.

a.

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

b.

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

c.

## 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.


a.

State an upper bound for the travelling salesman problem for graph $$G$$.


b.

Hence find a lower bound for the travelling salesman problem for $$G$$.


d.

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$$.


e.

## 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 R1 is awarded.

[3 marks]

a.

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]

b.

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]

d.

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]

e.

## Examiners report

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

a.

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

b.

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

d.

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

e.

## Question

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


a.

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


b.

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


c.

## Markscheme complete graph on five vertices     A1

weights correctly marked on graph     A1

[2 marks]

a.

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]

b.

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]

c.

[N/A]

a.

[N/A]

b.

[N/A]

c.

## 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.


a.

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.


b.

(i)     State the travelling salesman problem.

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


c.

## Markscheme

(i) A2

Note:     Award A1 if one edge is missing. Award A1 if the edge weights are not labelled.

(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]

a.

(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]

b.

(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]

c.

## 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).

a.

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.

b.

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.

c.

## 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$$.


a.

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.


b.

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


c.

## Markscheme complete graph on 5 vertices     A1

weights correctly marked on graph     A1

[2 marks]

a.

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]

b.

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]

c.

[N/A]

a.

[N/A]

b.

[N/A]

c.

## Question

Consider the following weighted graph G. State what feature of G ensures that G has an Eulerian trail.


a.i.

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


a.ii.

Write down an Eulerian trail in G.


b.

State the Chinese postman problem.


c.i.

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


c.ii.

Calculate the total weight of the solution.


c.iii.

## Markscheme

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

[1 mark]

a.i.

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

[1 mark]

a.ii.

for example BAEBCEFCDF      A1A1

Note: Award A1 for start/finish at B/F, A1 for the middle vertices.

[2 marks]

b.

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]

c.i.

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]

c.ii.

total weight is (65 + 15=)80      A1

[1 mark]

c.iii.

[N/A]

a.i.

[N/A]

a.ii.

[N/A]

b.

[N/A]

c.i.

[N/A]

c.ii.

[N/A]

c.iii.

## 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 .


a.

(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 .


b.

## 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]

a.

(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]

b.

[N/A]

a.

[N/A]

b.