13.1 Graphs, Paths, and Circuits 849 A B C D E F G H A C B D D C B A (a) (b) (c) Figure 13.17 We next discuss an important type of edge called a bridge. Definition: Bridge A bridge is an edge that, if removed from a connected graph, would create a disconnected graph. Fig. 13.18 shows graphs with bridges indicated. Compare these graphs with those in Fig. 13.17. The graphs in Fig. 13.18 are the same graphs as those in Fig. 13.17 with a bridge added. Note in Fig. 13.18(c) that, in addition to edge AB that we added, edges AD and BC are also bridges. If edge AD were removed, vertex D would be isolated from the rest of the graph and we would have a disconnected graph. If edge BC were removed, vertex C would be isolated from the rest of the graph. Note that our graph theory definition of bridge is different from bridges as they are used in the Königsberg bridge problem. In the Königsberg bridge problem, none of the edges that represent real bridges is a bridge in the graph theory sense. A B C D E F G H A C B D D C B A (a) (b) (c) Bridge Bridge Bridge Bridge Bridge Figure 13.18 Exercises Warm Up Exercises In Exercises 1–8, fill in the blanks with an appropriate word, phrase, or symbol(s). 1. A finite set of points connected by line segments is called a(n) _______. Graph 2. A point in a graph is called a(n) _______. Vertex 3. A line segment in a graph is called a(n) _______. Edge 4. An edge that connects a vertex to itself is called a(n) _______. Loop 5. A sequence of adjacent vertices and the edges connecting them is called a(n) _______. Path 6. A path that begins and ends with the same vertex is called a(n) _______. Circuit SECTION 13.1 Instructor Resources for Section 13.1 in MyLab Math • Objective-Level Videos 13.1 • PowerPoint Lecture Slides 13.1 • MyLab Exercises and Assignments 13.1
RkJQdWJsaXNoZXIy NjM5ODQ=