Chapter 5- TSP Flashcards
1
Q
Walk
A
A finite sequence of edges such that the end vertex of one edge is the start of the next
2
Q
Tour
A
A walk which visits every vertex, returning to it’s starting vertex
3
Q
Classical TSP
A
Each vertex visited exactly once before returning to the start
4
Q
Practical TSP
A
Every vertex visited at least once before returning to the start
5
Q
Triangle inequality
A
The longest side of any triangle <= the sum of the two shorter sides