13.3 Hamilton Paths and Hamilton Circuits 865 Ralph delivers mail for the United States Postal Service. He wishes to determine the shortest route that begins at the post office, goes to each mailbox in his delivery area exactly one time, and ends back at the post office. In this section, we will study a special type of problem like the one facing Ralph. Hamilton Paths and Hamilton Circuits SECTION 13.3 LEARNING GOALS Upon completion of this section, you will be able to: 7 Understand Hamilton paths, Hamilton circuits, and complete graphs. 7 Solve traveling salesman problems. Why This Is Important As we saw in Section 13.2, there are many real-life problems that can be represented and solved using graphs, paths, and circuits. Anytime a problem involves visiting multiple locations, graph theory can be used to represent and solve the problem. The methods we study in this section can also be used in biology, physics, chemistry, and engineering and in many business applications. 45. Determine an Euler path through the Southwestern states (see Example 4) that begins with the state of Utah. UT CO NM AZ CA NV UT AZ NV , , , , , , , , 46. Determine an Euler path for the Phenomenal Phitness Gym (see Example 5) that begins in locker room (vertex) A. AOHCBKHGASHO , , , , , , , , , , , In Exercises 47–50, determine an Euler circuit for the Greenbriar crime stopper group (see Example 6) that begins with 47. vertex B followed by vertex A. BAEHIJKDCGGJFCBFIEB , , , , , , , , , , , , , , , , , , 48. vertex B followed by vertex E. BEHIJKDCGGJFCBFIEAB , , , , , , , , , , , , , , , , , , 49. vertex J followed by vertex G. JGGCFJKDCBFIEBAEHIJ , , , , , , , , , , , , , , , , , , 50. vertex J followed by vertex F. JFCGGJKDCBAEHIEBFIJ , , , , , , , , , , , , , , , , , , Concept/Writing Exercises 51. Imagine a very large connected graph that has 400 even vertices and no odd vertices. a) Does an Euler path exist for this graph? Explain. Yes. There are no odd vertices. b) Does an Euler circuit exist for this graph? Explain. Yes. There are no odd vertices. 52. Imagine a very large connected graph that has two odd vertices and 398 even vertices. a) Does an Euler path exist for this graph? Explain. Yes. There are exactly two odd vertices. b) Does an Euler circuit exist for this graph? Explain. No. There is at least one odd vertex. 53. Imagine a very large connected graph that has 400 odd vertices and no even vertices. a) Does an Euler path exist for this graph? Explain. No. There are more than two odd vertices. b) Does an Euler circuit exist for this graph? Explain. No. There is at least one odd vertex. 54. Imagine a very large connected graph that has 200 odd vertices and 200 even vertices. a) Does an Euler path exist for this graph? Explain. No. There are more than two odd vertices. b) Does an Euler circuit exist for this graph? Explain. No. There is at least one odd vertex. Challenge Problems/Group Activities 55. U.S. Map Consider a map of the contiguous United States. Imagine a graph with 48 vertices in which each vertex represents one of the contiguous states. Each edge would represent a common border between states. a) Would this graph have an Euler path? No b) Explain why or why not. * 56. Attempt to draw a graph with an Euler circuit that has a bridge. What conclusion can you develop from this exercise? It is not possible to draw a graph with an Euler circuit that has a bridge. Therefore, a graph with an Euler circuit has no bridge. 57. a) Draw a graph with one vertex that has both an Euler path and an Euler circuit. * b) Draw a graph with two vertices that has an Euler path but no Euler circuit. * c) Draw a graph with two vertices that has both an Euler path and an Euler circuit. * Research Activity 58. Knot Theory Write a paper on the history and development of the branch of mathematics known as knot theory. Include a discussion on its applications to science and technology. See the Did You Know? box on page 855. *See Instructor Answer Appendix Pierre Rochon photography/ Alamy Stock Photo
RkJQdWJsaXNoZXIy NjM5ODQ=