854 CHAPTER 13 Graph Theory Section 13.1 provided us with some of the basic definitions of graph theory. Although we were able to represent physical settings with graphs, we have not yet discussed solving problems related to these settings. In this section, we will provide more details of graph theory, which allows us to reach solutions to the Königsberg bridge problem and other real-world problems. Before we do so, we need to give two more definitions. Definition: Euler Path An Euler path is a path that passes through each edge of a graph exactly one time. If a graph has an Euler path, we say the graph is traversable. If a graph has an Euler path, or is traversable, it is possible to trace the entire graph without removing the pencil from the paper and without tracing an edge more than once. For our next definition, recall that a circuit is a path that begins and ends at the same vertex. Definition: Euler Circuit An Euler circuit is a circuit that passes through each edge of a graph exactly one time. The difference between an Euler path and an Euler circuit is that an Euler circuit must start and end at the same vertex. An alternate definition for an Euler circuit is that it is an Euler path that begins and ends at the same vertex. To become familiar with Euler paths and Euler circuits, examine the graphs in Fig. 13.19(a) and (b). As we discuss each graph, trace each path or circuit with a pencil or with your finger, or draw the path or circuit on a separate sheet of paper. In Fig. 13.19(a), the path D E B C A B D C E , , , , , , , , is an Euler path, since each edge was traced only one time. However, since the path begins at vertex D and ends at a different vertex, E, the path is not a circuit and therefore is not an Euler circuit. In Fig. 13.19(b), the path DEBCABDCEFD , , , , , , , , , , is an Euler path, since each edge was traced only one time. Furthermore, since the path begins and ends with the same vertex, D, it is also an Euler circuit. Note that every Euler circuit is an Euler path, but not every Euler path is an Euler circuit. Our next task is to determine whether a given graph has an Euler path, an Euler circuit, neither, or both. In the next example, we will use trial and error to determine Euler paths and Euler circuits. Our discussion will help us introduce Euler’s theorem, which will be used to solve the Königsberg bridge problem and other problems involving graph theory. C E A B D (a) An Euler path D E, , B C A B D C E , , , , , , Figure 13.19 C E A F B D (b) An Euler circuit D, E B C A B D C , , , , , , , E F D , , Example 1 Euler Paths and Circuits For the graphs shown in Fig. 13.20, determine if an Euler path, an Euler circuit, neither, or both exist. (c) A D B E (a) A B D C E F (b) A E C C D B F Figure 13.20 Learning Catalytics Keyword: Angel-SOM-13.2 (See Preface for additional details.)
RkJQdWJsaXNoZXIy NjM5ODQ=