n阶图,零图,平凡图,空图。 若G=<V,E>,则VG)=V,E(G=E 静若D=以V,E>,则V(D)=V,E()=E 阶图( (order-n graph):(G)=n 有限图( inite graph): V(G)|<∞ 秦零图(u‖! graph):E=,N 鲁平凡图( trival graph):1阶零图,N 空图( empty graph):V=E=, 《集合论与图论》第14讲
《集合论与图论》第14讲 6 n阶图,零图,平凡图,空图 若G=<V,E>, 则V(G)=V, E(G)=E 若D=<V,E>, 则V(D)=V, E(D)=E n阶图(order-n graph): |V(G)|=n 有限图(finite graph): |V(G)|<∞ 零图(null graph): E=∅, Nn 平凡图(trival graph): 1阶零图, N1 空图(empty graph): V=E=∅, ∅
标定图,非标定图,基图 壽标定图( abeled graph):顶点或边带标记 非标定图 unlabeled graph:顶点或边不 带标记 基图(底图):有向图去掉边的方向后得到 的无向图 a d 《集合论与图论》第14讲
《集合论与图论》第14讲 7 标定图,非标定图,基图 标定图(labeled graph): 顶点或边带标记 非标定图(unlabeled graph): 顶点或边不 带标记 基图(底图): 有向图去掉边的方向后得到 的无向图 a b c d
相邻( (adjacent),关联( incident) 相邻(邻接)( adjacent:点与点,边与边 豢邻接到,邻接于:u邻接到ν,V邻接于u以 关联( (incident):点与边· 关联次数: 秦环(0p):只与一个顶点关联的边 孤立点( solated vertex):· 平行边( parallel edge) 《集合论与图论》第14讲
《集合论与图论》第14讲 8 相邻(adjacent),关联(incident) 相邻(邻接)(adjacent): 点与点,边与边 邻接到,邻接于: u邻接到v, v邻接于u 关联(incident):点与边 关联次数: 环(loop):只与一个顶点关联的边 孤立点(isolated vertex): 平行边(parallel edge): ? 1 1 +1 -1 2 u v
邻域( neighborhood 邻域:N()={uueV(G)(u,)∈E(G)Auzy 闭( closed)邻域:N(v)=N(y{vy 关联集:I()={ee与v关联} 后继:ID()= uuEVD<v,U>E(D)Au=1 前驱:D()={ uUEV(D)uv>∈E(D)八u 邻域:Ne()=ID)() 闭邻域:ND(v)=ND(v){v 《集合论与图论》第14讲
《集合论与图论》第14讲 9 邻域(neighborhood) 邻域: NG(v)={u|u∈V(G)∧(u,v)∈E(G)∧u≠v} 闭(closed)邻域: 关联集: IG(v) = { e | e与v关联 } 后继:ΓD+(v)={u|u∈V(D)∧<v,u>∈E(D)∧u≠v} 前驱:ΓD-(v)={u|u∈V(D)∧<u,v>∈E(D)∧u≠v} 邻域: NG(v)=ΓD+(v)∪ΓD-(v) 闭邻域: N (v) N (v) {v} G = G ∪ N (v) N (v) {v} D = D ∪
顶点的度数( legree/valence) 度d):与v关联的边的次数之和 出度d+(0):与v关联的出边的次数之和 鲁入度d(0):与v关联的入边的次数之和 度dD)=db)+d() (d,d) 《集合论与图论》第14讲
《集合论与图论》第14讲 10 顶点的度数(degree/valence) 度dG(v): 与v关联的边的次数之和 出度dD+(v): 与v关联的出边的次数之和 入度dD-(v): 与v关联的入边的次数之和 度dD(v) = dD+(v) + dD-(v) 0 3 3 4 0,0 1,2 (d+,d-) 2,1 2,2