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

 

https://play.google.com/store/apps/details?id=com.iitianDownload IITian Academy  App for accessing Online Mock Tests and More..

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 .

a.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.[5]

b.Find the total weight of the cycle ADCBEA.[1]

c.What do you conclude from your results?[1]

▶️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]

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.

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

 

b.State an upper bound for the travelling salesman problem for graph \(G\).[1]

 

d.Hence find a lower bound for the travelling salesman problem for \(G\).[2]

 

e.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\).[3]

▶️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 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.

a.Draw the graph \(K\).[2]

 

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

 

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

▶️Answer/Explanation

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.

Examiners report

[N/A]

a.

[N/A]

b.

[N/A]

c.

Question

a.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.[8]

b.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.[3]

c.(i)     State the travelling salesman problem.

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

▶️Answer/Explanation

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.
Scroll to Top