The travelling salesman problem

The travelling salesman problem Flashcards

Spec 3.2 · Edexcel International A Level Maths: 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.
AB≤AC+CBAB\leq AC+CB, where ABAB is the longest side of the triangle ABCABC.
How many different tours does a complete graph on nn vertices have?
(n−1)!2\frac{(n-1)!}{2}, counting a tour and its reverse as the same.
How many tours are there on 44 vertices?
33.
How many tours are there on 55 vertices?
1212.
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.

Flashcards