Suppose a traveling salesman wishes to visit several cities. If the cities are represented as vertices and the possible routes between them as edges then, as we have already said, the salesman’s preferred itinerary is a Hamilton cycle in the graph.

In most cases there is a cost associated with every edge. Depending on the salesman’s priorities, the cost might be a dollar cost (such as airfare or gasoline), or the number of miles to be driven, or the number of hours the trip will take. The most desirable itinerary will be the one for which the sum of costs is a minimum. The problem of finding this cheapest Hamilton cycle is called the Traveling Salesman Problem.

We shall continue to speak in terms of a salesman, but these problems have many other applications. They arise in airline and delivery routing and in telephone routing. More recently they have been important in manufacturing integrated circuits and computer chips, and for internet routing. A Hamilton cycle is often the solution to a problem where you need to examine a number of sites, while an Euler circuit is appropriate when you need to examine the routes between the sites.

In order to solve a Traveling Salesman Problem on n vertices, your first thought might be to list all Hamilton cycles in the graph and then work out the cost; the cheapest answer would be the solution. But very often we can assume the graph is complete. In that case listing all the cycles can be a very long task, because of the following theorem.

Theorem 1. The complete graph Kn contains (n−1)!/2 Hamilton cycles.

Proof. K_n has n vertices, so there are n! different ways to list the vertices in order.

As we pointed out previously, each cycle of length n gives rise to 2n different ways to list its vertices. So there are n!/(2n)=(n−1)!/2 Hamilton cycles.

This number grows very quickly. For n = 3,4,5,6,7 the value of (n−1)!/2 is 1,  3, 12, 60, 360; in K₁₀, there are 181,440, and in K₂₄, there are about 10²³ Hamilton cycles. Twenty-four vertices is not an unreasonably large network, but performing so many summations and comparing them would be impossible in practice. To give you some idea of the times involved, if you had a computer capable of evaluating and sorting through a million ten-vertex cycles per second, a complete search solution of the Traveling Salesman Problem for K₁₀ would take about .18 s. No problem so far. However, assuming the computer took about twice as much time to process a 24-vertex cycle as it took for a ten-vertex cycle, so that it could sort through half a million 24-vertex cycles per second, the complete search for K₂₄ would take about a billion years.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength