894 CHAPTER 13 Graph Theory 8. Use Fleury’s algorithm to determine an Euler circuit in the following graph. ADEAFEHFIGFBGCBA , , , , , , , , , , , , , , , ;otheranswersare possible. A B C D E H I F G 9. In the following graph, determine a Hamilton path. B A D E F C G , , , , , , ; other answers are possible. D E F G A B C 10. In the following graph, determine a Hamilton circuit. ABCGEDHIKJFA , , , , , , , , , , , ; other answers are possible. G K H I D E J F C B A 11. Draw a complete graph with five vertices. * 12. Senate Campaign Tamiko is campaigning in Arizona for the U.S. Senate. Tamiko lives in Yuma and she wishes to travel to the following cities: Flagstaff, Phoenix, Tombstone, Tucson, and Winslow. How many different ways can Tamiko visit each city and return to her home in Yuma? 5! 120 ways = Business Travel In Exercises 13–15, use the following information. Doug is a purchasing agent for Champs Sports C( ). For his job, he must travel to meet with representatives from the following sports companies: Nike N( ), Reebok R( ), and Under Armour U( ). The prices of one-way flights between the corresponding cities for these companies are as follows: Champs to Nike is $253, Champs to Reebok is $114, Champs to Under Armour is $122, Nike to Reebok is $199, Nike to Under Armour is $183, and Reebok to Under Armour is $112. 13. Represent this traveling salesman problem with a complete weighted graph showing the prices of flights on the appropriate edges. * 14. Use the brute force method to determine the least expensive route for Doug to visit each company and return to Champs Sports. What is the cost of this route? C R N U C , , , , or C U N R C , , , , for$618 15. Use the nearest neighbor method to approximate the optimal route for Doug to visit each company and return to Champs Sports. What is the cost of this route? C R U N C , , , , for$662 16. Family Tree Use a tree to show the parent–child relationships in the following family. Beth has three children: Kevin, Demarius, and Teri. Kevin has one child, Chris. Demarius has two children: Michelle and April. Teri has one child, Lucy. * 17. Determine a spanning tree for the following graph. * K A B C D E F G H I J L M 18. Determine the minimum-cost spanning tree for the following graph. * A 3 31 17 7 11 13 23 19 41 37 B E C D F Irrigation System In Exercises 19 and 20, use the following information. Daniel is planning a new irrigation system for his yard. His current system has valves already in place as shown in the following figure. The numbers shown are in feet. 19. Determine the minimum-cost spanning tree that reaches each valve. * 20. If the new irrigation materials cost $1.25 per foot, what would be the cost of installing the system determined in part (a)? $183.75 45 98 65 29 41 73 32 57 51 Valve 1 Valve 3 Valve 4 Valve 5 Valve 2 0n 0ff 0n 0ff 0n 0ff 0n 0ff 0n 0ff *See Instructor Answer Appendix
RkJQdWJsaXNoZXIy NjM5ODQ=