# graph theory

Information about graph theory

Published on August 26, 2010

Author: shubha64

Source: authorstream.com

Why Graphs? : VIIT CSE II Graph Theory - Unit 8 1 Why Graphs? Graphs can be used to represent many problems in computer science that are otherwise abstract. Finding a way to represent the solution to a problem as a graph can present new approaches to solving the problem or even lead directly to a solution derived from graph theory. Many problems computers are used to solve, involve representing relationships between objects, places or concepts. Because graphs can be either directed or undirected, they are a flexible method of showing connections. Brief History of Graph Theory : VIIT CSE II Graph Theory - Unit 8 2 Brief History of Graph Theory Graph theory was born in 1736 with Euler’s paper on konigsberg bridge problem. Then for next 100 years nothing more was done. In 1847 kirchoft developed a theory of trees for electrical networks. In 1857 Cayley used trees to enumerate isomers of saturated hydrocarbons Cn H2n+2. In 1850 – four colour problem – “to colour atlas 4 colours are sufficient “ was stated by De-Margon in his letter to his friend in London. (The most famous unsolved problem yet) In 1859 – Hamilton put a puzzle on a dodecahedron (having12 faces and 20 corners) 1936- first book on Graph Theory was published by Konig. Thousands of papers have been published in last 75 years. Simple Graph : VIIT CSE II Graph Theory - Unit 8 3 Definition Simple Graph A simple graph G(V,E) consists of V, a nonempty finite set of vertices and E, a set of unordered pairs of distinct elements of V called edges. Simple graphs are often used to represent network models (models with links between elements) where the only information is the location of the connections. Slide 4: VIIT CSE II Graph Theory - Unit 8 4 For example, the following diagram is a graph of a “real world” Local Area Network (LAN). Multigraph and Pseudograph : VIIT CSE II Graph Theory - Unit 8 5 Multigraph and Pseudograph Sometimes we want to model the situation when there more than one connection between some pairs of vertices, which is not allowed in simple graph. Hence, we need the concept of multigraph: Definition A multigraph G(V,E) consists of V, a nonempty finite set of vertices and E, a finite multiset set of unordered pairs of distinct elements of V called edges. Thus, multiple edges between two vertices are allowed in a multigraph. Slide 6: VIIT CSE II Graph Theory - Unit 8 6 Neither simple graphs nor multigraphs may have loops. All such graphs can only have edges between distinct pairs of vertices. In order to allow loops, we need the notion of a pseudograph (multigraph with loops). Definition A pseudograph G(V,E) consists of V, a nonempty finite set of vertices and E, a finite multiset set of unordered pairs of elements of V called edges. Thus, multiple edges between two vertices and loops are allowed in a pseudo graph. An example of a pseudo is shown below: Directed Graph : VIIT CSE II Graph Theory - Unit 8 7 Directed graphs are used when the direction of the connections is important. For example, if traffic in a computer network only flowed in particular directions, we might use a directed graph to model it. A formal definition of directed graph more formally below: Definition A directed graph G(V,E) consists of V, a nonempty finite set of vertices and E, a set of ordered pairs of elements of V called edges. Directed Graph Slide 8: VIIT CSE II Graph Theory - Unit 8 8 One interesting application of directed graph is to specify the hierarchical import relationships between modules. This kind of directed graph is called module dependency graph. Here is an example of a module dependency graph: Slide 9: VIIT CSE II Graph Theory - Unit 8 9 Here is another “small” and colorful example of directed graph: Slide 10: VIIT CSE II Graph Theory - Unit 8 10 Graphs can be used for Utilities Problem: Three houses H1, H2, H3. Three utilities water (W), Gar (G) & electricity (E) each home to be connected to each utility without any crossing over Electrical network problem Seating arrangement in a room Data base management Telephone network systems Bus / Rail transport network Pedigree (family tree) Computer networking Slide 11: VIIT CSE II Graph Theory - Unit 8 11 Finite and infinite graphs: A graph with finite number of vertices and edges is called a finite graph otherwise it is an infinite graph. Incidence: When a vertex Vi is incident on an edge two vertices Vi, Vj are said to be adjacent if they are the end vertices of an edge.   Degree of a vertex: The number of edges incident on a vertex (with self loop counted as 2 ) is called degree of a vertex. And is denoted by d(vi) Slide 12: VIIT CSE II Graph Theory - Unit 8 12 Slide 13: VIIT CSE II Graph Theory - Unit 8 13 Subgraph: Let G(V, E) be a graph, then a graph H (V’, E’) where is said to be a subgraph of G. H is said to be a subgraph induced by its vertex set if its edge set E1 contains all edges from E incident on vertices of V1. Slide 14: VIIT CSE II Graph Theory - Unit 8 14 If v is a vertex in G than G-v is a graph obtained from G by removing the vertex v and all the edges incident on v. If e is an edge in G than G-e is a graph obtained by removing only the edge e from E(G). Slide 15: VIIT CSE II Graph Theory - Unit 8 15 Spanning Subgraph: Given a graph G(V,E) if there is a subset E1 of edges induced on the set of vertices V(G) then G1(V, E1) is a spanning subset of G. Slide 16: VIIT CSE II Graph Theory - Unit 8 16 Isomorphic graphs: Let G(V, E) and G1(V1, E1) be two graphs G and G1 are said to be isomorphic graphs if there exits a one to one correspondence which preserves edges ie (u1, u2) E For isomorphic graphs the necessary conditions are |V| = |V’| |E| = |E’| deg seq (G) = deg seq(G’) Slide 17: VIIT CSE II Graph Theory - Unit 8 17 Euler graph: If we have a closed walk in a graph that contains all the edges then such a closed walk is called an Euler line and the graph is called an Euler graph. Theorem : A connected graph G is an Euler graph iff all vertices in G are of even degree. Slide 18: VIIT CSE II Graph Theory - Unit 8 18 Hamiltonian path and circuit: A Hamiltonian path in a connected graph is a walk that traverses every vertex of G exactly once. If the starting vertex is same as the ending vertex then it is called Hamiltonian Circuit. A graph may contain more than one Hamiltonian Circuits. Result : In a complete graph Kn there are edge disjoint Hamiltonian cycles Chromatic Number of a graph : VIIT CSE II Graph Theory - Unit 8 19 Chromatic Number of a graph The minimum number of colours required to colour the vertices of a graph so that no two adjacent vertices are of same colour is called the chromatic number of the Graph. Chromatic number of Path graph 2 Cycle graph 2 or 3 Star graph 2 Wheel graph 3 or 4 Complete graph n Complete Bipartite graph 2 Null graph is 1 In the same manner we can define edge colouring of a graph. Planar Graph : VIIT CSE II Graph Theory - Unit 8 20 Planar Graph A graph G is said to be a planar graph if the edges in the graph can be drawn without crossing. Smallest non planar graphs are K5 and K3,3. Any graph containing a sub graph isomorphic to K5 and K3,3 is non-planar. Slide 21: VIIT CSE II Graph Theory - Unit 8 21 Paths and Circuits Walk: A finite alternating sequence of vertices & edges. Beginning and ending with vertices is called a walk. Circuit: A closed walk in which no edge is repeated is called circuit. Path: A walk where no vertex is repeated is a path. Circuit: A closed path is called cycle. Connected graph: A graph is a connected graph if there is a path between every pair of vertices, otherwise it is a disconnected graph. . Slide 22: VIIT CSE II Graph Theory - Unit 8 22 Trees and Fundamental circuits: An acyclic connected graph is called a tree. A collection of disconnected graph components, where each component in a tree, is called a forest. A single vertex with no edges is called a degenerate tree. Theorem: Let G be a graph with n>1 vertices then the following are equivalent 1) G is a tree 2) G is cycle free & has (n-1) edges. 3) G is connected & has (n-1)edges. Slide 23: VIIT CSE II Graph Theory - Unit 8 23 Some properties of trees:   There is one and only one path between each pair of vertices in T. A tree with n vertices has (n-1) edges A connected graphs with n vertices & (n-1) edges is a tree. A graph with n vertices & (n-1) edges having no circuits is connected. A graph is a tree if it is minimally connected. In any tree there are at least 2 pendent vertices. Spanning tree of a graph G: A spanning tree T is a subgraph of G s.t. V(G) = V(T) and T is a tree. Minimal spanning tree: A spanning tree of a weighted graph with lowest total weight is a minimal spanning tree of the graph G. Slide 24: VIIT CSE II Graph Theory - Unit 8 24 Matrix representation of graphs Advantages : 1. Diagrammatic representation is possible only when the no. of vertices & edges is reasonably small when it is large it is clumsy & complicated for use. 2. Matrix represent is easy to store and manipulate. 3. Operation of matrix algebra can be used for operation in graphs. Eg. to calculate path, cycles or other char of you   Let G = (V1 E) be a simple graph with V = {v1, v2,……,vn} An n x n matrix A = [aij] where aij = 1 if vi vj is an edge and = 0 otherwise is called an adjacency matrix of G Slide 25: VIIT CSE II Graph Theory - Unit 8 25 V1 V2 V3 V4 V5 V1 0 1 1 0 0 V2 1 0 0 1 0 V 3 1 0 0 1 1 V4 0 1 1 0 1 V5 0 0 1 1 0 V1 V2 V4 V3 V5 Observations 1. For simple graph dia(A) = 0 0 0 ….. 0 2. Row sum gives degree of the vertices 3. A is symmetric as (v1 v2) is an edge means (v2 v1) is also an edge Slide 26: VIIT CSE II Graph Theory - Unit 8 26 4. If two adjacency matrices are such that one can be obtained from the other by interchanging rows then G1 = G2 . 5. For a null graph A = O 6. Only loops & no other edges A = In 7. A2 gives pathsof length 2 between every pair of vertices A3 gives paths of length 3between every pair of vertices ……… An gives paths of length n between every pair of vertices 8. Number of paths of length r between every pair of vertices can be obtained by considering Br = A+A2+A3+ …….. Ar Questions : VIIT CSE II Graph Theory - Unit 8 27 Questions 1. Kn has _______________________edges and Km,n has _______________edges. 2. If the simple graph G has n vertices then G, the complement of G has __________edges. 3. Suppose that the graph G has 2 vertices of degree 4, 4 vertices of degree 3 and 2 vertices of degree 3 and 2vertices of degree 5. Then G has ________________ edges. 4. The number of Hamiltonian cycles in K17 =___________ 5. The largest possible number of vertices in a graph with 35 edges and all vertices of degree at least 3 is a) 23 b) at most 23 c) at least 23 d) none Slide 28: VIIT CSE II Graph Theory - Unit 8 28 6. The number of edges in k-regular graph with n-vertices is a) Kn b) Kn/2 c) n/k d) none 7. If G is a simple graph with 15 edges and G has 13 edges. How many vertices and three edges are a) 6 b) 8 c) 7 d) 5 8. Suppose that a connected planar simple graph has 20vertices each of degree3. Then the number of regions is equal to a) 10 b) 14 c) 16 d) 12 9. The number of edges in a 50-regular graph with 10 vertices have? a) 5000 b) 2500 c) 50 d) none 10. Maximum number of edges of in a an undirected simple graph with n-vertices are a) n2 b) n(n-1)/2 c) n-1 d) n(n+1)/2