Travelling Salesman Problem (DP IB Applications & Interpretation (AI)): Revision Note

Hamiltonian paths & cycles

What are Hamiltonian paths and cycles?

• A Hamiltonian path is a path which visits each vertex in a graph exactly once

• A Hamiltonian cycle is a path which visits each vertex in a graph exactly once and begins and ends at the same vertex

  • The start and end vertex is the only vertex that is repeated

• A graph which contains a Hamiltonian cycle is called a Hamiltonian graph

• A semi-Hamiltonian graphs contains a Hamiltonian path but not a Hamiltonian cycle

• The only way to show that a graph is Hamiltonian or semi-Hamiltonian is to find a Hamiltonian cycle or Hamiltonian path

Travelling salesman problem

What is the travelling salesman problem?

• The travelling salesman problem requires you to find the route of least weight such

  • it starts and finishes at the same vertex

  • and it visits every other vertex in the graph exactly once

• The classical problem has the following conditions:

  • the graph is complete

  • the direct route between two vertices is the shortest route

    • it is said to satisfy the triangle inequality

How do I solve the classical travelling salesman problem?

• There is no known algorithm that guarantees finding the shortest Hamiltonian cycle in a graph

• List all the possible Hamiltonian cycles

• Add together the edges for each cycle

• Find the cycle of least weight

  • This method is only suitable for small graphs