13.1 Graphs, Paths, and Circuits 845 Now try Exercise 31 California (CA) Nevada (NV) Colorado (CO) Arizona (AZ) New Mexico (NM) Utah (UT) Figure 13.5 Solution In our graph, each vertex will represent one of the six states shown in Fig. 13.5. We begin by placing six vertices in the same relative positions as the six states on the map and then labeling each vertex with the corresponding two-letter abbreviation (Fig. 13.6). The exact placement of the vertices is not critical. Next, if two states share a common border, connect the respective vertices with an edge. For example, Nevada shares a common border with Utah, Arizona, and California so there will be edges that connect vertex NV to vertices UT AZ , , and CA, as shown in Fig. 13.7. CA NV NM CO AZ UT Figure 13.7 Next, note that Utah shares a common border with Nevada, Arizona, and Colorado. Therefore, the graph in Fig. 13.7 will have edges that connect UT to NV AZ , , and CO, respectively. Note that Utah and New Mexico have borders that touch only at a corner point and thus are not considered to share a common border. Therefore, in the graph shown in Fig. 13.7, no edge connects UT to NM. Likewise, Arizona and Colorado are not considered to share a common border; thus, no edge connects AZ to CO. To finish the graph, we continue adding edges until, for every two states in Fig. 13.5 that share a common border, there is an edge between their respective vertices in Fig. 13.7. 7 m Bryce Canyon National Park, Utah CA NV NM CO AZ UT Figure 13.6 In Example 2, the graph shown in Fig. 13.7 is only one possible arrangement of vertices and edges that can show which states share a common border. Many other graphs that display the same relationship are equally valid. Fig. 13.8 shows one such graph. Although the vertices in the graph in Fig. 13.8 do not resemble the respective locations of the states they represent, the relationship between the vertices is the same as in Fig. 13.7. CO NM CA NV AZ UT Figure 13.8 Neale Clark/Robertharding/ Alamy Stock Photo
RkJQdWJsaXNoZXIy NjM5ODQ=