118 CHAPTER 2 Discrete Mathematics
Of more significance than just finding a Hamiltonian cycle in a simple
graph is that of finding a Hamiltonian cycle of least total weight
in a weighted graph. Such is the nature of the traveling salesman
problem. We start with a simple example.
Example 1. A salesman needs
to visit five cities in the American
Midwest: Chicago, Gary, Joliet,
Merriville, and Highland. The cost
of travel between the cities is de-
picted in the graph to the right.^30
We display the costs in tabular form. It will be convenient to use
the lettersA, B, C, D,andE to represent the cities. Notice that since
the matrix of entries is symmetric, there is no need to fill in all of the
entries.
A= Chicago B= Gary C= Merriville D= Highland E= Joliet
Chicago * $185 $119 $152 $133
Gary * $121 $150 $200
Merriville * $174 $120
Highland * $199
Joliet *Assuming that the salesman will begin and end his trip in Chicago,
what it the optimal, i.e., cheapest route for him to take? That is,
which Hamilton cycle will afford the least total weight?
In order to answer this question, a few observations are in order.
First of all, acomplete graph is one in which every pair of distinct
vertices are joined by an edge. Thus, the above graph is a (weighted)
complete graph. Next, it is obvious that in a complete graph withn
vertices, there are exactly (nā1)! Hamiltonian cycles starting from a
given vertex. In the present example there are 4! = 24 Hamiltonian
(^30) The numbers are taken from Example 2, page 201 of Excursions in Modern Mathematics, Fourth
Edition, by Peter Tannenbaum and Robert Arnold.