7.1.2度数与握手定理 1.顶点的度数 设无向图G=VE〉,顶点ⅵ的度数记为d(v),是指与v 相关联的边的条数 在有向图D=V,E〉中,以顶点v为始点引出的边 的条数,称为该顶点的出度记为d():以顶点v为终点引 入的边的条数,称为该顶点的入度,记为d():而顶点的出 度数与入度数之和称为该顶点的度数,简称度,记为0(), d(v)=d()+d()
7.1.2度数与握手定理 1.顶点的度数 设无向图G=〈V,E〉,顶点vi的度数记为d(vi ),是指与vi 相关联的边的条数. 在有向图D＝〈V，E〉中，以顶点v为始点引出的边 的条数，称为该顶点的出度,记为d + (v)；以顶点v为终点引 入的边的条数，称为该顶点的入度,记为d - (v)；而顶点的出 度数与入度数之和称为该顶点的度数，简称度，记为d(v)， 即 d(v)＝d + (v)+d- (v)
7.1.2度数与握手定理 握手定理 定理7.1-1(握手定理)图G=V,E)为任意无 向图,其中V=V1,v2,…,n3旧E|=mm为边数),此 ∑d(Ⅵ)=2m, 即图中结点的度数之和等于边数的两倍
7.1.2度数与握手定理 2.握手定理 定理7.1-1 (握手定理)图G=〈V,E〉为任意无 向图，其中V={v1 ,v2 ,…,vn },|E|=m(m为边数)，此 时有 ∑ d(vi )=2m, 即图中结点的度数之和等于边数的两倍. n i=1
7.1.2度数与握手定理 定理71-2设D=V,E〉为任意有向图, V={1,V2,…n},旧E=m,此时有 ∑d(W)=2m ⅰ=1 且∑d(v)=∑d(w)=m 推论任何图(无向的或有向的)中,奇度数顶点的个 数是偶数
7.1.2度数与握手定理 定理7.1-2 设D=〈V,E〉为任意有向图， V={v1 ,v2 ,…,vn }，|E|=m，此时有 ∑d(vi )=2m 且∑d+ (vi )= ∑d- (vi )= m. 推论 任何图(无向的或有向的)中，奇度数顶点的个 数是偶数. n i=1 n i=1 n i=1
7.1.3子图与补图 1.子图 定义71-4设G=V,E〉,G=〈V,E"〉是两个图若 VV,且gE,则称是G的子图,G是G的母图,记作G 若G'国且G长G(即VV或贮E),则G是G的真子图 若G′G且V=V,则称G'是G的生成子图 设∨1且∨1,以V1为顶点集,以两端点均在V1中 的全体边边集的G的子图,称为V1导出的导出子图 设E1E,且E1,以E1为边集,以E1中边关联的顶 点的全体均顶点集的G的子图,称为E导出的导出子图
7.1.3子图与补图 1.子图 定义7.1-4 设G=〈V,E〉，G′=〈V′,E′〉是两个图.若 V′ V,且E′ E,则称G′是G的子图，G是G′的母图，记作G′ G. 若G′ G且G′≠G(即V′ V或E′ E)，则称G′是G的真子图. 若G′ G且V′= V，则称G′是G的生成子图. 设V1 V且V1≠φ，以V1为顶点集，以两端点均在V1中 的全体边为边集的G的子图，称为V1导出的导出子图. 设E1 E,且E1≠φ，以E1为边集，以E1中边关联的顶 点的全体为顶点集的G的子图，称为E1导出的导出子图
7.1.3子图与补图 2.补图 定义7.1-5设G=〈V,E〉是n阶无向简 单图以V为顶点,以所有能使G成为完全图 K的添加边组成的集合为边集的图,称为G 相对于完全图Kn的补图,简称G的补图,记 作G
7.1.3子图与补图 2.补图 定义7.1-5 设G=〈V,E〉是n阶无向简 单图.以V为顶点，以所有能使G成为完全图 Kn的添加边组成的集合为边集的图，称为G 相对于完全图Kn的补图，简称G的补图，记 作 G