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<V2,V1><Ⅴ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 )={<V1 ,V2>,<V2 ,V1>,<V2 ,V3>} V3