1Graphs• 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 twiceIsomorphism• (G is isomorphic to H) ↔ There exists a bijective function f1:(V(G)) → V(H) and a bijectivefunction f2:(E(G)) →E(H) −==11))((xixiKEnyxKEnyx*))((,=2Traversing a GraphYESonly the start/end NOSimple CircuitYESallowedNOCircuitYESallowed allowedClosed WalkNONONOSimple PathallowedallowedNOPathallowedallowedallowedWalkSame end/startRepeated VerticiesRepeated EdgesNameEuler 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 degreeHamiltonian 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
View Full Document
Unlocking...