Module-5 (Part 1), VTU, MCA Mathematical Foundations for Computer Application

VTU Mathematical foundation for computer application
Module-5 Graph theory notes

1. Module - 5 GRAPH THEORY Part – 1 Introduction to Graph Theory

2. D e f i n i t i on : A g r aph G i s a p a i r of f i n i t e s e t s (V, E) , wh er e V = { v 1 , v 2 , ...... , v n } i s non e m p t y set , who s e e l e m e n t s a r e ca l le d v er t ic e s (or nodes) a nd E = { e 1 , e 2 , ...... , e n } i s a s e t who s e ele m e n t s a r e c a l l e d e dg e s of G. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints. G A graph with three vertices and three edges.

3. O R D E R AND S I Z E OF A G R A P H : I n a fi n i t e g ra ph G ( V , E ) , t he nu m b e r of v ertice s d e no te d by V (G) i s ca l le d t h e o r d e r o f t he g r a ph G a nd t he nu m b e r of e d g e s d e no te d by E (G) i s cal l e d t he s i z e of t he g ra ph G. Example: Remark: The set of vertices V of a graph G may be infinite. A g ra ph G ( V , E ) i s c a ll e d a fi n i t e g r aph i f i t h a s f i n it e nu m b e r o f v erti c e s a nd e d g es . O t h er w i s e i t i s c a l l e d a n i n fi n it e g r ap h .

4. DIRECTED AND UNDIRECTED GRAPHS : Let G ( V , E ) be a graph. If the elements of E are ordered pair of vertices of G, then the Graph G is called a directed graph . Each directed edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair ( u , v ) is said to start at u and end at v . If the elements of E are unordered pair of vertices of G, then the Graph G is called an undirected graph .

5. BASIC TERMINOLOGIES: Two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G if u and v are endpoints of an edge e of G. Such an edge e is called incident with the vertices u and v and e is said to connect u and v . In other words, if ‘ v ’ i s a n e nd v e r te x of a n e d g e ‘ e ’ of G, t h e n e i s an i n ci d e n t t o t h e v e rt e x v . T wo v e r ti c e s i n a g ra p h a r e sai d t o b e ad j a ce n t , i f t h e y ar e t he e nd v er t i c e s o f t h e s a m e e d g e . T wo p ar a l l e l e d g e s a r e s a i d t o be ad j a ce nt e dg e s , i f t h e y i n ci d e nt on a c o m m on v er t e x.

6. The set of all neighbors of a vertex v of G = (V, E), denoted by N ( v ), is called the neighborhood of v . If A is a subset of V, we denote by N (A) the set of all vertices in G that are adjacent to at least one vertex in A. In a directed graph G, when ( u , v ) is an edge, 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. I n a g ra ph G ( V , E), t h e e d g e s h a v i ng t he sa m e p a i r o f e nd v e r t i ce s ar e c a ll e d p a r a l le l e dg e s or m u l ti p l e e d g e s .

7. I n a g ra ph G ( V , E), t he e d g e s who s e e n d v er t ic e s a r e i d e n t i ca l a r e c a l l e d s e l f l oo p . A g ra ph w it h n o s e l f l oo p s a nd no p ar a l l e l e d g e s i s c a l l e d S i m p l e g r ap h . A g ra ph wh ic h h a s p ar a l l e l e d g e s a nd no s e l f l oo p s i s c al l e d M u l t i g r ap h .

8. A g ra ph wh ic h h a s b o t h p a r al l e l e d g e s a nd s e l f l oops i s ca l le d P se udo g r ap h . A g ra ph c on t ai n i ng no e d ge s i s ca l le d a n u l l g r ap h . A fi n it e g r a ph w i t h o n e v er t e x a nd n o e d g e s i s c a l le d a T ri v i al g r aph.

9. A g ra ph i n wh i c h e ac h v e rt e x i s as s i g n e d a u n i q u e l a b e l i s c a l l e d Lab e l g r aph. A g ra ph G i s i n wh i c h w e i g h t s a r e as s i g n e d t o e v er y e d g e i s c a ll e d a w e i ghted graph. A graph with both directed and undirected edges is called a mixed graph .

10. 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 ). I f t he d e g re e o f v ert e x v i s z er o, t h e n v i s c a l le d a n i s o l a te d v er t e x . I f t he d e g re e o f v ert e x v i s on e , t h e n v i s ca l le d p e nd e nt v e r te x . A v erte x i n a g ra ph G i s sa i d t o be e v e n or odd v e r te x acc o r d i ng a s i t s d e g r e e i s a n e v e n or odd nu m b er .

11. Example: 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. IN-DEGREE AND OUT-DEGREE : In a directed graph, 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. (Note that a loop at a vertex contributes 1 to both the in-degree and the out-degree of this vertex.) Example: The in-degrees in G are deg - ( a ) = 2, deg - ( b ) = 2, deg - ( c ) = 3, deg - ( d ) = 2, deg - ( e ) = 3 and deg - ( f ) = 0. The out-degrees in G are deg + ( a ) = 4, deg + ( b ) = 1, deg + ( c ) = 2, deg + ( d ) = 2, deg + ( e ) = 3 and deg + ( f ) = 0.

