In this chapter, the following content will be discussed: More of an interactive demonstration than an animation, demonstrate conceptual execution model of Type II nested queries, type II nested queries are important for solving problems involving difference operator, problems with difference are not common. | (CSC 102) Lecture 30 Discrete Structures Graphs Previous Lecture Subgraphs The Concept of Degree Walks, Trails, Paths and Circuits Connectedness Connected Component of a Graph Euler Circuits Finding an Euler Circuit Today’s Lecture Euler Circuits Finding an Euler Circuit Euler Trails Finding an Euler Trail Hamiltonian Circuits A Traveling Salesman Problem Matrices and Graphs Euler Circuits Theorem If a graph has an Euler circuit, then every vertex of the graph has positive even degree. Contrapositive Version of Theorem If some vertex of a graph has odd degree, then the graph does not have an Euler circuit. Euler Circuits Show that the graph below does not have an Euler circuit. Vertices v1 and v3 both have degree 3, which is odd. Hence by (the contrapositive form of theorem), this graph does not have an Euler circuit. Constructing an Euler Circuit Theorem If a graph G is connected and the degree of every vertex of G is a positive even integer, then G has an Euler circuit. Constructing an Euler Circuit Step I: Pick any vertex v of G at which to start. Step II: Pick any sequence of adjacent vertices and edges, starting and ending at v and never repeating an edge. Call the resulting circuit C. Step III: Check whether C contains every edge and vertex of G. If so, C is an Euler circuit, and we are finished. If not, perform the following steps. Step IIIa: Remove all edges of C from G and also any vertices that become isolated when the edges of C are removed. Call the resulting subgraph G’. Step IIIb: Pick any vertex w common to both C and G’. Step IIIc: Pick any sequence of adjacent vertices and edges of G’, starting and ending at w and never repeating an edge. Call the resulting circuit C’. Step IIId: Patch C and C’ together to create a new circuit C’’ as follows: Start at v and follow C all the way to w. Then follow C’ all the way back to w. After that, continue along the untraveled portion of C to return to v. Step IIIe: Let C = C’’ and go back to step 3. Since the . | (CSC 102) Lecture 30 Discrete Structures Graphs Previous Lecture Subgraphs The Concept of Degree Walks, Trails, Paths and Circuits Connectedness Connected Component of a Graph Euler Circuits Finding an Euler Circuit Today’s Lecture Euler Circuits Finding an Euler Circuit Euler Trails Finding an Euler Trail Hamiltonian Circuits A Traveling Salesman Problem Matrices and Graphs Euler Circuits Theorem If a graph has an Euler circuit, then every vertex of the graph has positive even degree. Contrapositive Version of Theorem If some vertex of a graph has odd degree, then the graph does not have an Euler circuit. Euler Circuits Show that the graph below does not have an Euler circuit. Vertices v1 and v3 both have degree 3, which is odd. Hence by (the contrapositive form of theorem), this graph does not have an Euler circuit. Constructing an Euler Circuit Theorem If a graph G is connected and the degree of every vertex of G is a positive even integer, then G has an Euler circuit. Constructing
