SECTION 2.2 Elementary Graph Theory 119
cycles.
In order to find the Hamiltonian cycle of minimal weight, we shall
resort to theBrute-Force Method, that is we shall form a complete
list of the Hamiltonian cycles and their weights, choosing the one of
minimal weight as the solution of our problem. There is one final sim-
plification, namely, if the complete graph with vertices{v 1 ,v 2 , ...,vn}
is weighted, then the weight of the Hamiltonian cycle (v 1 ,v 2 ,...,vn,v 1 )
clearly has the same weight as the “reverse cycle” (v 1 ,vn,vn− 1 ,...,v 2 ,v 1 ).
Therefore the Brute Force Method will require us to compare the weights
of^12 (n−1)! Hamiltonian cycles.
We now list the weights of the Hamiltonian cycles in the above graph,
highlighting the cycle of minimal weight.
cycle weight reverse cycle
ABCDEA 185 + 121 + 174 + 199 + 133 = $812 AEDCBA
ABCEDA 185 + 121 + 120 + 199 + 152 = $777 ADECBA
ABDCEA 185 + 150 + 174 + 120 + 133 = $762 AECDBA
ABDECA 185 + 150 + 199 + 120 + 119 = $773 ACEDBA
ABECDA 185 + 200 + 120 + 174 + 152 = $831 ADCEBA
ABEDCA 185 + 200 + 199 + 174 + 119 = $877 ACDEBA
ACBDEA 119 + 121 + 150 + 199 + 133 = $722 AEDBCA
ACBEDA 119 + 121 + 200 + 199 + 152 = $791 ADEBCA
ADBCEA 152 + 150 + 121 + 120 + 133 = $676 AECBDA
ADBECA 152 + 150 + 200 + 120 + 119 = $741 ACEBDA
AEBCDA 133 + 200 + 121 + 174 + 152 = $780 ADCBEA
AEBDCA 133 + 200 + 150 + 174 + 119 = $776 ACDBEAAs a result of the above computations we see that the minimal cost is
for the salesman to visit the cities in the order
Chicago−→Highland−→Gary−→Merriville−→Joliet−→Chicago,
which results in a total cost of $676. In the next subsection we shall con-
sider a few algorithms which can be used to determine “good” Hamil-
tonian cycles if not the optimal Hamiltonian cycle.
The above is an example of theTraveling Salesman Problem—