1. Graph and Graph Terminologiesimp.pptx

Graphs

1. Introduction to Graphs There are 5 main categories of graphs: Simple graph Multigraph Pseudograph Directed graph Directed multigraph 1 Prof. N.G.Dharashive

2. Definition 1 A simple graph G = (V, E) consists of V, a nonempty set of vertices (or nodes) ; and E, a set of edges . Example: Telephone lines connecting computers in different cities. Each edge has either one or two vertices associated with it, called its endpoints. 2 Introduction to Graphs Prof. N.G.Dharashive

3. Introduction to Graphs Definition 2: Multigraph A graph that having multiple edges connecting the same pair of vertices is called multigraph . Example: A comp. network with Multiple Links between Data centers When there are m different edges associated to the same unordered pair of vertices { u,v }, we say that { u,v } is an edge of multiplicity m . 3 Prof. N.G.Dharashive

4. Introduction to Graphs In a graph some edges connect a vertex to itself. Such edges are called loops . Definition 3: Pseudograph A graph that may include loops, and possibly multiple edges connecting same pair of vertices, is called pseudograph . 4 Prof. N.G.Dharashive

5. Introduction to Graphs So far introduced graphs are undirected graphs. Definition 4: Directed Graph / Digraph A directed graph (V,E) consists of a nonempty set of vertices V and a set of directed edges (or arcs) E. The directed edge associated with the ordered pair of vertices (u , v) is said to start at u and end at v . 5 Prof. N.G.Dharashive

6. Introduction to Graphs When a directed graph has no loops and has no multiple directed edges, it is called a simple directed graph . Definition 5: Directed Multigraph A directed graph that may have multiple directed edges from a vertex to a second vertex (possibly the same) is called as directed multigraph . When there are m directed edges, each associated to an ordered pair of vertices ( u , v ), we say that ( u , v ) is an edge of multiplicity m . 6 Prof. N.G.Dharashive

7. Introduction to Graphs 7 Example of directed graph Prof. N.G.Dharashive

8. Graph Terminology Definition : Adjacent Two vertices u and v in an undirected graph G are called adjacent (or neighbors ) in G if {u , v} is an edge of G . The edge e is also said to connect u and v. The vertices u and v are called endpoints of the edge { u,v }. Definition : Degree of a Vertex The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex v is denoted by deg(v). 8 Prof. N.G.Dharashive

9. Example: What are the degrees of the vertices in the graphs G & H? Solution: 9 Prof. N.G.Dharashive

10. Graph Terminology Definition : Isolated Vertex A vertex of degree zero is called isolated vertex. An isolated vertex is not adjacent to any vertex. Vertex g in graph G in last slide is isolated. Definition : Pendant Vertex A vertex is pendant if and only if it has degree one. A pendant vertex is adjacent to exactly one other vertex. Vertex d in graph G in last slide is pendant. 10 Prof. N.G.Dharashive

11. Graph Terminology Theorem 1: The handshaking theorem Let G = (V,E) be an undirected graph with e edges. Then (Note that this applies even if multiple edges & loops are present.) 11 Prof. N.G.Dharashive

12. Graph Terminology Example: How many edges are there in a graph with ten vertices each of degree 6 ? Solution: Since the sum of the degrees of the vertices is 6*10 = 60  2e = 60. Therefore, e = 30 Example: What are the degrees of the vertices in the graphs G and H ? Solution: In G , deg(a) = 2 , deg(b) = deg(c) = deg(f ) = 4, deg(d ) = 1, deg(e) = 3, and deg(g) = 0. In H , deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, and deg(d ) = 5. 12 Prof. N.G.Dharashive

13. Example: A graph has five vertices. Can you draw the graph if the degree of the vertices are: (a) 2, 3, 1, 1, and 2? (b) 2, 3, 3, 4, and 4? Graph Terminology Solution: (a) No , because 2 + 3 + 1 + 1 + 2 = 9, is an odd number . (b) Yes , because 2 + 3 + 3 + 4 + 4 = 16, is an even number .

