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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Tour

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Classical TSP

A

Each vertex visited exactly once before returning to the start

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Practical TSP

A

Every vertex visited at least once before returning to the start

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Triangle inequality

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly