Chapter 12 G raphs
Chapter 12 Graphs
Main topics Definition of graphs and some terminology Three common graph representations Some algorithms
Main topics • Definition of graphs and some terminology • Three common graph representations • Some algorithms
12.1 Definition and terminologies 1. Definition of graphs Graph=(v,e) V: nonempty finite vertice set E: edge set Undirected prapl oh If the tuple denoting an edge is unordered then (v1, v2)and(v2, vl)are the same edge
12.1 Definition and terminologies 1. Definition of graphs: Graph=(V, E) V: nonempty finite vertice set E: edge set • Undirected praph: If the tuple denoting an edge is unordered, then (v1,v2) and (v2,v1) are the same edge
12.1 Definition and terminologies oh Directed grap If the tuple denoting an edge is ordered. then (VI, v2)and(v2, v I)are different edges
12.1 Definition and terminologies • Directed graph: If the tuple denoting an edge is ordered, then (v1,v2) and (v2,v1) are different edges
12.1 Definition and terminologies Example V(G1)={V12V2V32V4} v3E(G1)={(V1,V2)V1V3),(V12V 4)(V2,3)(V2,V4)(V3,V4)} V(G2)={V1V2,V3} E(G2){V1V2>2<Ⅴ2V3}
12.1 Definition and terminologies • Example: V2 V4 V3 V1 V(G1 )={V1 ,V2 ,V3 ,V4} E(G1 )={(V1 ,V2 ),(V1 ,V3 ),(V1 ,V 4 ),(V2 ,V3 ),(V2 ,V4 ),(V3 ,V4 )} V1 V2 V(G2 )={V1 ,V2,,V3} E(G2 )={,,} V3
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