848 CHAPTER 13 Graph Theory a graph and a path. In Fig. 13.14, the graph is the set of black vertices and the blue edges connecting them. The path, shown in red, can be thought of as movement from vertex C to vertex D to vertex A to vertex B. For convenience, and to help in explanations, paths will be referred to with the sequence of vertices separated by commas. For example, the path in Fig. 13.14 will be referred to as path C D A B , , , . Note that path C D A B , , , consists of three separate paths: C D D A , ; , ;and A B, . F E D C B A Figure 13.14 A path does not need to include every edge and every vertex of a graph. In addition, a path could include the same vertices and the same edges several times. For example, in Fig. 13.15, we see a graph with four vertices. The path A B C D A B , , , , , , C D A B C D A B C , , , , , , , , starts at vertex A, “circles” the graph three times, and then goes through vertex B to vertex C. C D B A Figure 13.15 We now will discuss a special kind of path called a circuit. Definition: Circuit A circuit is a path that begins and ends at the same vertex. Examine Fig. 13.16. The path given by A C B D A , , , , forms a circuit. The path given by B D E B , , , forms another circuit. Note that every circuit is, by definition, a path; however, not every path is a circuit. A circuit needs to begin and end at the same vertex. For example, in Fig. 13.16, the path given by A C B D , , , is not a circuit, since it does not begin and end at the same vertex. In Sections 13.2 and 13.3, we will discuss paths and circuits in more depth. Our next definitions classify graphs themselves. A graph is connected if, for any two vertices in the graph, there is a path that connects them. All the graphs we have studied thus far have been connected because a path existed between each pair of vertices in each graph. If a graph is not connected, it is disconnected. Fig. 13.17 shows three examples of disconnected graphs. In Fig. 13.17(c), although edge AD and edge BC cross, the graph is not connected because there is no vertex indicated where the edges cross. D E C B A Figure 13.16
RkJQdWJsaXNoZXIy NjM5ODQ=