# Lecture Notes for CMSC 250 - Discrete Structures with Plane at Maryland (UMD)

## Notes Information

 Material Type: Class Note Professor: Plane Class: CMSC 250 - Discrete Structures Subject: Computer Science University: University of Maryland Term: -- Keywords: Bijective FunctionSimple GraphInfinite SetsCombinationsConnected GraphComplete GraphPropositionalIntroductionIsomorphismEuler Circuit  ## Sample Document Text

1 Graphs . Formal Definition of Graph G is 2 finite sets - V(G) = set of vertices & E(G) = set of edges . Example: - 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)} . Variations - digraph : edges are ordered tuples - multi-graph : edge list is a mulitset (bag) not set - simple graph : no parallel edges and no "reflexive loops" - connected graph: can get from any vertex to any other - complete graph: has an edge for every pair of vertices - complete bipartite graph: 2 subsets of vertices (u and v), edge from each v to each u, no edges connecting u elements and no edges connecting v elements . Subgraph: H is a subgraph of G � V(H) ?V(G) and E(H)?E(G) Counting in Graphs . Number of Edges Possible - complete (simple) graph - complete bipartite graph . Degree of a Vertex = number of times that vertex is the endpoint of an edge = number of edges incident on it with self-loops counted twice Isomorphism . (G is isomorphic...

## Related Documents Square Brackets Quiz Square Brackets Quiz Cmsc 250 Quiz Quiz Rational Number Quiz Square Brackets Quiz Square Brackets Quiz Square Brackets Quiz Square Brackets Quiz Either...or Quiz Square Brackets Quiz Definitions Notes Provided That Quiz Square Brackets Quiz Square Brackets Quiz Either...or Quiz Make-to-Order Quiz