Graph Theory PDF

G RAPH T HEORY Renjith P. NITC Graph Theory 1 / 35 An old story The town of Konigsberg, Prussia (now called Kaliningrad and part of the Russian republic), was divided into four sections by the branches of the Pregel River. These four sections included the two regions on the bank...

G RAPH T HEORY Renjith P. NITC Graph Theory 1 / 35 An old story The town of Konigsberg, Prussia (now called Kaliningrad and part of the Russian republic), was divided into four sections by the branches of the Pregel River. These four sections included the two regions on the banks of the Pregel, Kneiphof Island, and the region between the two branches of the Pregel. In the eighteenth century seven bridges connected these regions. NITC Graph Theory 2 / 35 An old story The townspeople took long walks through town on Sundays. They wondered whether it was possible to start at some location in the town, travel across all the bridges once without crossing any bridge twice, and return to the starting point. The Swiss mathematician Leonhard Euler solved this problem. His so- lution, published in 1736, may be the first use of graph theory. Euler studied this problem using the multigraph obtained when the four re- gions are represented by vertices and the bridges by edges. The prob- lem of traveling across every bridge without crossing any bridge more than once can be rephrased in terms of this model. The question becomes: Is there a simple circuit in this multigraph that contains every edge? NITC Graph Theory 3 / 35 Euler circuit An Euler circuit in a graph G is a simple circuit containing every edge of G. A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree NITC Graph Theory 4 / 35 Euler Trail An Euler trail in G is a simple trail containing every edge of G. A connected multigraph has an Euler trail but not an Euler circuit if and only if it has exactly two vertices of odd degree Which among the following has an Euler trail? NITC Graph Theory 5 / 35 Applications? Many puzzles ask you to draw a picture in a continuous motion with- out lifting a pencil so that no part of the picture is retraced. We can solve such puzzles using Euler circuits and paths. Traverses each street in a neighborhood graph, each road in a trans- portation network, each connection in a utility grid, or each link in a communications network exactly once! NITC Graph Theory 6 / 35 Hamiltonian Path and Cycle ? A simple path in a graph G that passes through every vertex exactly once is called a Hamilton path ? A simple cycle in a graph G that passes through every vertex exactly once is called a Hamilton cycle ? This terminology comes from a game, called the Icosian puzzle, invented in 1857 by the Irish mathematician Sir William Rowan Hamilton ? It consisted of a wooden dodecahedron [a polyhedron with 12 regular pentagons as faces] with a peg at each vertex of the dodecahedron, and string ? The 20 vertices of the dodecahedron were labeled with different cities in the world. ? The object of the puzzle was to start at a city and travel along the edges of the dodecahedron, visiting each of the other 19 cities exactly once, and end back at the first city. NITC Graph Theory 7 / 35 Dodecahedron Which are having HC, HP? NITC Graph Theory 8 / 35 Characterization ? There are no known simple necessary and sufficient criteria for the existence of Hamilton cycles ? However, many theorems are known that give sufficient conditions for the existence of Hamilton cycles ? Certain properties can be used to show that a graph has no Hamilton cycle ? A graph with a vertex of degree one (pendant vertex) cannot have a Hamilton cycle ? A graph with a cut vertex cannot have a Hamilton cycle ? If a vertex in the graph has degree two, then both edges that are incident with this vertex must be part of any Hamilton cycle NITC Graph Theory 9 / 35 Sufficient Conditions Dirac’s Theorem If G is a simple graph with n vertices with n ≥ 3 such that the degree of every vertex in G is at least n/2, then G has a Hamilton cycle Ore’s Theorem If G is a simple graph with n vertices with n ≥ 3 such that deg(u) + deg(v) ≥ n for every pair of nonadjacent vertices u and v in G, then G has a Hamilton cycle Note: The best algorithms known for finding a Hamilton cycle in a graph or determining that no such cycle exists have exponential worst- case time complexity NITC Graph Theory 10 / 35 Applications ? The famous travelling salesperson problem or TSP asks for the shortest route a travelling salesperson should take to visit a set of cities ? This problem reduces to finding a Hamilton circuit in a complete graph such that the total weight of its edges is as small as possible ? A Gray code is a labeling of the arcs of the circle such that adjacent arcs are labelled with bit strings that differ in exactly one bit ? We can model this problem using the n-cube Qn ? What is needed to solve this problem is a Hamilton circuit in Qn NITC Graph Theory 11 / 35 Practice Questions NITC Graph Theory 12 / 35 Practice Questions NITC Graph Theory 13 / 35 Practice Questions NITC Graph Theory 14 / 35 Practice Questions NITC Graph Theory 15 / 35 Practice Questions ? For which values of m and n does the complete bipartite graph Km,n have a Hamiltonian cycle? ? For which values of n do these graphs have an Euler circuit? a) Kn b) Cn c) Wn d) Qn ? For which values of n do these graphs have an Euler trail but no Euler circuit? a) Kn b) Cn c) Wn d) Qn ? For which values of m and n does the complete bipartite graph Km,n have an a) Euler circuit? b) Euler trail? ? All connected 2-regular graphs have a Hamiltonian cycle - True or False? ? All connected 3-regular graphs have a Hamiltonian cycle - True or False? NITC Graph Theory 16 / 35 Planar Graphs ? Is it possible to join these houses and utilities so that none of the connections cross? ? This problem can be modeled using the complete bipartite graph K3,3 ? Whether a graph can be drawn in the plane without edges crossing NITC Graph Theory 17 / 35 Planar Graphs A graph is called planar if it can be drawn in the plane without any edges crossing (where a crossing of edges is the intersection of the lines or arcs representing them at a point other than their common endpoint) Such a drawing is called a planar representation of the graph. ? Is K4 planar? ? Is Q3 planar? ? Is K3,3 planar? NITC Graph Theory 18 / 35 Applications ? Planarity of graphs plays an important role in the design of electronic circuits ? We can print an electronic circuit on a single board with no connections crossing if the graph representing the circuit is planar ? If the graph is not planar, we can partition the vertices in the graph representing the circuit into planar subgraphs ? Then construct the circuit using multiple layers ? A second option - draw the graph with the fewest possible crossings and insulate wires whenever connections cross ? The planarity of graphs is also useful in the design of road networks ? We can built this road network without using underpasses or overpasses if the resulting graph is planar NITC Graph Theory 19 / 35 Euler’s Formula ? A planar representation of a graph splits the plane into regions ? Euler showed that all planar representations of a graph split the plane into the same number of regions ? He accomplished this by finding a relationship among the number of regions, the number of vertices, and the number of edges of a planar graph Let G be a connected planar simple graph with e edges and v vertices. Let r be the number of regions in a planar representation of G. Then r = e - v + 2 NITC Graph Theory 20 / 35 Euler’s Formula Let G be a connected planar simple graph with e edges and v vertices. Let r be the number of regions in a planar representation of G. Then r = e - v + 2 Proof We will prove the theorem by constructing a sequence of subgraphs G1 , G2 ,... , Ge = G Proof by Induction on the number of edges ? Base case: e1 = 1, v1 = 2, and r1 = 1. The relationship r1 = e1 − v1 + 2 is true for the graph K2 = G1 ? IH: Assume that rk = ek − vk + 2 is true for all connected planar simple graphs on k edges k ≥ 1 ? IS: There are two possibilities to consider ? Let {ak+1 , bk+1 } be the edge that is added to Gk to obtain Gk+1 NITC Graph Theory 21 / 35 Euler’s Formula Proof. ? These two vertices must be on the boundary of a common region R and the addition of this new edge splits R into two regions ? Consequently, in this case, rk+1 = rk + 1, ek+1 = ek + 1, and vk+1 = vk ? Therefore, rk+1 = ek+1 − vk+1 + 2 ? In the second case, one of the two vertices of the new edge is not already in Gk ? Consequently, in this case, rk+1 = rk , ek+1 = ek + 1, and vk+1 = vk + 1 ? Therefore, rk+1 = ek+1 − vk+1 + 2 NITC Graph Theory 22 / 35 An Illustration NITC Graph Theory 23 / 35 Corollaries Corollary If G is a connected planar simple graph, then G has a vertex of degree not exceeding five Def: Degree of a region, is defined to be the number of edges on the boundary of this region Corollary If G is a connected planar simple graph with e edges and v vertices, where v ≥ 3, then e ≤ 3v − 6 P Proof 2e = deg (R) ≥ 3r =⇒ (2/3)e ≥ r all regions R Using Euler’s formulae r = e − v + 2, (2/3)e ≥ e − v + 2 It follows that e/3 ≤ v − 2 This shows that e ≤ 3v − 6 NITC Graph Theory 24 / 35 Corollaries 1 Is K5 planar? 2 Is K3,3 planar? Corollary If G is a connected planar simple graph with e edges and v vertices, where v ≥ 3, and no circuits of length three, then e ≤ 2v − 4 P Proof 2e = deg (R) ≥ 4r =⇒ (1/2)e ≥ r all regions R Using Euler’s formulae r = e − v + 2, (1/2)e ≥ e − v + 2 It follows that e/2 ≤ v − 2 This shows that e ≤ 2v − 4 NITC Graph Theory 25 / 35 Kuratowski’s Theorem A graph is nonplanar if and only if it contains a subgraph homeomorphic to K3,3 or K5 ? If a graph is planar, so will be any graph obtained by removing an edge {u,v} and adding a new vertex w together with edges {u,w} and {w,v} ? Such an operation is called an elementary subdivision ? The graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ) are called homeomorphic if they can be obtained from the same graph by a sequence of elementary subdivisions NITC Graph Theory 26 / 35 Kuratowski’s Theorem A graph is nonplanar if and only if it contains a subgraph homeomorphic to K3,3 or K5 ? It is clear that a graph containing a subgraph homeomorphic to K3,3 or K5 is nonplanar ? The proof of the converse, namely that every nonplanar graph contains a subgraph homeomorphic to K3,3 or K5 , is complicated NITC Graph Theory 27 / 35 Practice Questions ? Which of these nonplanar graphs have the property that the removal of any vertex and all edges incident with that vertex produces a planar graph? a) K5 b) K6 c) K3,3 d) K3,4 ? Determine whether the given graph is homeomorphic to K3,3 NITC Graph Theory 28 / 35 Practice Questions ? Determine whether the given graph is planar. If so, draw it so that no edges cross. NITC Graph Theory 29 / 35 Graph Coloring ? Each map in the plane can be represented by a graph ? Each region of the map is represented by a vertex ? Edges connect two vertices if the regions represented by these vertices have a common border ? Two regions that touch at only one point are not considered adjacent ? The resulting graph is called the dual graph of the map ? Any map in the plane has a planar dual graph NITC Graph Theory 30 / 35 Graph Coloring ? The problem of coloring the regions of a map is equivalent to the problem of coloring the vertices of the dual graph so that no two adjacent vertices in this graph have the same color A proper coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color NITC Graph Theory 31 / 35 Graph Coloring The chromatic number of a graph is the least number of colors needed for a coloring of this graph. The chromatic number of a graph G is denoted by χ(G ) The chromatic number of a planar graph is no greater than four ? Nonplanar graphs can have arbitrarily large chromatic numbers ? What is the chromatic number of Kn ? ? What is the chromatic number of the complete bipartite graph Km,n ? ? What is the chromatic number of the graph Cn , Wn ? ? What is the chromatic number of the Peterson’s graph? NITC Graph Theory 32 / 35 Applications of Graph Colorings 1 Scheduling Final Exams Vertices representing courses Edge between two vertices if there is a common student in the courses they represent ? Each time slot for a final exam is represented by a different color ? A scheduling of the exams corresponds to a coloring of the associated graph 2 Frequency Assignments No two nearby stations can operate on the same frequency 3 Register Allocation With the minimum available registers you need to execute a set of instructions NITC Graph Theory 33 / 35 Three Problems ? A Clique in a simple undirected graph is a complete subgraph of the graph ? A maximal Clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph ? A set of non adjacent vertices is called an Independent set of a graph ? A maximal Independent set of a simple undirected graph is an Independent set that is not contained in any larger Independent set ? A set V 0 ⊆ V (G ) of a graph G (V , E ) is called a Vertex cover if for all edges e ∈ E (G ), e is adjacent to at lease one vertex in V 0 ? A minimal Vertex cover of a simple undirected graph G is a vertex cover that does not contain another vertex cover of G as a proper subgraph NITC Graph Theory 34 / 35 Highlights A maximal Independent in a simple undirected graph G is a maximal clique in G For a simple undirected graph G , K ⊆ V (G ) is a maximal independent set if and only if V (G ) \ K is a minimal vertex cover in G NITC Graph Theory 35 / 35