This chapter continues with the learning approaches of Chapter 4: provide many examples to imitate and problem-solving guidelines to help you reason through difficult problems. This chapter extends your knowledge of query formulation to advanced matching problems. To solve these advanced matching problems, additional parts of the SELECT statement are introduced. | (CSC 102) Lecture 29 Discrete Structures Graphs Previous Lecture Graphs Directed Graphs Simple Graphs Complete Graphs Complete Bipartite Graphs Subgraphs The Concept of Degree Today’s Lecture Subgraphs The Concept of Degree Walks, Trails, Paths and Circuits Connectedness Connected Components Euler Circuits Constructing an Euler Circuits SubGraphs Example SubGraphs The Concept of Degree Degree of a Vertex and Total Degree of a Graph Find the degree of each vertex of the graph G shown below. Then find the total degree of G. The Concept of Degree The Concept of Degree Walks Let G be a graph, and let v and w be vertices in G. A walk from v to w is a finite alternating sequence of adjacent vertices and edges of G. Thus a walk has the form v0e1v1e2 · · · vn−1envn, where the v’s represent vertices, the e’s represent edges, v0 = v, vn = w, and for all i = 1, 2, . . . n, vi−1 and vi are the endpoints of ei. The trivial walk from v to v consists of the single vertex v. Definitions A trail from v to w is a walk from v to w that does not contain a repeated edge. A path from v to w is a trail that does not contain a repeated vertex. A closed walk is a walk that starts and ends at the same vertex. A circuit is a closed walk that contains at least one edge and does not contain a repeated edge. A simple circuit is a circuit that does not have any other repeated vertex except the first and last. For ease of reference, these definitions are summarized in the following table: Cont Often a walk can be specified unambiguously by giving either a sequence of edges or a sequence of vertices. Notations for Walk Example: Trails, Paths, Circuits Cont Cont Solution Connectedness Example Contd Theorem Let G be a graph. If G is connected, then any two distinct vertices of G can be connected by a path. b. If vertices v and w are part of a circuit in G and one edge is removed from the circuit, then there still exists a trail from v to w in G. c. If G is connected and G contains a circuit, . | (CSC 102) Lecture 29 Discrete Structures Graphs Previous Lecture Graphs Directed Graphs Simple Graphs Complete Graphs Complete Bipartite Graphs Subgraphs The Concept of Degree Today’s Lecture Subgraphs The Concept of Degree Walks, Trails, Paths and Circuits Connectedness Connected Components Euler Circuits Constructing an Euler Circuits SubGraphs Example SubGraphs The Concept of Degree Degree of a Vertex and Total Degree of a Graph Find the degree of each vertex of the graph G shown below. Then find the total degree of G. The Concept of Degree The Concept of Degree Walks Let G be a graph, and let v and w be vertices in G. A walk from v to w is a finite alternating sequence of adjacent vertices and edges of G. Thus a walk has the form v0e1v1e2 · · · vn−1envn, where the v’s represent vertices, the e’s represent edges, v0 = v, vn = w, and for all i = 1, 2, . . . n, vi−1 and vi are the endpoints of ei. The trivial walk from v to v consists of the single vertex v. Definitions A trail from
