The travelling salesman problem Flashcards
Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.
12 cards
Tap a card to flip it. Swipe right if you knew it, left if not.
See all 12 cards
- What is the travelling salesman problem?
- Find a route of minimum length which visits every vertex in an undirected network.
- What is a tour?
- A walk that visits every vertex and returns to the starting vertex.
- What is the classical TSP?
- Each vertex is visited exactly once, and the tour returns to the start.
- What is the practical TSP?
- A vertex may be visited more than once.
- What is a complete graph?
- A graph in which every pair of vertices is joined by an arc.
- State the triangle inequality.
- , where is the longest side of the triangle .
- How many different tours does a complete graph on vertices have?
- , counting a tour and its reverse as the same.
- How many tours are there on vertices?
- .
- How many tours are there on vertices?
- .
- Why does a vertex with only one arc stop a classical tour?
- A tour must enter and leave by the same arc, so the neighbouring vertex is visited twice.
- What is the shortest tour of a tree?
- Every arc is travelled twice, so twice the total weight.
- How do you show the triangle inequality fails?
- Find a triangle where the longest side is greater than the sum of the other two.