14. Graph Terminology Theorem 2: An undirected graph has an even number of vertices of odd degree. When (u , v) is an edge of the graph G with directed edges, u is said to be adjacent to v and v is said to be adjacent from u. The vertex u is called the initial vertex of (u , v), and v is called the terminal or end vertex of (u , v). The initial vertex and terminal vertex of a loop are the same. In a graph with directed edges the in-degree of a vertex v , denoted by deg - (v) , is the number of edges with v as their terminal vertex . The out-degree of v , denoted by deg + (v) , is the number of edges with v as their initial vertex . The initial vertex and terminal vertex of a loop are the same. (Note that a loop at a vertex contributes 1 to both the in-degree and the out-degree of this vertex.) 14 Prof. N.G.Dharashive

15. Graph Terminology Example: Find the in-degree and the out-degree of each vertex in the graph G Solution: The in-degree of G are: deg - (a) = 2, deg - (b) = 2, deg - (c) = 3, deg - (d) = 2, deg - (e) = 3, and deg - (f) = 0. The out-degree of G are: deg + (a) = 4, deg + (b) = 1, deg + (c) = 2, deg + (d) = 2, deg + (e) = 3, and deg + (f) = 0 15 Prof. N.G.Dharashive

16. Graph Terminology Theorem 3: Let G = (V,E) be a graph with directed edges. Then 16 Prof. N.G.Dharashive

17. Some Special Simple Graphs Complete Graph The complete graph on n vertices, denoted by K n , is the simple graph that contains exactly one edge between each pair of distinct vertices. The graphs K n , for n=1 , 2, 3 , 4, 5 , 6, are displayed in Figure 17 Prof. N.G.Dharashive

18. Some Special Simple Graphs Cycles The cycle C n , n ≥ 3, consists of n vertices v 1 , v 2 , . . . , v n and edges { v 1 , v 2 }, { v 2 , v 3 } , . . . , { v n-1 , v n }, and { v n , v 1 }. The cycles C 3 , C 4 , C 5 , and C 6 are displayed below 18 Prof. N.G.Dharashive

19. Some Special Simple Graphs Wheels We obtain the wheel W n when we add an additional vertex to the cycle C n , for n ≥ 3 , and connect this new vertex to each o f the n vertices in C n , by new edges. The wheels W 3 , W 4 , W 5 , and W 6 are displayed below 19 Prof. N.G.Dharashive

20. Some Special Simple Graphs Bipartite Graph A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint sets V 1 and V 2 such that every edge in the graph connects a vertex in V 1 and a vertex in V 2 In Bipartite Graph no edge in G connects either two vertices in V 1 or two vertices in V 2 . When above condition holds, we call the pair (V 1 , V 2 ) a bipartition of the vertex set V of G. 20 In fig. vertex set can be partitioned into the two sets V 1 = { v 1 , v 3 , v 5 } and V 2 = { v 2 , v 4 , v 6 }, and every edge of G connects a vertex in V 1 and a vertex in V 2 . Prof. N.G.Dharashive

21. Some Special Simple Graphs Example: Whether K 3 is a bipartite? Solution: K 3 is not bipartite. To verify this, note that if we divide the vertex set of K 3 into two disjoint sets, one of the two sets must contain two vertices. If the graph were bipartite, these two vertices could not be connected by an edge, but in K 3 each vertex is connected to every other vertex by an edge. Example: Are the graphs G and H in Figure below bipartite? hint on next slide 21 Prof. N.G.Dharashive

22. Some Special Simple Graphs Solution Hint: Use following theorem Theorem: A simple graph is bipartite if and only if it is possible to assign one of two different colors to each vertex of the graph so that no two adjacent vertices are assigned the same color. Solution to the last problem: Graph G is bipartite because its vertex set is the union of two disjoint sets, {a, b, d} and {c, e, j, g}, and each edge connects a vertex in one of these subsets to a vertex in the other subset. Graph H is not bipartite because its vertex set cannot be partitioned into two subsets so that edges do not connect two vertices from the same subset. 22 Prof. N.G.Dharashive

