12.1 Definition and terminologies We will not discuss graphs of the following types
12.1 Definition and terminologies • We will not discuss graphs of the following types
12.1 Definition and terminologies 2. Complete graph In an undirected graph with n nodes, the number of edges <=n*(n-1)/2.If=is satisfied then it is called a complete undirect graph
12.1 Definition and terminologies 2.Complete graph In an undirected graph with n nodes, the number of edges <=n*(n-1)/2. If “=“ is satisfied, then it is called a complete undirect graph. V2 V4 V3 V1
12.1 Definition and terminologies In a directed graph with n nodes, the number of edges <=n (n-1).If=is satisfied, then it is called a complete directed graph
12.1 Definition and terminologies In a directed graph with n nodes, the number of edges <=n*(n-1). If “=“ is satisfied, then it is called a complete directed graph
12.1 Definition and terminologies 3.degree d, of vertex 1, TD(v) is the number of edges incident on vertex i In a directed grap h in-degree of vertex i is the number of edges incident to 1, ID(v) out-degree of vertex i is the number of edges from the 1, OD(v)
12.1 Definition and terminologies 3.degree di of vertex i, TD(v): is the number of edges incident on vertex i. In a directed graph : • in-degree of vertex i is the number of edges incident to i, ID(v). • out-degree of vertex i is the number of edges from the i, OD(v)
12. 1 Definition and terminologies TD(V=ID(V+OD(V) v3ID(v2)=1 OD(v2 =2 TD(v2)=3 Generally if there are n vertices and e edges in a graph, the en e=(XTD(vi))/2
12.1 Definition and terminologies • TD(v)=ID(v)+OD(v) Generally,if there are n vertices and e edges in a graph, then e=(TD(vi ))/2 v1 v2 v3 ID(v2 )=1 OD(v2 )=2 TD(v2 )=3 i=1 n