Chapter 3 - The travelling salesman problem

Question 1

What is a walk?

Answer 1

A finite sequence of edges such that the end vertex of one edge us the start vertex of the next

Question 2

What is a tour?

Answer 2

A walk which visits every vertex, returning to it’s starting vertex

Question 3

What is a classical problem?

Answer 3

An tour which visit each vertex only once

Question 4

What is a practical problem?

Answer 4

An tour which visits each vertex at least once

Question 5

How do you find the minimum spanning tree (MST)?

Answer 5

With either Prim’s algorithm or Kruskal’s algorithm

Question 6

How do you find the upper bound with a MST?

Answer 6

MST x 2 = Initial upper bound,

Then seek ‘short cuts’

Question 7

How do you find the lower bound?

Answer 7

1) Remove a vertex
2) Find the residual minimum spanning tree (RMST)
3) Add the two shortest arcs to the deleted vertex

Question 8

What methods do you use to find the upper bound?

Answer 8

• Using a MST

- Use the nearest neighbour algorithm