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\leq AC+CB, where AB is the longest side of the triangle ABC.

How many different tours does a complete graph on n vertices have?

\frac{(n-1)!}{2}, counting a tour and its reverse as the same.

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.

The travelling salesman problemEdexcel International A Level Maths: Flashcards

Card 1 of 120 of 12 known

Question

What is the travelling salesman problem?

Tap or press Space to reveal

Tap card or press Space to flip

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\leq AC+CB$ , where $AB$ is the longest side of the triangle $ABC$ .
How many different tours does a complete graph on $n$ vertices have?: $\frac{(n-1)!}{2}$ , counting a tour and its reverse as the same.
How many tours are there on $4$ vertices?: $3$ .
How many tours are there on $5$ vertices?: $12$ .
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.

Exam questions on The travelling salesman problem

A sales representative must visit four towns $P$ , $Q$ , $R$ and $S$ , starting and finishing at $P$ . Every pair of towns is joined by a direct road. The distances in km are $PQ=12$ , $PR=15$ , $PS=9$ , $QR=8$ , $QS=14$ and $RS=11$ . Each town is to be visited exactly once.
Find the length of the shortest tour for the classical problem.2 marks
A driver starts at a depot $H$ , delivers to three shops $A$ , $B$ and $C$ , and returns to $H$ . The only roads are $HA=5$ , $HB=7$ and $HC=4$ , with lengths in km. The driver may pass through a junction more than once.
A fourth shop $D$ is added, joined only to $C$ by a road of length $3$ km. Find the length of the shortest route that visits all four shops and returns to $H$ .2 marks
Four offices $W$ , $X$ , $Y$ and $Z$ are joined by a complete network of direct links. The lengths in km are $WX=20$ , $WY=35$ , $WZ=25$ , $XY=15$ , $XZ=30$ and $YZ=10$ .
Show that the triangle inequality is not satisfied by this network.3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).