第7章图和广义表 7.1图的定义和术语 7.2图的存储结构 7.3图的遍历 7.4连通内的最小生成树 7.5单源最短路径 7.6拓扑排序 7.7关键路径 7.8广义表
6
7。國的喜家术漫 V=vertex 图:记为G=(VE) E=edge 其中:V是O的顶点集合,是有穷非空集; E是的边集合,是有穷集。 问:当E(G)为空时,图G存在否? 答:还存在!但此时图G只有顶点而没有边 有向图:图G中的每条边都是有方向的; 无向图:图G中的每条边都是无方向的 完全图:图G任意两个顶点都有一条边相连接; 必若n个顶点的无向图有m(n-1)/2条边,称为无向完全图 心若n个顶点的有向图有m(m-1)条边,称为有向完全图
7 7.1 图的基本术语 n(n-1)/2 条边 无向完全图 n(n-1) 条边 有向完全图
①完全无向图有m(m1)/2条边。 证明:若是完全无向图,则顶点1必与所有其他顶点各有条连 线,即有n-1条边,顶点2有n-2条边,…,顶点n-1有1条边,顶点 n有0条边 总边数=n-1+n-2+…+1+0=(n-+0)n/2=m(-1)2 ②完全有向图有n(m1)条边。 证明:若是完全有向图,则顶点1必必与所有其他顶点各有2条 连线,即有2(n-1)条边,顶点2有2(n-2)条边,…,顶点n1有2 条边,顶点n有0条边 总边数=2(n-1+n-2+…+1+0)=2(n-1+0)n/2=m(-1)
8
例:判断下列4种图形各属什么类型? (3)④⑤⑥ (a)G1 (b)G2 (C)G3 (d)G4 无向完全图无向图(树) 有向图有向完全图 m(1)2条边 m(n-)条边 G的顶点集合为V(G1)=1{0,1,2,3} 边集合为E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}
9
例 ① G 图G中:Ⅴ(G1)={1,2,3,45,6} E(G1={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>} 例 图G2中:V(G2)={1,2,3,456,7} E(G1)={(1,2),(1,3),(2,3),(2,4),(25),(5,6),(5,7)
10