# 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