13.2 Euler Paths and Euler Circuits 859 a) Can the residents of Greenbriar start at one intersection (or vertex) and walk each street block (or edge) in the neighborhood exactly once and return to the intersection where they started? b) If yes, determine a circuit that could be followed to accomplish their walk. Solution a) Since the residents wish to start at one intersection (or vertex) and return to the same intersection (or vertex), we need to determine if this graph has an Euler circuit. From Fig. 13.28, we see that there are no odd vertices. Therefore, by item of Euler’s theorem, we determine that there is at least one Euler circuit. b) In part (a), we determined that an Euler circuit exists. Now we use Fleury’s algorithm to determine one such circuit. Euler’s theorem states that we can start at any vertex to determine an Euler circuit. Let us choose to begin at vertex A. We face a choice of tracing edge AB or edge AE. Since neither edge AB nor edge AE is a bridge, we can choose either edge. Let us choose edge AB. Our first choice is indicated in Fig. 13.29. Start here A 1 B E F G C D H J I K Figure 13.29 We will continue to trace from vertex to vertex around the outside of the graph, as indicated in Fig. 13.30. Notice that no edge chosen is a bridge. Start here A 1 2 B E F G 4 8 C D 3 H J I 6 5 K 7 Figure 13.30 We are now at vertex E. Our choices are edge EA, edge EB, or edge EI. Edge EA is a bridge because removing edge EA would leave vertex A disconnected from the rest of the untraced graph. Neither edge EB nor edge EI is a bridge. Therefore, we need to choose either edge EB or edge EI. Let us choose edge EB. Now we are at vertex B and must choose edge BF. Our choices so far are shown in Fig. 13.31. A H E B C D I J K F G 1 2 3 4 5 6 7 8 9 10 Start here Figure 13.31 Profile in Mathematics Paul Erdös Paul Erdös (1913–1996) was a Hungarian mathematician who worked in many areas of mathematics, including graph theory, topology, number theory, set theory, and probability theory. Erdös’s parents were both mathematics teachers, and he grew up loving to solve mathematics problems. At age 20, Erdös received his doctorate from University Pázmány Péter in Budapest. During his career, Erdös published about 1475 papers — more than any other mathematician in history. He strongly believed in discovering mathematics through social interaction, having 511 different collaborators on his publications. Erdös owned very few possessions, and for most of his career he did not hold a conventional position. Instead, he traveled between various conferences and universities, working with his many collaborators. He often would offer cash rewards for individuals who would solve certain aspects of problems on which he was working. Erdös was recognized for his brilliance by receiving over 15 honorary doctorate degrees from universities all over the world. Erdös worked until the day he died, at age 83, of a heart attack while attending a mathematics conference in Warsaw, Poland.
RkJQdWJsaXNoZXIy NjM5ODQ=