866 CHAPTER 13 Graph Theory In this section, we continue our study of graph theory by studying Hamilton paths and Hamilton circuits. These paths and circuits are named for Irish mathematician and astronomer William Rowan Hamilton (1805–1865); see the Profile in Mathematics on page 870. Before formally defining Hamilton paths and Hamilton circuits, we will introduce an example that will be examined at several points throughout this section. Example 1 A Transportation Problem Priya is the chief operating officer for Hard Rock Cafe International. Priya lives in Orlando, Florida, and needs to visit Hard Rock Cafe restaurants in Atlanta, Georgia; Memphis, Tennessee; and New Orleans, Louisiana. She would like to determine the least expensive way to visit each of these cities one time and return to her home in Orlando. To help analyze this problem, Priya searched online and obtained the least expensive one-way fares offered between each of the four cities (see Table 13.1). Now try Exercise 7 Table 13.1 Orlando Atlanta Memphis New Orleans Orlando (O) * $103 $161 $139 Atlanta (A) $103 * $229 $110 Memphis (M) $161 $229 * $171 New Orleans (N) $139 $110 $171 * Use this table to create a graph. Let the vertices represent the cities, then connect each pair of cities with an edge. List the airfare between each two cities on the respective edges. Solution First we note that the cost of a one-way flight between two given cities in the table is the same regardless from which city Priya starts. For example, the oneway fare from New Orleans to Atlanta is $110 and the one-way fare from Atlanta to New Orleans is also $110. This information will allow us to list the flight cost along an edge with a single number. Next we draw a graph with four vertices that represent the four cities and six edges that represent the flights between each city. We also include the price of one-way flights along the appropriate edge. Two such graphs are shown in Fig. 13.35. Many other graphs could also display this information. 7 M N A O 229 139 103 171 161 110 (a) O A N M 103 229 110 171 161 139 (b) Figure 13.35 Problems like the one in Example 1 are called traveling salesman problems. There are usually variations to the situation, but these problems generally involve seeking the least expensive or shortest way to travel among several locations. To help analyze traveling salesman problems, the costs or distances to travel between locations are indicated along each edge of a graph. Such a graph, as in Fig. 13.35(a) or (b), is called a weighted graph. We will use weighted graphs to solve traveling salesman problems, but first we need to introduce Hamilton paths and Hamilton circuits. Hamilton Paths, Hamilton Circuits, and Complete Graphs Now we introduce another important definition of graph theory. Definition: Hamilton Path A Hamilton path is a path that contains each vertex of a graph exactly one time. Matej_z/Shutterstock
RkJQdWJsaXNoZXIy NjM5ODQ=