Discrete Structures CMSC 250 Lecture 1Chapter 10, Graph TheoryDefinitionsGraph isomorphismVariations of graphsCounting in graphsTraversing a GraphEuler circuitSlide 9How hard are these problems?1CMSC 250Discrete StructuresCMSC 250Lecture 1January 28, 20082CMSC 250Chapter 10, Graph Theory3CMSC 250DefinitionsThe formal definition of graph G is 2 finite sets:–V(G) = a set of vertices–E(G) = a set of edgesExample:–V(H) = {a,b,c,d,e} E(H) = {{a,c},{c,e},{e,b},{b,d},{d,a}}–V(K) = {a,b,c,d} E(K)= {(a,b),(b,a),(a,d),(d,a),(c,c)}Subgraph: H is a subgraph of G iff V(H) V(G) andE(H) E(G)4CMSC 250Graph isomorphismG is isomorphic to H iff there exists a bijective function f1:(V(G)) V(H) and a bijective function f2:(E(G)) E(H)5CMSC 250Variations of graphsThe edges of a digraph are ordered tuples.The edge list of a multigraph is a multiset (bag), not a set.A simple graph has no parallel edges and no loops (reflexive edges).In a connected graph any vertex is reachable from any other one.A complete graph has an edge between every pair of vertices.A complete bipartite graph has two subsets of vertices (u and v), an edge from each vertex in u to each vertex in v, and no edges connecting any vertices in v to others in v, or connecting any vertices in u to others in u.6CMSC 250Counting in graphsNumber of edges possible–complete (simple) graph–complete bipartite graphDegree of a vertex = number of times that vertex is the endpoint of an edge= number of edges incident on it with self-loops counted twice11))((xixiKEnyxKEnyx*))((,7CMSC 250Traversing a Graph Name Repeated Edges Repeated VerticiesSame end/startWalk allowed allowed allowedPath NO allowed allowedSimple Path NO NO NOClosed Walk allowed allowed YESCircuit NO allowed YESSimple Circuit NO only the start/end YES8CMSC 250Euler circuitA circuit that contains every edge and every vertex–starts and stops at the same point–uses every vertex at least once–uses every edge exactly onceG has an Euler circuit iff G is a connected graph and every vertex of G has even degree9CMSC 250Hamiltonian circuit•A simple circuit that contains every vertex.–starts and stops at the same point–uses every vertex exactly once (except the first and last)–does not repeat an edge10CMSC 250How hard are these problems?Finding a Hamiltonian circuit is thought to be a hard problem.How does it compare with the problem discussed in the first lecture of finding a satisfying assignment for the variables of a Boolean
View Full Document
Unlocking...