The Salesman's Problem

The Salesman's Problem and its big brother, the Traveling Salesman's Problem, are both graph theory classics.

What You Should Learn

  • The definitions of the Salesman and Traveling Salesman problems.
salesman on globe

Say you're a salesman and you have to travel to a list of a dozen cities. You need to find an intinerary that takes you to each city on your route once and only once. There wouldn't, technically, be anything wrong with your visiting a city multiple times but it's an extra expense that you'd probably rather avoid. We'll need some new language to work through this problem. Almost all of our definitions in the previous sections focused on not repeating edges. To get our salesman where he needs to go we'll need some language that focuses more on the vertices. In the next sections we'll see how to tell if the required route exists for a given combination of cities and routes.

The Traveling Salesman Problem

salesman on globeThis is a much more difficult question. Say you're that salesman again and that you have multiple routes from which to choose. That is, there's more than one route that takes you through every city exactly once. Being a smart businessman, you want to choose the one that will cost the least. We can model this situation as a network where the number assigned to each edge (i.e. to each road) is equal to the cose of using it. The total cost of the trip would be the sum of the values of the edges that make it up. That sounds so simple, right? Unfortunately, this is a problem that, despite its importance in operations research, doesn't have an easy solution. The only answers are calculated on a case-by-case basis, usually by having a computer calculate the cost of every possible trip.

Hamiltonian Graphs, Part I >><< Trails and Circuits, Exercises