IntroductionTypesClassesBipartite GraphsRepresentationsIsomorphismComputabilityExampleIdentifying `Candidates'ConnectivityEuler & HamiltonianGraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianGraphsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSections 9.1-9.5 of [email protected] / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianIntroduction 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 thatcreated an island and then split off into two parts.Seven bridges were built so that pe ople could easily get around.Euler wondered, is it possible to walk around K¨onigsberg,crossing every bridge exactly once?2 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianIntroduction II3 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianIntroduction 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.v1v2v3v4b0b1b2b3b4b5b64 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianIntroduction IVThe question now become s, does there exist a path in thefollowing graph such that every edge is traversed exactly once?v1v2v3v4b4b5b6b0b1b2b35 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianDefinitions IDefinitionA simple graph G = (V, E) is a 2-tuple withV = {v1, v2, . . . , vn} – a finite set of vertices.E = V × V = {e1, e2, . . . , em} – an unordered set ofedges where each ei= (v, v0) is an unordered pair ofvertices, v, v0∈ V .Since V and E are sets, it makes sense to consider theircardinality. As is standard, |V | = n denotes the number ofvertices in G and |E| = m denotes the number of edges in G.6 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianDefinitions IIA multigraph is a graph in which the edge set E is amultiset. Multiple distinct (or parallel) edges can existbetween vertices.A pseudograph is a graph in which the edge set E canhave edges of the form (v, v) called loopsA directed graph is one in which E contains ordered pairs.The orientation of an edge (v, v0) is said to be “from v tov0”.A directed multigraph is a multigraph whose edges setconsists of ordered pairs.7 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianDefinitions IIIIf we look at a graph as a relation then, among other things,Undirected graphs are symmetric.Non-pseudographs are irreflexive.Multigraphs have nonnegative integer entries in theirmatrix; this corresponds to degree s of relatedness.Other types of graphs can include labeled graphs (each edgehas a uniquely identified label or weight), colored graphs (edgesare colored) etc.8 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianTerminologyAdjacencyFor now, we will concern ourselves with simple, undirectedgraphs. We now look at some more 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 andv.Edge e is said to connect u and v.u and v are also called the endpoints of e.9 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianTerminologyDegreeDefinitionThe degree of a vertex in an undirected graph G = (V, E) isthe number 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.10 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianTerminologyHandshake 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 thedegree of each vertex, deg(v), deg(v0). If e = (v, v) is a loopthen it contributes 2 to deg(v). Therefore, the total degreeover all vertices will be twice the number of edges.11 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianTerminologyHandshake LemmaCorollaryAn undirected graph has an even number of vertices of odddegree.12 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianTerminology - Directed Graphs IIn a directed graph (digraph), G = (V, E), we have analogousdefinitions.Let e = (u, v) ∈ E.u is adjacent to or incident on v.v is adjacent from or incident from u.u is the initial vertex.v is the terminal vertex.For a loop, these are the same.13 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianTerminology - Directed Graphs IIWe make a distinction between incoming and outgoing edgeswith respect to degree.Let v ∈ V .The in-degree of v is the number of edges incident on vdeg−(v)The out-degree of v is the number of edges incident fromv.deg+(v)14 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianTerminology - Directed Graphs IIIEvery edge e = (u, v) contributes 1 to the out-degree of u and1 to the in-degree of v. Thus, the sum over all vertices is thesame.TheoremLet G = (V, E) be a directed graph. ThenXv∈Vdeg−(v) =Xv∈Vdeg+(v) = |E|15 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianMore 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 − 116 / 56GraphsCSE235IntroductionTypesClassesRepresentationsIsomorphismConnectivityEuler &HamiltonianMore 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 morethan once. From now on we will only consider simple paths andcycles.17 /
View Full Document