13. REGULAR GRAPHS : A g ra ph G i s s ai d t o b e a R e g u l ar g r a p h , i f e v er y v erte x of G h a s t he s a m e d e g ree . A g ra ph G i s s a i d t o be a k - R e gu l a r g r ap h , i f e v er y v erte x o f G h a s d e g re e k . The size of the k - R e gu l a r g r ap h is Example:

14. Remark : 3 - Re g u la r g ra phs a r e c a l le d c ub i c g r ap h s . Cub i c g ra ph wh ic h c on t ai n 1 v er t ic e s a nd 15 e d g e s i s ca l le d t he P et e rse n g r aph

15. COMPLETE GRAPHS : A simple graph in which there exists an edge between every pair of distinct vertices is called a complete graph. A complete graph on n vertices , denoted by K n . Example : The graphs K n , for n = 1, 2, 3, 4, 5, 6, are shown below:

16. The graph K 5 is known as Kuratowski’s first graph . A simple graph for which there is at least one pair of distinct vertex not connected by an edge is called noncomplete . BIPARTITE GRAPHS : 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 . i . e ., no e d g e i n G c on n e c t s e i t h e r t wo v er t ice s i n V 1 o r t wo v e r t i ce s i n V 2 .

17. Example : The following graphs are bipartite graphs

18. COMPLETE BIPARTITE GRAPHS : A bipartite graph G = ( V 1 , V 2 ; E) is called a complete bipartite graph if there is an edge between every vertex in V 1 and every vertex in V 2 . It is denoted by K m, n Example : The following are the complete bipartite graphs The graph K 3, 3 is known as Kuratowski’s second graph .

19. THE HANDSHAKING THEOREM : T he s um of d e g ree s of a l l t he v e r t i ce s i n a g ra ph i s a n e v e n nu m b er . Th i s nu m b e r i s e qu a l t o t w i c e t he nu m b e r o f e d g e s i n t he g ra ph. T h a t i s , f o r a ny undirected graph G = ( V , E ), P r oo f : Every edge of G incident with two vertices.  Every edge of G contributes 2 to the sum of degrees of vertices of G i.e., Every edge of G contributes 2 to the

20. Note: This property is called hand shaking property because every people shake hands, then total number of h a n ds s h a k e n m u s t be e v e n. T h i s p r op e r t y i s al s o k nown a s t he f i r s t t h e o re m of g ra ph t h e o r y .

21. Theorem: An undirected graph has an even number of vertices of odd degree. (By using hand shaking theorem)

22. Determine for the graph in the following cases: G has 9 edges and all the vertices of degree 3 G has 10 edges with two vertices of degree 4 and the others of degree 3. G is a cubic graph with 9 edges. G is a regular graph with 15 edges. 16 edges and all vertices of degree 4. 21 edges, 3 vertices of degree 4 and other vertices of degree 3. 12 edges, 6 vertices of degree 3 and other vertices of degree less than 3.  

23. Therefore,   By data, To find ?   By hand shaking theorem, we have G has 9 edges and all the vertices of degree 3

24. Therefore,   By data, To find ?   By hand shaking theorem, we have b) G has 10 edges with two vertices of degree 4 and the others of degree 3.

25. Therefore,   By data, To find ?   By hand shaking theorem, we have c) G is a cubic graph with 9 edges.

26. Possible values of Possible values of    By data, To find ?   By hand shaking theorem, we have d) G is a regular graph with 15 edges .

27. Therefore,   By data, To find ?   By hand shaking theorem, we have e) 16 edges and all vertices of degree 4.

28. Therefore,   By data, To find ?   By hand shaking theorem, we have f) 21 edges, 3 vertices of degree 4 and other vertices of degree 3.

29. By data, To find ?   By hand shaking theorem, we have g) 12 edges, 6 vertices of degree 3 and other vertices of degree less than 3. Therefore, is at least 9.  

30. Show that there is no graph with 28 edges and 12 vertices in the following cases: The degree of a vertex is either 3 or 4 The degree of a vertex is either 3 or 6 (a) By data, By hand shaking property, we have , which is impossible. Therefore, there is no such graph.  

31. Show that there is no graph with 28 edges and 12 vertices in the following cases: The degree of a vertex is either 3 or 4 The degree of a vertex is either 3 or 6 (b) By data, By hand shaking property, we have , which is impossible. Therefore, there is no such graph.  

32. Show that in a complete graph of n vertices Degree of every vertex is The total number of edges is (a) In a complete graph of n vertices, each edge is incident with n - 1 edges. Therefore, degree of every vertex is . By hand shaking property, we have . .