《时期图的基本概念》PPT课件.ppt
《《时期图的基本概念》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《时期图的基本概念》PPT课件.ppt(76页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、本章内容本章内容14.1 14.1 图图14.2 14.2 通路与回路通路与回路14.3 14.3 图的连通性图的连通性14.4 14.4 图的矩阵表示图的矩阵表示14.5 14.5 图的运算图的运算基本要求基本要求作业作业14.1 14.1 图的基本概念图的基本概念q图的定义图的定义q图的一些概念和规定图的一些概念和规定q简单图和多重图简单图和多重图q顶点的度数与握手定理顶点的度数与握手定理q图的同构图的同构q完全图与正则图完全图与正则图q子图与补图子图与补图无序积与多重集合无序积与多重集合无序积与多重集合无序积与多重集合 q设设A A,B B为任意的两个集合,称为任意的两个集合,称 a,b
2、|aAbBAbB为为A A与与B B的的无序积无序积,记作,记作A&BA&B。可将无序积中的无序对可将无序积中的无序对 a,b 记为记为(a,b),并且允许并且允许ab。无论无论a,ba,b是否相等,均有是否相等,均有(a,b)(b,a),因而因而A&BA&BB&AB&A。q元素可以重复出现的集合称为元素可以重复出现的集合称为多重集合多重集合或者或者多重集多重集,某元,某元素重复出现的次数称为该元素的素重复出现的次数称为该元素的重复度重复度。例如例如 在多重集合在多重集合 a,a,b,b,b,c,d 中,中,a,b,c,d的重复度分别为的重复度分别为2,3,1,12,3,1,1。一个一个无向图
3、无向图是一个有序的二元组是一个有序的二元组,E,记作记作G G,其中其中(1 1)VV称为称为顶点集顶点集,其元素称为,其元素称为顶点顶点或或结点结点。(2 2)E E称为称为边集边集,它是,它是无序积无序积V&VV&V的多重子集,其元素称为的多重子集,其元素称为无向无向边边,简称,简称边边。一个一个有向图有向图是一个有序的二元组是一个有序的二元组 E,记作记作D D,其中其中(1 1)VV称为称为顶点集顶点集,其元素称为,其元素称为顶点顶点或或结点结点。(2 2)E E为为边集边集,它是,它是笛卡儿积笛卡儿积VVVV的多重子集,其元素称为的多重子集,其元素称为有向有向边边,简称,简称边边。无
4、向图和有向图无向图和有向图无向图和有向图无向图和有向图说明说明q可以用图形表示图,即用小圆圈(或实心点)表示顶可以用图形表示图,即用小圆圈(或实心点)表示顶点,用顶点之间的连线表示无向边,用有方向的连线点,用顶点之间的连线表示无向边,用有方向的连线表示有向边。表示有向边。例例14.114.1(1)(1)给定无向图给定无向图G G,其中其中 V Vvv1 1,v,v2 2,v,v3 3,v,v4 4,v,v5 5,E=(vE=(v1 1,v,v1 1),(v),(v1 1,v,v2 2),(v),(v2 2,v,v3 3),(v),(v2 2,v,v3 3),(v),(v2 2,v,v5 5),
5、(v),(v1 1,v,v5 5),(v),(v4 4,v,v5 5).).(2)(2)给定有向图给定有向图D=D=,其中其中 V Va,b,c,da,b,c,d,E E,。画出画出G G与与D D的图形。的图形。图的一些概念和规定图的一些概念和规定图的一些概念和规定图的一些概念和规定qG G表示无向图,但有时用表示无向图,但有时用G G泛指图泛指图(无向的或有向的无向的或有向的)。qD D只能表示有向图。只能表示有向图。qV(G)V(G),E(G)E(G)分别表示分别表示G G的的顶点集顶点集和和边集边集。q若若|V(G)|V(G)|n n,则称则称G G为为n n阶图阶图。q若若|V(G)
6、|V(G)|与与|E(G)|E(G)|均为有限数,则称均为有限数,则称G G为为有限图有限图。q若边集若边集E(G)E(G),则称则称G G为为零图零图,此时,又若,此时,又若G G为为n n阶图,则称阶图,则称G G为为n n阶零图阶零图,记作,记作N Nn n,特别地,称特别地,称N N1 1为为平凡图平凡图。q在图的定义中规定顶点集在图的定义中规定顶点集V V为非空集,但在图的运算中可能产为非空集,但在图的运算中可能产生顶点集为空集的运算结果,为此规定生顶点集为空集的运算结果,为此规定顶点集为空集的图顶点集为空集的图为为空空图图,并将空图记为,并将空图记为。标定图与非标定图、基图标定图与
7、非标定图、基图 q将图的集合定义转化成图形表示之后,常用将图的集合定义转化成图形表示之后,常用e ek k表示表示无向边无向边(v vi i,v,vj j)(或或有向边有向边 ),),并称并称顶点或边用字母标定顶点或边用字母标定的图的图为为标定图标定图,否则称为,否则称为非标定图非标定图。q将有向图各将有向图各有向边均改成无向边后的无向图有向边均改成无向边后的无向图称为原来图的称为原来图的基图基图。q易知标定图与非标定图是可以相互转化的,任何无向图易知标定图与非标定图是可以相互转化的,任何无向图G G的各边均加上箭头就可以得到以的各边均加上箭头就可以得到以G G为基图的有向图。为基图的有向图。
8、关联与关联次数、环、孤立点关联与关联次数、环、孤立点 q设设G G为无向图,为无向图,ek(vi,vj)E)E,称称vi,vj为为ek的端点的端点,ek与与vi或或ek与与vj是彼此相是彼此相关联关联的。的。若若vivj,则称则称ek与与vi或或ek与与vj的的关联次数为关联次数为1 1。若若vivj,则称则称ek与与vi的的关联次数为关联次数为2 2,并称,并称ek为为环环。任意的任意的vlVV,若若vlvi且且vlvj,则称则称ek与与vl的的关联次数为关联次数为0 0。q设设D D为有向图,为有向图,ek EE,称称vi,vj为为ek的的端点。端点。若若vivj,则称则称ek为为D D中
9、的中的环环。q无论在无向图中还是在有向图中,无边关联的顶点均称为无论在无向图中还是在有向图中,无边关联的顶点均称为孤立孤立点点。相邻与邻接相邻与邻接 q设无向图设无向图G GVE,vi,vjVV,ek,elEE。若若 etEE,使得使得et(vi,vj),则称则称vi与与vj是是相邻的相邻的。若若ek与与el至少有一个公共端点至少有一个公共端点,则称,则称ek与与el是是相邻的相邻的。q设有向图设有向图D DVE,vi,vjVV,ek,elEE。若若 etEE,使得使得et ,则称则称vi为为et的的始点始点,vj为为et的的终终点点,并称,并称vi邻接到邻接到vj,vj邻接于邻接于vi。若若
10、ek的终点为的终点为el的始点,则称的始点,则称ek与与el相邻相邻。邻域邻域q设无向图设无向图G ,vV,称称 u|uV(u,v)Euv 为为v的的邻域邻域,记做,记做NG(v)。称称NG G(v)v 为为v的的闭邻域闭邻域,记做,记做NG(v)(v)。称称 e|eEe与与v相关联相关联 为为v的的关联集关联集,记做,记做IG(v)。q设有向图设有向图D ,vV,称称 u|uVV EEuv 为为v的的后继元集后继元集,记做,记做+D(v)v)。称称 u|uVV EEuv 为为v的的先驱元集先驱元集,记做,记做-D(v)v)。称称+D D(v)-D D(v)为为v的的邻域邻域,记做,记做ND(
11、v)。称称ND(v)v 为为v的的闭邻域闭邻域,记做,记做ND(v)。举例举例举例举例N NG G(v1 1)+D(d)v2 2,v5 5 NG(v1)v1 1,v2 2,v5 5 I IG G(v1 1)e1 1,e2 2,e3 3 c-D(D(d)a,c N ND D(d)a,c N ND D(d)a,c,d 简单图与多重图简单图与多重图 在无向图中,关联一对顶点的无向边如果在无向图中,关联一对顶点的无向边如果多于多于1 1条条,则称这些,则称这些边为边为平行边平行边,平行边的条数称为,平行边的条数称为重数重数。在有向图中,关联一对顶点的有向边如果在有向图中,关联一对顶点的有向边如果多于多
12、于1 1条条,并且这些,并且这些边的边的始点和终点相同始点和终点相同(也就是它们的方向相同也就是它们的方向相同),则称这些边,则称这些边为为平行边平行边。含平行边的图称为含平行边的图称为多重图多重图。既不含平行边也不含环的图既不含平行边也不含环的图称为称为简单图简单图。例如:例如:在图中,在图中,(a)a)中中e e5 5与与e e6 6是平行边,是平行边,(b)b)中中e e2 2与与e e3 3是平行边,但是平行边,但e e6 6与与e e7 7不是平行边。不是平行边。(a)a)和和(b)b)两个图都不是简单图。两个图都不是简单图。顶点的度数顶点的度数 设设G G为一无向图,为一无向图,v
13、VV,称称v作为边的端点次数之和作为边的端点次数之和为为v的度数的度数,简称为,简称为度度,记做,记做 dG(v)。在不发生混淆时,简记为在不发生混淆时,简记为d(v)。设设D DVE为有向图,为有向图,vVV,称称v作为边的始点次数之和为作为边的始点次数之和为v的出度的出度,记做,记做d+D(v),简记作简记作d+(v)。称称v作为边的终点次数之和为作为边的终点次数之和为v的入度的入度,记做,记做d-D(v),简记作简记作d-(v)。称称d+(v)+)+d-(v)为为v v的的度数度数,记做,记做d(v)。图的度数的相关概念图的度数的相关概念q在无向图在无向图G G中,中,最大度最大度(G)
14、G)maxmaxd(v)|)|vV(G)V(G)最小度最小度(G)(G)mind(mind(v)|)|vV(G)V(G)q在有向图在有向图D D中,中,最大出度最大出度+(D)D)maxmaxd+(v)|)|vV(D)V(D)最小出度最小出度+(D)(D)minmind+(v)|)|vV(D)V(D)最大入度最大入度-(D)(D)maxmaxd-(v)|)|vV(D)V(D)最小入度最小入度-(D)(D)minmind-(v)|)|vV(D)V(D)q称度数为称度数为1 1的顶点为的顶点为悬挂顶点悬挂顶点,与它关联的边称为,与它关联的边称为悬挂边悬挂边。度为偶数度为偶数(奇数奇数)的顶点称为的
15、顶点称为偶度偶度(奇度奇度)顶点顶点。图的度数举例图的度数举例d(v1 1)4(4(注意,环提供注意,环提供2 2度度),4 4,1 1,v4 4是悬挂顶点,是悬挂顶点,e7 7是悬挂边。是悬挂边。d+(a)4 4,d-(a)1 1(环环e1 1提供出度提供出度1 1,提供入度,提供入度1)1),d(a)4+14+15 5。5 5,3 3,+4(4(在在a点达到点达到)+0(0(在在b点达到点达到)-3(3(在在b点达到点达到)-1(1(在在a和和c点达到点达到)握手定理握手定理 设设G G为任意无向图,为任意无向图,V V v1 1,v2 2,vn,|E|E|m,则则说明说明任何无向图中,各
16、顶点度数之和等于边数的两倍。任何无向图中,各顶点度数之和等于边数的两倍。证明证明G G中每条边中每条边(包括环包括环)均有两个端点,均有两个端点,所以在计算所以在计算G G中各顶点度数之和时,中各顶点度数之和时,每条边均提供每条边均提供2 2度,当然,度,当然,m条边,共提供条边,共提供2 2m度。度。定理定理14.2 14.2 设设D D为任意有向图,为任意有向图,V V v1 1,v2 2,vn,|E|E|m,则则 握手定理的推论握手定理的推论推论推论任何图任何图(无向的或有向的无向的或有向的)中,奇度顶点的个数是偶数。中,奇度顶点的个数是偶数。证明证明设设G GVE为任意一图,令为任意一
17、图,令V V1 1 v|vVVd(v)为奇数为奇数 V V2 2 v|vVVd(v)为偶数为偶数 则则V V1 1VV2 2V V,V V1 1VV2 2 ,由握手定理可知由握手定理可知 由于由于2 2m和和,所以,所以为偶数为偶数,但因但因V V1 1中顶点度数为奇数,中顶点度数为奇数,所以所以|V V1 1|必为偶数。必为偶数。问题研究问题研究问题:问题:在一个部门的在一个部门的2525个人中间,由于意见不同,是否可能每个个人中间,由于意见不同,是否可能每个人恰好与其他人恰好与其他5 5个人意见一致?个人意见一致?解答:解答:不可能不可能。考虑一个图,其中顶点代表人,如果两个人意见。考虑一
18、个图,其中顶点代表人,如果两个人意见相同,可用边连接,所以每个顶点都是奇数度。存在奇数个度相同,可用边连接,所以每个顶点都是奇数度。存在奇数个度数为奇数的图,这是不可能的。数为奇数的图,这是不可能的。说明:说明:(1)(1)很多离散问题可以用图模型求解。很多离散问题可以用图模型求解。(2)(2)为了建立一个图模型,需要决定顶点和边分别代表什么。为了建立一个图模型,需要决定顶点和边分别代表什么。(3)(3)在一个图模型中,边经常代表两个顶点之间的关系。在一个图模型中,边经常代表两个顶点之间的关系。度数列度数列设设G G为一个为一个n阶无向图,阶无向图,V V v1 1,v2 2,vn,称称d(v
19、1 1),d(v2 2),d(vn n)为为G G的的度数列度数列。对于顶点标定的无向图,它的度数列是唯一的。对于顶点标定的无向图,它的度数列是唯一的。反之,对于给定的非负整数列反之,对于给定的非负整数列d d1 1,d2 2,dn,若存在若存在V V v1 1,v2 2,vn 为顶点集的为顶点集的n阶无向图阶无向图G G,使得使得d(vi)di,则称则称d是是可图化的可图化的。特别地,若所得图是简单图,则称特别地,若所得图是简单图,则称d是是可简单图化的可简单图化的。类似地,设类似地,设D D为一个为一个n n阶有向图,阶有向图,V V v1 1,v2 2,vn,称称d(v1 1),d(v2
20、 2),d(vn)为为D D的的度数列度数列,另外称,另外称d+(v1 1),d+(v2 2),d+(vn)与与d-(v1 1),d-(v2 2),d-(vn)分别为分别为D D的的出度列出度列和和入度列入度列。度数列举例度数列举例按顶点的标定顺序,度数列为按顶点的标定顺序,度数列为4,4,2,1,34,4,2,1,3。按字母顺序,度数列,出度列,入按字母顺序,度数列,出度列,入度列分别为度列分别为5,3,3,35,3,3,34,0,2,14,0,2,11,3,1,21,3,1,2可图化的充要条件可图化的充要条件 设非负整数列设非负整数列d(d1 1,d2 2,dn),则则d d是可图化的当且
21、仅当是可图化的当且仅当 证明证明必要性。必要性。由握手定理显然得证。由握手定理显然得证。充分性。充分性。由已知条件可知,由已知条件可知,d中有偶数个奇数度点。中有偶数个奇数度点。奇数度点两两之间连一边,剩余度用环来实现。奇数度点两两之间连一边,剩余度用环来实现。5331由握手定理可知必然性显然。由握手定理可知必然性显然。下面证明充分性。下面证明充分性。由已知条件可知,由已知条件可知,d d中有中有2 2k(0kn/2)k(0kn/2)个奇数,个奇数,不妨设它们为不妨设它们为d d1 1,d d2 2,d dk k,d dk+1k+1,d dk+2k+2,d d2k2k。可用多种方法做出可用多种
22、方法做出n n阶无向图阶无向图G G,V Vvv1 1,v,v2 2,v,vn n。比如边集如下产生:在顶点比如边集如下产生:在顶点v vr r与与v vr+kr+k之间连边,之间连边,r r1,2,k1,2,k。若若d di i为偶数,令为偶数,令d d i id di i,若若d di i为奇数,令为奇数,令d d i id di i-1-1,得得d d(d(d 1 1,d d 2 2,d d n n),则则d d i i均为偶数。均为偶数。再在再在v vi i处做出处做出d d i i/2/2条环条环,i i1,n1,n,将所得各边集合在一起组成将所得各边集合在一起组成E E,则则G G
23、的度数列为的度数列为d d。其实,其实,d di i为偶数时,为偶数时,d(vd(vi i)2d2d i i/2/22d2di i/2/2d di i,当当d di i为奇数时,为奇数时,d(vd(vi i)1+2d1+2d i i/2/21+d1+d i i1+d1+di i-1-1d di i,这就证明了这就证明了d d是可图化的。是可图化的。可图化举例可图化举例由定理立即可知,由定理立即可知,(3,3,2,1)(3,3,2,1),(3,2,2,1,1)(3,2,2,1,1)等是不可图化的,等是不可图化的,(3,3,2,2)(3,3,2,2),(3,2,2,2,1)(3,2,2,2,1)等
24、是可图化的。等是可图化的。设设G G为任意为任意n阶无向简单图,则阶无向简单图,则(G)G)n-1-1。证明证明因为因为G G既无平行边也无环,既无平行边也无环,所以所以G G中任何顶点中任何顶点v至多与其余的至多与其余的n-1-1个顶点均相邻,个顶点均相邻,于是于是d(v)n-1-1,由于由于v v的任意性,所以的任意性,所以(G)G)n-1-1。判断下列各非负整数列哪些是可图化的?哪些是可简单图化判断下列各非负整数列哪些是可图化的?哪些是可简单图化的?的?(1)(5,5,4,4,2,1)(1)(5,5,4,4,2,1)不可图化。不可图化。(2)(5,4,3,2,2)(2)(5,4,3,2,
25、2)可图化,不可简单图化。若它可简单图化,可图化,不可简单图化。若它可简单图化,设所得图为设所得图为G G,则则(G)G)max5,4,3,2,2max5,4,3,2,25 5,这与定理矛盾。这与定理矛盾。(3)(3,3,3,1)(3)(3,3,3,1)可图化,不可简单图化。假设该序列可以简单图化,可图化,不可简单图化。假设该序列可以简单图化,设设G GVE以该序列为度数列。以该序列为度数列。不妨设不妨设V Vvv1 1,v,v2 2,v,v3 3,v,v4 4 且且 d(vd(v1 1)d(vd(v2 2)d(vd(v3 3)3,d(v3,d(v4 4)1 1,由于由于d(vd(v4 4)1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 时期图的基本概念 时期 基本概念 PPT 课件
限制150内