870 CHAPTER 13 Graph Theory We know that since there are 4 cities that must be visited, there are − = = ⋅ ⋅ = (4 1)! 3! 3 2 1 6 possible unique Hamilton circuits we need to examine for cost. These Hamilton circuits are listed in the first column of Table 13.2. Now try Exercise 29 Table 13.2 Hamilton Circuit First Leg/Cost Second Leg/Cost Third Leg/Cost Fourth Leg/Cost Total Cost O , A , M , N , O O to A $103 A to M $229 M to N $171 N to O $139 $642 O , A , N , M , O O to A $103 A to N $110 N to M $171 M to O $161 $545 O , M , A , N , O O to M $161 M to A $229 A to N $110 N to O $139 $639 O , M , N , A , O O to M $161 M to N $171 N to A $110 A to O $103 $545 O , N , A , M , O O to N $139 N to A $110 A to M $229 M to O $161 $639 O , N , M , A , O O to N $139 N to M $171 M to A $229 A to O $103 $642 The Hamilton circuits are listed in the column on the far left. In the next four columns, we place the cost associated with each leg of the given circuit. In the farright column, we place the total cost of travel using the given circuit. From this last column, we see that two circuits have the lowest cost, $545 (circled). Priya has two choices for an optimal solution. She can either fly from Orlando to Atlanta to New Orleans to Memphis then back to Orlando, or she can fly from Orlando to Memphis to New Orleans to Atlanta then back to Orlando. These two Hamilton circuits are shown on the maps in Fig. 13.42. Notice that the second circuit involves visiting the cities in the exact reverse order of the first circuit. Either circuit provides Priya with the least expensive way to visit each city and return to her home in Orlando. Atlanta New Orleans Memphis Orlando Atlanta New Orleans Memphis Orlando Figure 13.42 Profile in Mathematics William Rowan Hamilton Born in Dublin, Ireland, Sir William Rowan Hamilton (1805–1865) made many contributions to mathematics and the sciences. His work in mathematics included abstract algebra, calculus, geometry, graph theory, logic, and number theory. Perhaps his most important work involved the use of quaternions in abstract algebra. Quaternions are elements in a noncommutative group (see Chapter 9 for a discussion of group theory) that Hamilton labeled with the letters i j , , and k. For years, Hamilton puzzled over how to multiply the quaternions. Finally, one day while walking with his wife, he realized the solution. In his excitement, Hamilton carved the solution in the stone of Brougham (or Broom) Bridge as he and his wife passed by on their walk: = = = = − i j k ijk 1. 2 2 2 To this day, there is a plaque on this bridge commemorating Hamilton’s discovery. Hamilton’s interests also included philosophy, religion, foreign languages, and poetry. Hamilton also invented a game called the Icosian Game (see Exercise 39) that includes many aspects of graph theory you will study in this section. For more information on Hamilton, see the Profiles in Mathematics on page 575. Although we used the brute force method in Example 5, it becomes impractical as the number of vertices increases. In fact, with more complex problems, the brute force method is impractical on even the world’s fastest supercomputers. For example, suppose the president of the United States wished to visit all of the state capitals and return to Washington, DC. The president would have − = (51 1)! 50! choices to accomplish this trip. Furthermore, each choice requires adding the costs or distances of traveling the 51 legs of each trip. As of September 2023, it would take the world’s fastest supercomputer × 2.06 1040 or 20,600,000,000,000,000,000,000,000,000,000,000,000,000 (20.6 duodecillion) years to perform the brute force method to determine the optimal solution! Computer scientists and mathematicians have developed much more efficient algorithms for approximating the optimal solution to traveling salesmen problems. 7
RkJQdWJsaXNoZXIy NjM5ODQ=