13.2 Euler Paths and Euler Circuits 857 Euler’s theorem can be used to determine whether a graph has an Euler path or an Euler circuit. If an Euler path or Euler circuit exists, how can we determine it? We can always attempt to determine Euler paths and Euler circuits using trial and error. This strategy might work well for simpler graphs. However, we would like to attempt this task with a more systematic approach. Our final topic in this section, Fleury’s algorithm, will give us such an approach. An algorithm is a procedure for accomplishing some task. Euler Circuits FLEURY’S ALGORITHM To determine an Euler path or an Euler circuit: 1. Use Euler’s theorem to determine whether an Euler path or an Euler circuit exists. If one exists, proceed with Steps 2–5. 2. If the graph has no odd vertices (therefore has at least one Euler circuit, which is also an Euler path), choose any vertex as the starting point. If the graph has exactly two odd vertices (therefore has only an Euler path), choose one of the two odd vertices as the starting point. 3. Begin to trace edges as you move through the graph. Number the edges as you trace them. Since you can’t trace any edges twice in Euler paths and Euler circuits, once an edge is traced consider it “invisible.” 4. When faced with a choice of edges to trace, if possible, choose an edge that is not a bridge (i.e., don’t create a disconnected graph with your choice of edges). 5. Continue until each edge of the entire graph has been traced once. PROCEDURE Example 5 Locking a Fitness Center In Section 13.1, Example 3, we introduced the Phenomenal Phitness gym and drew the graph that represented the floor plan. The graph is repeated in Fig. 13.23. Joe runs a gym-cleaning service and is responsible for cleaning the gym and locking all the doors after the gym closes each night. Joe wishes to determine a way to move through the gym using each doorway exactly once. a) Is it possible for Joe to move through the gym using each doorway of the gym exactly one time? In other words, does an Euler path exist in the graph in Fig. 13.23? b) If so, determine one such Euler path. Solution a) To determine if there is an Euler path, we will use Euler’s theorem. The graph in Fig. 13.23 contains exactly two odd vertices, O and A. By item 2 of Euler’s theorem, the graph has at least one Euler path (but no Euler circuit). By Euler’s theorem, the Euler path would have to begin at one of the two odd vertices, either O or A, and end at the other odd vertex. Therefore, Joe could move through the gym and use each doorway of the gym exactly one time by starting at the outside (vertex O) or at locker room A (vertex A). b) In part (a), we determined that an Euler path exists. Now we use Fleury’s algorithm to determine one such path. We can start at either odd vertex, O or A. Let us choose to start at vertex O (see Fig. 13.23). As a matter of convention, once we trace an edge, we will redraw it using a dashed, instead of solid, edge. The dashes will indicate that the edge has already been traced and so it cannot be traced again. At vertex O, there are three choices of edges: the left-side edge OH, the right-side edge OH, or edge OA. None of these edges is a bridge. Thus, if we were to remove any one 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 the left-side edge OH as our first edge and number it 1 (see Fig. 13.24). C S B H A O K G Figure 13.23 Start here C S B H A O 1 2 K G Figure 13.24
RkJQdWJsaXNoZXIy NjM5ODQ=