## Notes Information

Login / Sign Up to View Document

## 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

© Copyright 2020 , Koofers, Inc. All rights reserved.

The information provided on this site is protected by U.S. and International copyright law, and other applicable intellectual property laws, including laws covering data access and data compilations. This information is provided exclusively for the personal and academic use of students, instructors and other university personnel. Use of this information for any commercial purpose, or by any commercial entity, is expressly prohibited. This information may not, under any circumstances, be copied, modified, reused, or incorporated into any derivative works or compilations, without the prior written approval of Koofers, Inc.