858 CHAPTER 13 Graph Theory Now closely examine our position at vertex H. We now must make a choice among the following edges: HG HS HK HC , , , , and the right-side edge HO. None of these edges is a bridge. Thus, if we were to remove any of these edges, we would not create a disconnected graph. Since none of these edges is a bridge, we can choose to trace any one of these edges. Let us choose edge HK and label it edge 2 as shown in Fig. 13.24. Now we are at vertex K. At vertex K, we have no choice but to select edge KB, followed by edge BC, followed by edge CH. We will choose these edges and label them edges 3, 4, and 5, respectively, as in Fig. 13.25. We are now back at vertex H. Examine our position at vertex H in Fig. 13.25. There are three choices of edges: HG HS , , and right-side edge HO. None of these edges is a bridge, so we may choose to trace any one of these edges. Let us choose edge HG and label it 6. That will put us at vertex G, where our only choice is to trace edge GA and label it 7. We are now at vertex A. At vertex A, there is a choice between edges AO and AS. Because neither edge is a bridge, we may choose either one of these edges. Let us choose edge AS and label it 8. Our choices up to this point are shown in Fig. 13.26. We are now at vertex S, where our only choice is to trace edge SH followed by edge HO, followed by edge OA. These edges are labeled 9, 10, and 11, respectively, and the completed Euler path is given in Fig. 13.27. Now try Exercise 29 C S B H A O 1 2 5 3 4 K G Figure 13.25 C S B H A O 1 2 5 6 3 4 7 8 K G Figure 13.26 C S B H A O 1 2 5 6 9 3 4 7 8 11 10 K G Figure 13.27 Notice that we started at one odd vertex, O, and ended at the other odd vertex, A. Therefore, if Joe followed the path OHKBCHGASHOA , , ,, , , ,,, , ,,hewould travel through each doorway exactly one time. Many other Euler paths also exist for this problem. You will be asked to determine another one in Exercise 46. 7 Example 6 Crime Stoppers Problem In Section 13.1, Example 4, we introduced the Greenbriar subdivision of homes and drew a graph to represent it. The graph is repeated in Fig. 13.28 below. The Greenbriar Neighborhood Association is planning to organize a crime stopper group in which residents take turns walking through the neighborhood with cell phones to report any suspicious activity to the police. A B E F G C D H J I K Figure 13.28
RkJQdWJsaXNoZXIy NjM5ODQ=