Koofers

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 Function
  • Simple Graph
  • Infinite Sets
  • Combinations
  • Connected Graph
  • Complete Graph
  • Propositional
  • Introduction
  • Isomorphism
  • Euler Circuit
Login / Sign Up to View Document
Preview Page 1Preview Page 2

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
155, "/var/app/current/tmp/"