13.1 Graphs, Paths, and Circuits 847 Now that we have some experience using graphs to represent real-life settings, we will introduce some additional vocabulary used in graph theory. We will begin with a method of classifying vertices. The degree of a vertex is the number of edges that connect to that vertex. For instance, in Fig. 13.13, vertex A has two edges connected to it. Therefore, the degree of vertex A is two. We also see from Fig. 13.13 that vertex B has three edges connected to it, as does vertex C. Therefore, vertices B and C each have degree three. Vertex D has a loop connected to it. A question arises: Should loop DD count as one edge or two edges when determining the degree of vertex D? We will agree to count each end of a loop when determining the degree of a vertex. Thus, vertex D from Fig. 13.13 will have degree four. A vertex with an even number of edges connected to it is an even vertex, and a vertex with an odd number of edges connected to it is an odd vertex. In Fig. 13.13, vertices A and D are even and vertices B and C are odd. Palm Aire Boulevard Cypress Lakes Boulevard O’Keefe Lane Sabino Lane Runde Circle Thomas Drive D’Amato Drive Buckhout Drive Scott Drive Altieri Drive Dittell Drive Terpstra Lane Figure 13.11 Solution In this problem, the vertices will represent the street intersections and the edges will represent the street blocks. We will use the letters A B C K , , , ,… to name the vertices. The resulting graph is shown in Fig. 13.12. A B E F G C D H J I K Figure 13.12 7 Now try Exercise 39 A B C D Figure 13.13 Learning Catalytics Keyword: Angel-SOM-13.1 (See Preface for additional details) Paths, Circuits, and Bridges We next introduce some definitions of graph theory that can be used to describe “movement.” Definition: Path A path is a sequence of adjacent vertices and the edges connecting them. By adjacent vertices, we mean two vertices that are connected by a common edge. For example, in Fig. 13.13, vertices A and B are adjacent vertices, since there is a common edge between vertex A and vertex B. Vertices A and D are not adjacent vertices, since there is not a common edge between vertex A and vertex D. An example of a path is given in Fig. 13.14. It is important to recognize the difference between
RkJQdWJsaXNoZXIy NjM5ODQ=