Graph terminologies & special type graphs

This is the topic of Discrete Structure.

1. DISCRETE STRUCTURE

2. GRAPH TERMINOLOGIES & SPECIAL TYPE GRAPHS

3. TYPES OF GRAPHS Undirected Graphs Directed Graphs Special Simple Graphs Special Simple Graphs

4. UNDIRECTED GRAPHS The graph in which u and v (vertices ) are endpoints of an edge of graph G is called an undirected graph G. U V LOOP

5. DEGREE The number of edges for which vertex is an endpoint . The degree of a vertex v is denoted by deg(v).

6. DEGREE If deg( v) = 0, v is called isolated . If deg( v) = 1, v is called pendant.

7. THE HANDSHAKING THEOREM Let G = (V, E) be an undirected graph with E edges. Then 2|E| =  v  V deg( v ) Note that This applies if even multiple edges and loops are present.

8. EXAMPLE How many edges are there in a graph with 10 vertices each of degree 5?  v  V deg( v ) = 6·10 = 60 2 E=  v  V deg( v ) = 60 E=30

9. EXAMPLE How many edges are there in a graph with 9 vertices each of degree 5?  v  V deg( v ) =5 · 9 = 45 2E =  v  V deg( v ) = 45 2E =45 E=22.5 Which is not possible.

10. DIRCTED GRAPHS When (u, v) is an edge of the graph G with directed edges. 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 .

11. DEGREE The in degree of a vertex v , denoted deg − (v) is the number of edges which terminate at v. Similarly, the out degree of v, denoted deg + (v), is the number of edges which initiate at v.  vV deg － (v) =  vV deg ＋ (v)= |E|

12. EXAMPLE Find the in-degree and out-degree of each vertex in the graph G with directed edges. The Directed Graph G . 12

13. EXAMPLE The in-degrees in G are deg − (a) = 2 deg − (b) = 2 deg − (c) = 3 deg − (d) = 2 deg − (e) = 3 deg − (f ) = 0 The out-degrees in G are deg + (a) = 4 deg + (b) = 1 deg + (c) = 2 deg + (d) = 2 deg + (e) = 3 deg + (f ) = 0

14. SOME SPECIAL SIMPLE GRAPHS 14 There are several classes of simple graphs. Complete graphs Cycles Wheels n-Cubes Bipartite Graphs New Graphs from Old

15. COMPLETE GRAPHS 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 1≦ n ≦6.

16. COMPLETE GRAPHS K5 & K6 is important because it is the simplest non-planar graph. It cannot be drawn in a plane with nonintersecting edges.

17. CYCLE 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. The Cycles C 3 , C 4 , C 5 , and C 6 .

18. WHEEL 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 of the n vertices in C n , by new edges. The Wheels W 3 , W 4 , W 5 , and W 6 . 18

19. N-CUBES Q n is the graph with 2n vertices representing bit strings of length n. An edge exists between two vertices that differ by one bit position. 19

20. EXAMPLE A common way to connect processors in parallel machines. Intel Hypercube.

21. EXAMPLE The n-cube Q n for n = 1, 2, and 3. 21

22. BIPARTITE GRAPH A simple graph G is called bipartite if its vertex set V and 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 . When this condition holds, we call the pair (V 1 , V 2 ) a bipartition of the vertex set V .

23. BIPARTITE GRAPH A Star network is a K (1,n) bipartite graph. V1(n=ODD) V2(n=EVEN)

24. BIPARTITE GRAPH V1={v1,v3,v5} ; V1={v2,v4,v6} This is the graph of Hexagonal.

25. BIPARTITE GRAPH

26. NEW GRAPHS FROM OLD A sub-graph of a graph G = ( V , E ) is a graph H =( W , F ), where W  V and F  E . A sub-graph H of G is a proper sub-graph of G if H  G . 26

27. NEW GRAPHS FROM OLD The graph G shown below is a sub-graph of K 5 . A Sub-graph of K 5 . 27

28. NEW GRAPHS FROM OLD The union of two simple graphs G 1 = (V 1 , E 1 ) & G 2 = (V 2 , E 2 ) is the simple graph with vertex set V 1  V 2 and edge set E 1  E 2 . The union of G 1 and G 2 is denoted by G 1  G 2 . 28

29. NEW GRAPHS FROM OLD The Simple Graphs G 1 and G 2 Their Union G 1 ∪ G 2 . 29

30. APPLICATION OF SPYCIAL TYPES OF GRAPHS Suppose that there are m employees in a group and j different jobs that need to be done where m  j . Each employee is trained to do one or more of these j jobs. We can use a graph to model employee capabilities. We represent each employee by a vertex and each job by a vertex. For each employee, we include an edge from the vertex representing that employee to the vertices representing all jobs that the employee has been trained to do. 30

31. APPLICATION OF SPYCIAL TYPES OF GRAPHS Note that the vertex set of this graph can be partitioned into two disjoint sets, the set of vertices representing employees and the set of vertices representing jobs, and each edge connects a vertex representing an employee to a vertex representing a job. Consequently, this graph is bipartite.

32. APPLICATION OF SPYCIAL TYPES OF GRAPHS To complete the project, we must assign jobs to the employees so that every job has an employee assigned to it and no employee is assigned more than one job. Modeling the Jobs for Which Employees Have Been Trained. 32

33. END

34. THANK YOU