874 CHAPTER 13 Graph Theory 14. A B C G D H I J K L E F FCBAHIJKLEDG , , , , , , , , , , , and GDELKJIHABCF , , , , , , , , , , , In Exercises 15–18, determine two different Hamilton circuits in each of the following graphs. 15. H A B C G D F E A B D G E H F C A , , , , , , , , and D B A C F H E G D , , , , , , , , 16. A B C D E F G H I J K L ABCDHLKGFJIEA , , , , , , , , , , , , and AEIJKLHDCGFBA , , , , , , , , , , , , 17. A B E C D F G H I ABCFIEHGDA , , , , , , , , , and AEBCFIHGDA , , , , , , , , , 18. A B C G D H I J E F ABCGJFIEHDA , , , , , , , , , , and BADEHIJFGCB , , , , , , , , , , 19. Draw a complete graph with four vertices. * 20. Draw a complete graph with five vertices. * In Exercises 21 and 22, determine the number of unique Hamilton circuits there are in a complete graph with the given number of vertices. 21. a) Six 120 b) Nine 40,320 22. a) Five 24 b) Twelve 39,916,800 Problem Solving 23. College Visits Tramon is a high school student who lives in Bakersfield, CA, and he wishes to visit colleges in the following cities: St. Cloud, MN; Valparaiso, IN; Lindonville, VT; Asheville, NC; and Norman, OK. In how many different ways can Tramon visit each of these cities and return home to Bakersfield? = 5! 120 ways 24. Culver’s Restaurants Craig, the president of Culver’s Restaurants, is at his home in Prairie du Sac, WI, and wishes to investigate locations for a new restaurant in the following cities: Robinson, IL; Erie, PA; Memphis, TN; Little Rock, AR; Tulsa, OK; Topeka, KS; and Dickinson, ND. In how many ways can Craig visit each of these cities and return to his home in Prairie du Sac? = 7! 5040 ways 25. Florida State League The Florida State League is a minor league baseball organization with teams in Bradenton, Clearwater, Daytona, Dunedin, Fort Myers, Jupiter, Lakeland, Palm Beach, Port Saint Lucie, and Tampa. James, the league commissioner, would like to visit each team and then return to his home in Sarasota. In how many ways can James visit each team and return to his home? 10! 3,628,800 ways = 26. WNBA Cathy, the league commissioner of the WNBA, is at her home in New York City and would like to visit the teams in the following cities: Dallas, Las Vegas, Los Angeles, Minneapolis, Phoenix, and Seattle. In how many ways can Cathy visit each team and return home? = 6! 720 ways 27. Cookie Delivery Brenda is a girl scout and needs to deliver cookies to homes in her town. She will start at her home and deliver orders to 9 different homes. In how many ways can Brenda visit each home and return to her home? 9! 362,880 ways = 28. A Milk Truck Route Dale is a milk truck driver for Swiss Valley Farms Cooperative in eastern Iowa. Dale has to start at the processing plant and pick up milk on 12 different farms. In how many ways can Dale visit each farm and return to the processing plant? = 12! 479,001,600 ways 29. Running Errands on Campus Song needs to run errands on the campus of Pima Community College. She is in her office and needs to go to the duplicating center, student center, and library. She estimates the walking distances as follows: From her office to the duplicating center is 150 feet, from her office to the student center is 100 feet, from her office to the library is 400 feet, from the duplicating center to the student center is 125 feet, from the duplicating center to the library is 450 feet, and from the student center to the library is 250 feet. a) Represent this traveling salesman problem with a complete, weighted graph showing the distances on the appropriate edges. * *See Instructor Answer Appendix Kim Hukari/Image of Sport/ Kirby Lee/Alamy Stock Photo
RkJQdWJsaXNoZXIy NjM5ODQ=