(20120901)第十四章图的基本概念.ppt

,漳州师范学院计算机科学与工程系,第十四章 图的基本概念,第十四章 图的基本概念,图 通路与回路 图的连通性 图的矩阵表示 图的运算 知 识 点：图的基本概念、路与回路、连通度、图的矩阵 表示、图的运算 。 教学要求：深刻理解和掌握图的有关概念和表示 。 教学重点：图的基本概念。 学时: 6,14.1 图,图是用于描述现实世界中离散客体之间关系的有力工具 。图中点的位置和线的长短形状都是无关紧要的, 重要的是两点之间是否有连线。,无向图,有向图,14.1 图,设A,B为任意的两个集合 A与B的笛卡尔积: AB= |aA , bB A与B的无序集: A&B= a,b |aA , bB 无序对a,b记为(a,b), 有(a,b)=(b,a) =当且仅当 a=b A&B= B&A , AB一般不等于BA,14.1 图,例: 设 A=1,2,3,B=x,y , 则 AB=, A & B= 1,x,1,y, 2,x,2,y,3,x,3,y 例: 设 A=1,2,B=1,2 , 则 AB= , A & B= 1,1 , 1,2 , 2,2 或 = (1,1) , (1,2) , (2,2) ,14.1 图,定义14.1 一个无向图G是一个有序的二元组 V是一个非空有穷集,V ,称为顶点集,其元素称为顶点或结点 E是无序积V&V的有穷多重子集,称为边集,其元素称为无向边或边 例 图G如右图所示,其中 V=v1,v2,v3,v4,v5, E= (v1,v3),(v1,v4),(v2,v4),(v2,v5),(v3,v5) 或 E= e1 , e2 , e3 , e4 , e5 边 e1 可记作 e1= (v1,v4),14.1 图,定义14.2 一个有向图D是一个有序的二元组 V是一个非空有穷集,V ,称为顶点集,其元素称为顶点或结点 E是笛卡积VV的有穷多重子集,称为边集,其元素称为有向边或边 例 图G如右图所示,其中 V=v1,v2,v3,v4,v5, E= e1 , e2 , e3 , e4 , e5 或 E= , 边e1可记作 e1=,14.1 图,有关图的一些概念和规定 无向图和有向图统称为图,通常用G表示无向图,D表示有向图,有时也用G泛指图. V(G), E(G)分别表示G的顶点集和边集. |V(G)|,|E(G)|分别是G的顶点数和边数 顶点数称作图的阶,n个顶点的图称为n阶图,14.1 图,有关图的一些概念和规定(续) 一条边也没的图称为零图. n阶零图记作Nn 1阶零图N1称为平凡图.平凡图只有一个顶点,没有边 规定顶点集为空集的图为空图,并将空图记为 给每个顶点和每一条边指定一个符号 则称这样的图为标定图,否则称为非标定图,14.1 图,有关图的一些概念和规定(续) 将有向图的各条有向边改成无向边后 所得到的无向图称为这个图的基图,14.1 图,有关图的一些概念和规定(续) 设G=为无向图, ek= (vi,vj)E 称vi,vj为ek的端点, ek与vi ,vj关联, 若vivj,则称ek与vi ,vj的关联次数为1 若vi=vj, 则称ek与vi ,vj的关联次数为2 并ek称为环 若两个顶点与之间有一条边连接,则称这两个顶点相邻 若两条边至少有一个公共端点,则称这两条边相邻,e2,e3,14.1 图,有关图的一些概念和规定(续) 设D=为无向图, ek= E 称vi,vj为ek的端点, ek与vi ,vj关联,vi为ek与的始点, vj为ek与的始点。 若vi=vj, 则称ek为D中的环 若两个顶点与之间有一条边连接,则称这两个顶点相邻 若两条边中一条边的终点是另一条边的始点,则称这两条边相邻 图(无向的或有向的)中没有 边关联的顶点,称为孤立点,e2,e3,14.1 图,有关图的一些概念和规定(续) 设无向图G=,vV, 称 NG(v)= u| uV(u,v)Euv 为v的邻域 称 NG(v)= NG(v) v 为 v 的闭邻域 称 IG(v)= )= e| eEe与v相关联 为v的关联集 设有向图D=,vV 称D+ (v)=u|uVEuv为v的后继元集 称 D- (v)= u| uVEuv 为v的先驱元集 称 ND(v)=D+(v)D-(v)为v的邻域 称 ND(v)=ND(v)v为v的闭邻域,14.1 图,定义14.3 在无向图中,如果关联一对顶点的无向边多于1条, 则称这些边为平行边,平行边的条数称为重数. 在有向图中,如果关联一对顶点的有向边多于1条, 并且这些边的始点与终点相同,则称这些边为平行边. 含有平行边的图称为多重图, 既不含平行边也不含环的图称为简单图,多重图,简单图,14.1 图,定义14.4 设G=为无向图 vV,称v作为边的端点的次数之和为v的度数,记作dG(v) 设D=为有向图 vV,称v作为边的始点的次数之和为v的出度,记为dD-(v) vV,称v作为边的终点的次数之和为v的入度,记为dD+(v) 称 dD-(v)+dD+(v) 为v的度数,简记作d(v),14.1 图,图G的最大度 : (G)=max d(v)| vV (G) 图G的最小度 : (G)=min d(v)| vV (G) 类似定义有向图的最大出度、最小出度、最大入度、最小入度,14.1 图,定理14.1 在任何无向图中,所有顶点的度数之和 等于边数的2倍 证 图中每条边均有两个端点, 所以在计算各顶点的度数之和时 每条边均提供了2度. m 条边共提供2m度 欧拉于1736年给出握手定理,是图的基本定理,14.1 图,定理14.2 在任何有向图中,所有顶点的度数之和 等于边数的2倍。所有顶点的入度之和 等于所有顶点的出度之和,都等于边数 推论 在任何图中,奇度顶点的个数是偶数,14.1 图,设G=为一个n阶无向图,V=v1,v2,vn, 称d(v1),d(v2),d(vn)为G的度数(序)列 对于顶点标定的无向,它的度数列是唯一的 对于给定的非负整数列 d=(d1,d2,dn),若存在以V=v1,v2,vn为顶点集的n阶无向图G,使得 d(vi)=di 则称d是可图化的 特别地若所得到的图是简单图,则称d是可简单化的,14.1 图,例 画出度序列为 4,5,2,3,2 的图,G1,G2,14.1 图,定理14.3 非负整数列d=(d1,d2,dn)是可图化的 当且仅当 为偶数 定理14.4 设G为任意n阶无向简单图,则(G)n-1 例14.2 判断下列各非负整数列哪些是可图化的?哪些是可简单化的? (1) (5,5,4,4,2,1) (2) (5,4,3,2,2) (3) (3,3,3,1) (4) (d1,d2,dn), d1d2dn1且 为偶数 (5) (4,4,3,3,2,2),14.1 图,定义14.5 设G1=,G2=为两个无向图 若存在双射函数 f: V1V2 使得, vi,vjV1,(vi,vj)E1 当且仅当 f(vi),f(vj) )E2 并且 (vi,vj) 和 ( f(vi),f(vj) ) 的重数相同 则称G1和G2同构,记作 G1 G2 对有向图可类似定义,14.1 图,14.1 图,图之间的同构关系” ”构成全体图集合上的二元关系 关系是等价关系,具有自反性、对称性、传递性 在图的等价关系的每个等价类中的图在同构意义下都可看成一个图 至今仍未找到判断两个图是否同构的便于检查的充分必要条件 阶数相同、边数相同、度数列相同是两个图同构的必要条件,14.1 图,彼德森图,哈拉里图H10,3,14.1 图,定义14.6 设G是n阶无向简单图,若G中每个顶点均与其余的n-1个顶点相邻,则称G为n阶无向完全图,简称n阶完全图,记作Kn(n1),平凡图,14.1 图,设D是n阶有向简单图, 若D中每个顶点均与其余的n-1个顶点相邻,则称D为n阶有向完全图 设D是n阶有向简单图, 若D的基图是中每个顶点均与其余的n-1个顶点相邻,则称D为Kn,则称D是n阶竞赛图,14.1 图,定义14.7 设G为n阶无向简单图,若vV(G) , 均有d(v)=k,则称G为k-正则图,彼德森图,14.1 图,超立方体 (k-方体) : 它的顶点是0和1组成的有序 k元组, 两个顶点相邻当且仅当两个k元有序组恰有一个元不同 共有 2k 个顶点,依次编号为 000000, , 111111 两个顶点相邻当且仅当两个顶点的编号恰好有一位不同,4-方体,在4-方体中从顶点0010到1100的路径计算,1) 0010改变第1位得到0000,2) 0000改变第2位得到0100,3) 0100改变第3位得到1100,4-方体中从顶点0010到1100的路径为: 0010000001001100,14.1 图,定义14.8 设G=,G=为两个图, 如果 V V, E E, 称G是G的子图,G是G的母图,记作G G 如果G是G的子图,且 V V 或 E E,则称G为G的真子图 如果G是G的子图,且 V = V ,则称G为G的生成子图,14.1 图,设G=,V1V且V1, 称以V1为顶点集,以G中两个端点都在V1中的边组成 边集E1的图为G的V1导出子图,记作GV1 设G=,E1E且E1, 称以E1为顶点集,以G中与E1中边关联的顶点组成 顶点集 V1的图为G的E1导出子图,记作GE1,V1= v2,v3,v4,v5 ,E1= e1,e3,e4 ,14.1 图,定理 设非负整数序列d1, d2, dn 满足 d1 d2 dk dk+1 dn 则它是某个简单图的度序列的充分必要条 件是 为偶数 并且 对于任意的1 k n有成立,14.1 图,例 试判定序列5, 5, 3, 2, 2, 1是否为简单图的度序列 解： 当k=1时 5 5 = 1*0+(1+1+1+1+1) 当k=2时 5+5=10 9 = 2*1+(2+2+2+1) 此时 不等式不成立, 即不满足定理的条件 所以它不是简单图的度序列 例14.3 (1)画出4阶3条边的所有非同构的无向简单图 (2)画出3阶2条边的所有非同构的有向简单图,14.1 图,定义14.9 设G=为n阶无向简单图,令 E= (u,v)|uVvVuv(u,v)E 称 G=为G的补图 若 G G,则称G是自补图,图G和它的补图 拼接成一个完全图,G,G,自补图,14.1 图,定义14.10 设G=为无向图 设eE,用 G-e 表示从G中去掉边e,称为删除边e. 又设E E,用G-E表示从G中删除E中的所有边,称为删除E 设vV,用G-v 表示从G中去掉v及所关联的一切边,称为删除顶点v 又设VV,用G-V表示从G中删除V中所有的顶点,称为删除V,图G,14.1 图,设e=(u,v)E ,用 Ge 表示从G中删除e后,将e的两个端点u,v用一个新的顶点w (可以用u或v充当w)代替,并使w关联除e以外u,v关联的所有边,称为边e的收缩 设u,vV(u,v可能相邻也可能不相邻),用G(u,v) (或G+(u,v) )表示在u,v之间加一条边(u,v),称为加新边,图G,14.2 通路与回路,定义14.11 设G为无向标定图,G中的顶点和边组成的一 个交替序列= vi0ej1vi1ej2vi2ejkvik (k0) 称vi0为vik到的通路,其中vir-1,vir 为ejr 的端点 vi0 , vik分别称为的始点和终点 ,中边的条数称为它的长度 如果vi0 = vik 则称为回路 如果的所有边各异,则称简单通路 如果又有 vi0 = vik则称为简单回路 若所有顶点各异(端点除外),所有边也各异,则称为初级通路或路径。如果又有vi0=vik则称为初级回路或圈,14.2 通路与回路,v1e5v4e1v3e2v4e5v1e4v3,v1e5v4e1v3,v1e5v4e1v3e2v4e5v1,v1e4v3e2v1e2v3,14.2 通路与回路,注 长度为奇数的圈称为奇圈 , 长度为偶数的圈称为偶圈 长为1的圈只能由环生成 , 长为2的圈只能由平行边生成 在无向简单图中,圈的长度至少为3 若中有边重复出现,则称为复杂通路 如果又有vi0 = vik 则称为复杂回路 在简单图中可以只用顶点序列表示通路 在有向图中,通路、回路及分类的定义与无向图类似,14.2 通路与回路,v1e5v4e1v3e2v4e5v1e4v3,v1e5v4e1v3,v1e5v4e1v3e2v4,v1e5v4e1v3e4v1,是通路但不是简单通路 是简单通路但不是初级通路 是初级通路(路径) 是圈,14.2 通路与回路,定理14.5 在n阶图G中,若从顶点u到v(uv)存在通路,则 从u到v存在长度小于或等于n-1的通路 推论 在n阶图G中,若从顶点u到v(uv)存在通路,则u到v 一定存在长度小于或等于n-1的初级通路(路径) 定理14.6 在n阶图G中,若从v到自身的回路,则一定存在v 到自身长度小于或等于n的回路 推论 在n阶图G中,若从v到自身的简单回路,则一定存在v 到自身长度小于或等于n的初级回路 例14.4 无向完全图Kn(n3)中有几种非同构的圈 例14.5 无向完全图K3的顶点依次标定a,b,c. 在定义意义K3中有多少不同的圈,14.3 图的连通性,定义14.12 设无向图G=,若u,vV之间存在通路 则称u,v是连通的,记作uv. 规定: vV,vv 若无向图G是平凡图或G中任何两个顶点都是连通的, 则称G为连通图 , 否则称G为非连通图 无向图中顶点之间的连通关系是V上的等价关系 具有自反性、对称性和传递性 完全图Kn(n1)都是连通图,而零图Nn(n2)都是非连通图,14.3 图的连通性,定义14.13 设无向图G=,Vi是V关于顶点 之间的连通关系的一个等价类 称导出子图GVi为G的一个连通分支 G的连通分支数记为p(G),G,V= v1 , v2 , v3 ,v4 ,v5 V1=v1 , v2 , v4 V2= v3 , v5 ,14.3 图的连通性,例 G1是连通图, p(G1)=1 N5是非连通图,p(N5)=5 K5是连通图,p(K5)=1 G2是非连通图, p(G2)=3,G1,14.3 图的连通性,定义14.14 设u,v为无向图G中任意两个顶点, 若 uv , 则称u,v之间长度最短的通路为u,v之间的短程线. 短程线的长度称为u,v之间的距离,记作d(u,v). 当u,v不连通时,规定d(u,v)= 距离有以下性质: u,v,wV(G) d(u,v)0,且当且仅当 u=v 时等号成立 具有对称性: d(u,v)=d(v,u) 满足三角不等式: d(u,v)+d(v,w) d(u,w),14.3 图的连通性,图G如右图所示 d(v1,v3)=2 d(v2,v8)=3 d(v3,v7)=1,14.3 图的连通性,定义14.15 设无向图G=.若存在VV 使得 p(G-V)p(G) , 且对于任意的VV,均有 p(G-V)=p(G),则称V是G的点割集. 若|V|=v,则称v为割点 例 图G如右图所示 v2,v4 是点割集 v3 是点割集 v5 是点割集 v3 , v5 是割点,14.3 图的连通性,定义14.15 设无向图G=.若存在EE 使得 p(G-E)p(G) , 且对于任意的EE,均有 p(G-E)=p(G),则称E是G的边割集. 若|E|=e,则称e为割边或桥 例 图G如右图所示 e2,e3 是边割集 e1,e2 是边割集 e3,e4 是边割集 e1,e4 是边割集 e1,e3 是边割集 e2,e4 是边割集 e5 ,e6 是边割集,e5,e6是割边或桥,14.3 图的连通性,只考虑图是否连通是不够的, 还应该有衡量连通程度的指标,图的点连通度和边连通度 这是两个衡量图的连通程度的重要指标,14.3 图的连通性,定义14.17 设G为无向连通图且不是完全图 称(G)=min|V| |V是G的点割集 为G的点连通度 G的点连通度简称边通度,简记为 规定完全图Kn(n1)的点连通度为n-1 规定非连通图的点连通度为0 如果(G)k,则称G是 k 连通图,k为非负整数 例 如右图,点连通度为1 K5的点连通度为4 K5是1-连通图,2-连通图 3-连通图,4-连通图,14.3 图的连通性,定义14.17 设G为无向连通图 称(G)=min|E| |E是G的边割集 为G的边连通度 (G)简记为 规定非连通图的点连通度为0 如果(G)r,则称G是 r 连通图,r为非负整数 例 如右图所示,边连通度为1 K5的边连通度为4 K5是1边-连通图,2边-连通图 3边-连通图,4边-连通图,14.3 图的连通性,例14.6 求图14.9所示各图的点连通度和边连通度, 并指出它介各是几连通图及几边连通图, 最后将它们按点连通程度及边连通程序排序,点连通程度为: (a)(b)(c)=(f)(d)=(e)(g)=(h),边连通程度为: (a)(b)(c)=(e)=(f)(d)(g)=(h),14.3 图的连通性,定理14.7 对于任何无向图G,有 (G) (G) (G),14.3 图的连通性,对于任意满足 mn 的正整数m, n, 按如下方法构造的图称为哈拉里图, 记为Hm,n 哈拉里图的点 ”连通度、边连通度、最小度都等于 m” 即对于 Hm,n , =m Hm,n的构造方法: 分三种情形: m是偶数 m是奇数,n是偶数 m是奇数,n也是奇数,情形1: m 是偶数 设m = 2r, 则H2r,n构造如下: 以0, 1, 2, n1为其顶点, 对于每一个顶点i, 让它与它的下r 个顶点都相邻 即让顶点i与顶点 i n j 相邻 其中i = 0, 1, 2,n1, j=1,2,r 这里n是模n加法,H4,8 , n=8,m=2r=4,r=2,01,2,12,3,23,4,34,5,45,6,56,7,67,0,70,1,情形2: m 是奇数,n是偶数 设m = 2r + 1, 则H2r+1,n构造如下: 先构造H2r,n 在此基础上, 再让顶点 i与顶点 i n (n/2)相邻 i = 0, 1, 2,(n/2) 1,H5,8 , n=8,m=2r+1=5,r=2,04,15,26,37,05,16,27,38,情形3: m 是奇数, n是奇数 设m = 2r + 1, 则H2r+1,n构造如下: 先构造H2r,n , 在此基础上 再让顶点 i与顶点 i n ( (n+1)/2 ) 相邻 i = 0, 1, 2,(n-1)/2,H5,9 , n=9,m=2r+1=5,r=2,40,先构造H4,8,先构造H4,9,14.3 图的连通性,定义14.19 设D=为一个有向图 vi,vjV,若从vi到vj存在通路,则称vi可达vj,记作vivj. 规定vi总是可达自身的,即vivi 若vivj且vjvi,则称vi与vj是相互可达的,记作vivj 规定 vivi , 都是V上的二元关系 , 是V上的等价关系,14.3 图的连通性,定义14.20 设有向图D= vi,vjV,若vivj,称vi到vj长度 最短的通路为vi到vj的短程线 短程线的长度为vi到vj的距离,记作d=,14.3 图的连通性,定义14.21 设有向图D= 如果D的基图是连通图,则称D是弱连通图,简称连通图. 如果vi,vjV, vivj 与vjvi至少成立其一,则称D是单向连通图 如果vi,vjV,均有vivj,则称D是强向连通图,14.3 图的连通性,定理14.8 D是强连通图当且仅当D中存在经过每个顶点至少一次的回路 定理14.9 D是单向连通图当且仅当D中存在经过每个顶点一次的通路,14.3 图的连通性,扩大路径法 涉及路径和圈的构造性证明中常用的方法 若的始点和终点都不与外的顶点相邻,则称是一条极大路径 任给一条路径,如果它的始点或终点与路径外的某个顶点相邻,就把它延伸到这个顶点,继续这一过程,直到不能向外延伸为止,最后总能得到一条极大路径 上述方法称为扩大路径法,14.3 图的连通性,定义14.22 设无向图G= 若能将V划分成V1和V2(即V1V2=V,V1V2=且V1 ,V2 ),使得G中的每条边的两个端点都是一个属于V1,另一个属于V2, 则称G为二部图(或二分图,偶图), 称V1和V2为互补顶点子集,常将二部图记为 若G是简单二部图,V1中每个顶点均与V2中所有顶点相邻, 则称G为完全二部较,记为Kr,s, 其中r=|V1|,s=|V2| n阶(n2)零图为二部图,14.3 图的连通性,定理14.10 n(n2)阶无向图G是二部图当且仅当G中无奇圈 证 必要性 若G中无圈,结论显然成立 若G中有圈,设C为G中的一个圈,要证C是偶圈 令 C=vi1vi2vikvi1,k2 . 不妨设 vi1V1 , vi1vi2vik 则依次交替属于V1,V2 ,且vikV2 , 因此k为偶数,得证C是偶圈 充分性 不妨设G是连通图, v0V ,否则可对每个连通分支进行讨论 令 V1=v|vV(G)d(v0,v)为偶数 V2=v|vV(G)d(v0,v)为奇数, 设vi,vjV1并且相邻,令e=(vi,vj) v0到vi,vj的短程线分别为i ,j 则它们的长度d(v0,vi),d(v0,vj)都是偶数 于是i ,j和e构成一条长度为奇数的回路 其中由i ,j不共有的边及e构成一个奇圈 与条件矛盾.即不vi,vj相邻. 同理可证V2中的任意两顶点也不相邻. 即G是二部图,14.4 图的矩阵表示,无向图的关联矩阵 定义14.23 设无向图G= V= v1,v2,vn, E= e1 , e2 , , em 令 mij为顶点vi与边ej的关联次数 则称 (mij)nm为G的关联矩阵,记作M(G),14.4 图的矩阵表示,例 图G如右图所示 将图G标定并指定顶点和边的顺序,每列元素之和均为2,这是因为每条边恰好关联两个顶点,第i行的元素之和为顶点vi的度数,i=1,2,n,所有的元素之和为边数的倍,正好是握手定理的内容,第j列与第k列相同当且仅当 ej 与 ek 是平行边,第i行的元素之和为0当且仅当 vj 是孤立点,14.4 图的矩阵表示,有向图的关联矩阵 定义14.24 设有向图D=中无环 V= v1,v2,vn E= e1