The Travelling Salesperson Problem (AQA A-Level Further Maths): Flashcards

Shortest route visiting all vertices & returning to start

Closed path visiting each vertex exactly once, then returns

Minimum weight Hamiltonian cycle

$\frac{1}{2}(n-1)!$

Finds good solution that may not be optimal

Minimum weight arc to unvisited vertex

Repeat from each vertex, select best tour

Length of that tour

Two smallest arcs from $V$ + MST of rest

Smallest upper bound, largest lower bound