GraphsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSections 9.1-9.5 of [email protected] IGraph theory was introduced in the 18th century by LeonhardEuler via the K¨onigsberg bridge problem.In K¨onigsberg (old Prussia), a river ran through town that createdan island and then split off into two parts.Seven bridges were built so that people could easily get around.Euler wondered, is it possible to walk around K¨onigsberg, crossingevery bridge exactly once ?Introduction IIIntroduction IIITo solve this problem, we need to model it mathematically.Specifically, we can define a graph whose vertices are the landareas and whose edges are the bridges.v1v2v3v4b0b1b2b3b4b5b6Introduction IVThe question now becomes, does there exist a path in thefollowing graph such that every edge is traversed exactly once?v1v2v3v4b4b5b6b0b1b2b3Definitions IDefinitionA simple graph G = (V, E) is a 2-tuple withIV = {v1, v2, . . . , vn} – a finite set of vertices.IE = V × V = {e1, e2, . . . , em} – an unordered set of edgeswhere each ei= (v, v0) is an unordered pair of vertices,v, v0∈ V .Since V and E are sets, it makes sense to consider theircardinality. As is standard, |V | = n denotes the number of verticesin G and |E| = m denotes the number of edges in G.Definitions IIIA multigraph is a graph in which the edge set E is a multiset.Multiple distinct (or parallel) edges can exist between vertices.IA pseudograph is a graph in which the edge set E can haveedges of the form (v, v) called loopsIA directed graph is one in which E contains ordered pairs.The orientation of an edge (v, v0) is said to be “from v to v0”.IA directed multigraph is a multigraph whose edges setconsists of ordered pairs.Definitions IIIIf we look at a graph as a relation then, among other things,IUndirected graphs are symmetric.INon-pseudographs are irreflexive.IMultigraphs have nonnegative integer entries in their matrix;this corresponds to degrees of relatedness.Other types of graphs can include labeled graphs (each edge has auniquely identified label or weight), colored graphs (edges arecolored) etc.TerminologyAdjacencyFor now, we will concern ourselves with simple, undirected graphs.We now look at som e m ore terminology.DefinitionTwo vertices u, v in an undirected graph G = (V, E) are calledadjacent (or neighbors) if e = (u, v) ∈ E.We say that e is incident with or incident on the vertices u and v.Edge e is said to connect u and v.u and v are also called the endpoints of e.TerminologyDegreeDefinitionThe degree of a vertex in an undirected graph G = (V, E) is thenumber of edges incident with it.The degree of a vertex v ∈ V is denoteddeg(v)In a multigraph, a loop contributes to the degree twice.A vertex of degree 0 is called isolated.TerminologyHandshake TheoremTheoremLet G = (V, E) be an undirected graph. Then2|E| =Xv∈Vdeg(v)The handshake lemma applies even in multi and pseudographs.proof By definition, each e = (v, v0) will contribute 1 to the degreeof each vertex, deg(v), deg(v0). If e = (v, v) is a loop then itcontributes 2 to deg(v). Therefore, the total degree over allvertices will be twice the number of edges.TerminologyHandshake LemmaCorollaryAn undirected graph has an even number of vertices of odd degree.Terminology - Directed Graphs IIn a directed graph (digraph), G = (V, E), we have analogousdefinitions.ILet e = (u, v) ∈ E.Iu is adjacent to or incident on v.Iv is adjacent from or incident from u.Iu is the initial vertex.Iv is the terminal vertex.IFor a loop, these are the same.Terminology - Directed Graphs IIWe make a distinction between incoming and outgoing edges withrespect to degree.ILet v ∈ V .IThe in-degree of v is the number of edges incident on vdeg−(v)IThe out-degree of v is the number of edges incident from v.deg+(v)Terminology - Directed Graphs IIIEvery edge e = (u, v) contributes 1 to the out-degree of u and 1 tothe in-degree of v. Thus, the sum over all ve rtices is the same.TheoremLet G = (V, E) be a directed graph. ThenXv∈Vdeg−(v) =Xv∈Vdeg+(v) = |E|More Terminology IA path in a graph is a sequence of vertices,v1v2· · · vksuch that (vi, vi+1) ∈ E for all i = 1, . . . , k − 1.We can denote suc h a path by p : v1 vk.The length of p is the number of edges in the path,|p| = k − 1More Terminology IIA cycle in a graph is a path that begins and ends at the samevertex.v1v2· · · vkv1Cycles are also called circuits .We define paths and cycles for directed graphs analogously.A path or cycle is called sim ple if no verte x is traversed more thanonce. From now on we will only consider simple paths and cycles.Classes Of GraphsIComplete Graphs – Denoted Knare simple graphs with nvertices where every pos sible e dge is present.ICycle Graphs – Denoted Cnare simply cycles on n vertices.IWheels – Denoted Wnare cycle graphs (on n ve rtices) withan additional vertex connected to all other vertices.In-cubes – Denoted Qnare graphs with 2nverticescorresponding to each bit string of length n. Edges connectvertices whose bit strings differ by a single bit.IGrid Graphs – finite graphs on the N × N grid.Bipartite GraphsDefinitionA graph is called bipartite if its vertex set V can be partitionedinto two disjoint subsets L, R such that no pair of vertices in L (orR) is connected.We often use G = (L, R, E) to denote a bipartite graph.Bipartite GraphsTheoremA graph is bipartite if and only if it contains no odd-length cycles.Another way to look at this theorem is as follows. A graph G canbe colored (here, we color vertices) by at most 2 colors such thatno two adjacent vertices have the same color if and only if G isbipartite.Bipartite GraphsA bipartite graph is complete if every u ∈ L is connected to everyv ∈ R. We denote a complete bipartite graph asKn1,n2which means that |L| = n1and |R| = n2.Examples?Decomposing & Composing Graphs IWe can (partially) decompose graphs by considering subgraphs.DefinitionA subgraph of a graph G = (V, E) is a graph H = (V0, E0) whereIV0⊆ V andIE0⊆ E.Subgraphs are simply part(s) of the original graph.Decomposing & Composing Graphs IIConversely, we can combine graphs.DefinitionThe union of two graphs G1= (V1, E1) and G2= (V1, E1) isdefined to be G = (V , E) whereIV = V1∪ V2andIE = E1∪ E2.Data Structures IA graph can be implemented as a data structure using one of threerepresentations:1. Adjacency list (vertices to list of vertices)2.
View Full Document
Unlocking...