Chapter 5- TSP

Question 1

Walk

Answer 1

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

Question 2

Tour

Answer 2

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

Question 3

Classical TSP

Answer 3

Each vertex visited exactly once before returning to the start

Question 4

Practical TSP

Answer 4

Every vertex visited at least once before returning to the start

Question 5

Triangle inequality

Answer 5

The longest side of any triangle <= the sum of the two shorter sides