(Undigraph) ——无向图 G是由集合 V(G) 和 E(G) 组成?其中: V(G) 是顶点的非空有限集? E(G) 是边的有限集合,边是顶点的无序对,记为( v,w )或( w,v) ,并且( v,w)=(w,v) 图的定义和术语其它定义例245136 G1 图 G1 中: V(G1)={1,2,3,4,5,6} E(G1)={<1,2>, <2,1>, <2,3>, <2,4>, <3,5>, <5,6>, <6,3>} 例 157324 G2 6 图 G2 中: V(G2)={1,2,3,4,5,6,7} E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)} 图的定义和术语?pleted Graph —— n个顶点的有向图最大边数是 n(n-1) ?无向完备图—— n个顶点的无向图最大边数是 n(n-1)/2 ; ?稀疏图 Sparse Graph ——若边或弧的个数 e<nlogn ,则称作~,否则称作稠密图 Dense Graph ?权 Weight ——与图的边或弧相关的数叫~ ?work ——带权的图叫~,有向网,无向网?子图 Subgraph ——如果图 G(V,E) 和图 G’(V’,E’),满足: V’? V E ’? E 则称 G’为G的子图?邻接点 Adjacent ——顶点 v 和顶点 w 之间存在一条边,则称 v 和 w 互为~;边(v,w) 和顶点 v 和 w 相关联?顶点的度 Degree ?无向图中,顶点的度为与每个顶点相连的边数?有向图中,顶点的度分成入度与出度?入度 InDegree :以该顶点为头的弧的数目?出度 OutDegree :以该顶点为尾的弧的数目; 图的定义和术语其它定义
全文预览
