CHAPTER 13 Review Exercises 891 9. Identify any bridges in the following graph. Edge BD A B D E F G C H I J 13.2 Use the following graph for Exercises 10 and 11. A B G C D E F H 10. Determine an Euler path that begins with vertex C. CABFHGCDEDEF , , , , , , , , , , , ; other answers are possible 11. Determine an Euler path that begins with vertex F. FEDEDCGHFBAC , , , , , , , , , , , ; other answers are possible Use the following graph for Exercises 12 and 13. A B E C G F D 12. Determine an Euler circuit that begins with vertex A. ABEGFDCADEA , , , , , , , , , , 13. Determine an Euler circuit that begins with vertex E. EDCAEBADFGE , , , , , , , , , , 14. Consider the following map. CO NE OK TX KS MO IA a) Represent the map as a graph. * b) Determine (state yes or no) whether the graph has an Euler path. If yes, give one such Euler path. * c) Determine (state yes or no) whether the graph has an Euler circuit. If yes, give one such Euler circuit. No 15. a) The following drawing shows the floor plan of a single-story house. Construct a graph that represents the floor plan. * A C D B E F Outside b) Is it possible for a person to walk through each doorway in the house without using any of the doorways twice? Yes c) If so, where can the person start and where will the person finish? Explain. The person may start in any room or outside and will finish in the location from which he or she started. 16. a) Can a police officer walk each street shown in the following figure without walking any street more than once? Yes b) If yes, where would the police officer have to start the walk? The officer would have to start at either the intersection of Dayne St., Gibson Pl., and Alvarez Ave. or at the intersection of Chambers St., Fletcher Ct., and Alvarez Ave. Vincent Ave. Alvarez Ave. Chambers St. Fletcher Ct. Hall Pl. Gibson Pl. Toon Ct. Dayne St. 17. Use Fleury’s algorithm to determine an Euler path in the following graph. CABGFADCFDBEDGE ,,, ,,, , ,, ,,, , ,;other answers are possible. A B F C D E G 18. Use Fleury’s algorithm to determine an Euler circuit in the following graph. ABDEIJONLKGHLMIHD , , , , , , , , , , , , , , , , , C G F A , , , ; other answers are possible. A B G H I F C E K L M D J O N *See Instructor Answer Appendix
RkJQdWJsaXNoZXIy NjM5ODQ=