892 CHAPTER 13 Graph Theory 13.3 19. Determine two different Hamilton paths in the following graph. CAEKIFGJLHBD , , , , , , , , , , , and D B H L J G F C A , , , , , , , , , E K I , , ; other answers are possible. A E K B H L I C J D F G 20. Determine two different Hamilton circuits in the following graph. ABEFJILKHGCDA , , , , , , , , , , , , and IJFEBADCGHKLI , , , , , , , , , , , , ; other answers are possible. A B D E K L H C G I F J 21. Draw a complete graph with five vertices. * 22. Baseball The American League Eastern Division has the following teams: Baltimore Orioles, Boston Red Sox, New York Yankees, Tampa Bay Rays, and Toronto Blue Jays. How many different possible ways could a Boston Red Sox fan visit each team in the American League Eastern Division one time and return home to Boston? 4! 24 ways = 23. Job Interviews Lance is searching for a new job. He lives in Portland, Oregon, and has interviews in Des Moines, Iowa; Charleston, West Virginia; and Montgomery, Alabama. The costs of the one-way flights between these four cities are as follows: Portland to Des Moines is $428, Portland to Charleston is $787, Portland to Montgomery is $902, Des Moines to Charleston is $449, Des Moines to Montgomery is $458, and Charleston to Montgomery is $415. a) Represent this traveling salesman problem with a complete, weighted graph showing the prices of the flights on the appropriate edges. * b) Use the brute force method to determine the least expensive route for Lance to travel to each city and return home to Portland. P D M C P , , , , or P C M D P , , , , c) What is the total cost of airfare for Lance’s trip in part (b)? $2088 24. Visiting Sales Offices Jennifer is the sales manager for AT&T for the state of Missouri. There are major sales offices in Columbia, Kansas City, St. Joseph, St. Louis, and Springfield. The distances in miles between these cities are given in the following table. Columbia Kansas City St. Joseph St. Louis Springfield Columbia * 130 177 127 168 Kansas City 130 * 54 256 192 St. Joseph 177 54 * 304 224 St. Louis 127 256 304 * 210 Springfield 168 192 224 210 * a) Represent this traveling salesman problem with a complete, weighted graph showing the prices of the flights on the appropriate edges. * b) Use the nearest neighbor method to approximate the optimal route for Jennifer to begin in St. Joseph, visit each city once, and return to St. Joseph. SJKCCSLSpSJ , , , , , traveling a total of 745 miles c) Suppose that Jennifer starts in Springfield. Use the nearest neighbor method to approximate the optimal route for Jennifer to visit each city once and return to Springfield. SpCSLKCSJSp , , , , , traveling a total of 829 miles 13.4 25. Supervisory Relationships Use a tree to show the supervisory relationships in the Hulka Consulting Corporation. Hulka is president. Winger and Ziskey are vice presidents who work for Hulka. Markowicz, Oxburger, and Soyer are district managers who work for Winger. Elmo, Hector, and Jenesky are district managers who work for Ziskey. * 26. Determine two different spanning trees for the following graph. * C D F G A B E *See Instructor Answer Appendix
RkJQdWJsaXNoZXIy NjM5ODQ=