23. Some Special Simple Graphs Complete Bipartite Graph The complete bipartite graph K m,n is the complete graph that has its vertex set partitioned into two subsets of m and n vertices, respectively. The complete bipartite graphs K 2,3 , K 3,3 , K 3,5 , and K 2,6 are; 23 Prof. N.G.Dharashive

24. Subgraphs Definition A subgraph of a graph G = (V, E) is a graph H = (W, F), where A subgraph H of G is a proper subgraph of G if H ≠ G. Example: 24 Prof. N.G.Dharashive

25. Union of graphs Definition The union of two simple graphs G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) is the simple graph with vertex set V 1 U V 2 and edge set E 1 U E 2 . The union of G 1 and G 2 is denoted by G 1 U G 2 . Example: 25 Prof. N.G.Dharashive

26. Union of graphs In Exercises 50-52 find the union of the given pair of simple graphs. (Assume edges with the same endpoints are the same.) Solution: 26 Prof. N.G.Dharashive

27. Intersection graphs Definition The intersection graph of a collection of sets A 1 , A 2 , • • • , A n is the graph that has a vertex for each of these sets and has an edge connecting the vertices representing two sets if these sets have a nonempty intersection. Example: Construct the intersection graph of these collections of sets. 27 Prof. N.G.Dharashive

28. 28 Prof. N.G.Dharashive

29. Solution to problem 5: No, Because (as per Theorem 1.1) the sum of the degrees of the vertices cannot be odd. 29 Prof. N.G.Dharashive

30. 30 Prof. N.G.Dharashive

31. Solution: 31 Prof. N.G.Dharashive

32. In Exercises 21-25 determine whether the graph is bipartite. Determining whether it is possible to assign either red or blue to each vertex so that no two adjacent vertices are assigned the same color. Solution: ( Hint: You may find it useful to apply some theorem to determine color assignment) 32 Prof. N.G.Dharashive

33. Solution: ( Hint: You may find it useful to apply 2-color theorem to determine color assignment) 33 Complete Bipartite K 1,4 { e } and { a,b,c,d } Not Bipartite Not Bipartite Complete Bipartite K 2,3 with { a,c } and { b,d,e } Complete Bipartite K 2,4 with { c,f } and { a,b,d,e } Prof. N.G.Dharashive

34. Problem: For which values of n are these graphs bipartite ? a) K n b) C n c) W n Solution: a) By the definition of bipartite, K 1 does not have enough vertices to be bipartite, so K 1 is not bipartite Clearly K 2 is bipartite . There is a triangle in K n for n>2 , so those complete graphs are not bipartite . b) First we need n ≥ 3 for C n to be defined. If n is even , then C n is bipartite , since we can take one part to be every other vertex. If n is odd , then C n is not bipartite . c) Every wheel contains triangles, so no W n is bipartite . 34 Prof. N.G.Dharashive

35. Problem: How many vertices and how many edges do these graphs have? a) K n b) C n c) W n d) K m,n Solution: a) n vertices, n (n - 1 ) / 2 edges b) n vertices, n edges c) n + 1 vertices, 2 n edges d) m + n vertices, mn edges 35 Prof. N.G.Dharashive

36. Some Special Simple Graphs Regular Graph A simple graph is called regular if every vertex of this graph has the same degree . A regular graph is called n -regular if every vertex in this graph has degree n . Problem: For which values of n are these graphs regular? a) K n b) C n c) W n Solution: a) For all n ≥ 1 b) For all n ≥ 3 c) For n = 3 Problem: For which values of m and n is K m,n regular? Solution: Since the vertices in one part have degree m , and vertices in the other part have degree n , we conclude that K m,n is regular if and only if m = n . 36 Prof. N.G.Dharashive

37. Some Special Simple Graphs Complementary Graph The complementary graph of a simple graph G has the same vertices as G . Two vertices are adjacent in if and only if they are not adjacent in G . Problem: Describe each of these graphs. Solution: a) The graph with n vertices and no edges . b) The disjoint union of K m and K n graphs. i.e. for e.g. Lets G be K 2,3 Then will be 37 Prof. N.G.Dharashive