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 n E K x x 1 i 1 i n E K x y x y 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 to H There exists a bijective function f1 V G V H and a bijective function f2 E G E H 1 Traversing a Graph Name Walk Repeated Edges allowed Repeated Verticies allowed Same end start allowed Path NO allowed allowed Simple Path NO NO NO Closed Walk allowed allowed YES Circuit NO allowed YES Simple Circuit NO only the start end YES Euler Circuit A 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 once G has an Euler Circuit G is a connected graph and Every vertex of G has even degree Hamiltonian 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 edge 2
View Full Document
Unlocking...