组合数学-第11章省名师优质课赛课获奖课件市赛课一等奖课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢您,第 11 章图 论 引 导,第1页,11.1 基 本 性 质,11.1基本性质,图G是个二元组 G=(V，E)；,其中，V是图G顶点集合，且V是有限集；,E V V=(x，y)|x，y V，x y称为图G边集，且若边=(x，y)E，则边=(y，x)E，且，被视为同一条边。这么图G，我们也称作简单图。,顶点集合V中顶点个数称为图G阶。,若=(x，y)E是图G一条边，则说边连接顶点x和y；或者说，顶点x和y是邻接；或者说，顶点x和y均依附于边，即，x和，y和 是关联。,第2页,例 G是一个5阶图 G=(V,E),其中 V=a,b,c,d,e；,E=(a,b),(b,c),(c,d),(d,a),(e,a),(e,b),(e,d),G可图示为,11.1 基 本 性 质,第3页,假如边集E是一个多重集，则 G=(V,E)是一个,多重图。在多重图 G=(V,E)中，若边,=(x,y)在E,中出现了m次，则称m是边,重数，记作 m(x,y)。,对于多重图,G=(V,E)，若边集E中允许出现形,如(x,x)边，则称G是普通图，其中边(x,x)称作球。,11.1 基 本 性 质,第4页,例,11.1 基 本 性 质,第5页,对于图G=(V,E)，若V中任意一对不一样顶点x,y，,都有(x,y),E，则称G是一个 n=|V|阶完全图。对于n,阶简单完全图而言，它所包含边数是 n(n-1)/2。把,此图、记作K,n,。,例,K,1,K,2,K,3,K,4,K,5,11.1 基 本 性 质,第6页,对于图 G=(V,E)，若在平面上存在一个画法，使得,E中任意两条边均不相交（仅能在顶点处相交），则称,G是一个平面图。,在普通图 G=(V,E)中，x,V，顶点x度deg(x),是与x关联边条数。尤其，若,=(x,x),E，则,使x度增加了2。设,V=x,1,x,2,x,n,，则,deg(x,i,)=d,i,，,i=1,2,n，使得d,1,d,2,d,n,0，则称,（d,1,d,2,d,n,）,是图G度序列。,定理11.1.1,设G 是一个普通图，则其全部顶点度数,之和 d,1,+d,2,+d,n,是一个偶数，从而，其奇度顶点个数也必为偶数。,11.1 基 本 性 质,第7页,设G=(V,E),G=(V,E)均是普通图。若存在1-1对应：,：V,V,使得：x,y,V，(x,y)在E中重数等于(,(x),(y),),在E中重数，则称G和G是同构，对应,称为G和,G一个同构。,11.1 基 本 性 质,第8页,例 设 G=(a,1,a,2,a,3,a,4,E),G=(x,1,x,2,x,3,x,4,E),定义,(a,i,),=x,i,i=1,2,3,4,且若(a,i,a,j,),E，iff(x,i,x,j,),E,则 G 和G同构。,a,1,a,2,a,3,a,4,x,1,x,2,x,3,x,4,11.1 基 本 性 质,第9页,例,11.1 基 本 性 质,第10页,例,11.1 基 本 性 质,第11页,定理11.1.2,两个同构普通图含有相同度序列。,反之，则不一定。,11.1 基 本 性 质,第12页,设,G,（,V,，,E,）是一个普通图，,x,0,，,x,m,V，若,存在（x,i,x,i+1,）E,i=0,1,2,m-1 则称由这m个边组成,序列:,（x,0,x,1,）,(x,1,x,2,),(x,m-1,x,m,),是连接顶点x,0,和x,m,一条长度为m路径，记作：,x,0,x,1,x,2,x,m,若x,0,x,m,，则称该路径为开，不然为闭路径。,无重复边路径称为迹；无重复顶点路径称为链；,x,0,x,m,链称为圈。,11.1 基 本 性 质,第13页,设,G=(V,，,E),是一个普通图，,x,，,y,V,，,G,中均存在,连接x和y路径，则称,G,是连通图；不然,G,是非连通图。,设,G=(V,E),是一个连通图，,x,，,y,V,x,和,y,之间,距离是连接x和y 路径最短长度，记作d（x，y）。,11.1 基 本 性 质,第14页,设,G=(V,E),是普通图，,G,=(U,F),也是普通图，使得：,且,(x,y),F，有,x,，,y,U,，则称,G,是,G,普通子图。进,一步，若,x,，,y,U,，,(x,y),E,，必有,(x,y),F,，则称,G,是,GU,导出普通子图，记为,G,u,G,；在,G,中，若,U,V,，,则称,G,为,G,生成子图。,11.1 基 本 性 质,第15页,11.1 基 本 性 质,第16页,定理,11.1.3,设,G=(V,E),是普通图，则,V,存在划分,V,1,，,V,2,，,V,k,：,使得：,i,）由,V,i,导出普通子图,G,i,=(V,i,E,j,),是连通，,1,i,k,；,)若ij，则,x,V,i,和,y,V,j,，,G,中不存在连接,x,和,y,路径。并称,G,i,是,G,连通分量,(,连通分支，,连通分图,),，,1,i,k,。,V,i,V,j,=ij,V,i,1i k,11.1 基 本 性 质,第17页,定理,11.1.4,设,G=(V,E),，,G,=(V,E,),，则,G,与,G,同构,必有：,)若,G,是简单图，则,G,也是简单图；,),G,与,G,含有相同数目标连通分量；,)若,G,存在一个长度为,m,圈，则,G,亦然；,)若,G,存在一个,m,阶完全图,K,m,是,G,(导出)普通子,图，则,G,亦然。,11.1 基 本 性 质,第18页,设,G=(V,E),是,n,阶普通图,，V(x,1,x,2,x,n,)。,现定义nn矩阵 A(a,ij,),nn,：,a,ij,连接x,i,和x,j,边数目 1,i，j,n,则称A是G邻接矩阵。,11.1 基 本 性 质,第19页,例,A,x,1,x,2,x,3,x,4,x,5,x,6,0 1 2 0 1 0,1 1 0 0 2 0,2 0 0 1 1 1,0 0 1 1 2 2,1 2 1 2 0 0,0 0 1 2 0 0,x,1,x,2,x,3,x,4,x,5,x,6,11.1 基 本 性 质,第20页,11.2 欧 拉 迹,11.2 欧拉迹,设G(V,E)是一个普通图。若 x,y,V，连接x和,y迹包含了E中每一条边，则该迹称作欧拉迹。,比如,第21页,引理11.2.1,设G(V,E)是普通图，若 x,V，,deg(x)为偶数，则G每条边均属于一条闭迹，因而也,属于一个圈。,定理11.2.2,设G(V,E)是连通普通图，则G中存,在闭欧拉迹，iff x,V，deg(x)是偶数。,例,11.2 欧 拉 迹,第22页,定理11.2.3,设G(V,E)是连通普通图，则G中存在,一条开欧拉迹 iff G中恰好有两个奇度顶点u，v。且G,中任意一条开欧拉迹均连接u和v。,例,11.2 欧 拉 迹,第23页,定理11.2.4,设G(V,E)是连通普通图，G中奇度顶,点个数m0，则G边可划分为m/2个开迹，但不能划分,为少于m/2个开迹。,例,11.2 欧 拉 迹,第24页,例,11.2 欧 拉 迹,第25页,中国邮递员问题：设G(V,E)是连通普通图，G,中是否存在一条最短路径r，使得 ，e最少在r中,出现一次。,定理11.2.5,设G(V,E)是一个含有K|E|条边连通,普通图，则G中存在一条长度为2K闭路径r，使得,，e在r中出现次数等于e重数2倍。,分析 G：G*,G*中每条边重数均是G中每条边重数2倍，,且共有2K条边。依据定理11.2.2，G*中存在一条闭欧,拉迹。此欧拉迹即G中所求。,11.2 欧 拉 迹,第26页,例,11.2 欧 拉 迹,第27页,11.3 Hamilton链和Hamilton圈,11.3 Hamilton链和Hamilton圈,设G(V,E)是一个简单图，是否存在一个圈r，使,得 ，x在r中出现一次且仅出现一次。,若这么图存在，则称其为Hamilton圈。对应，,若G中存在一条链，使得 ，x在该链中出现一次,且仅出现一次，则该链是 Hamilton链。,第28页,例 关于K,n,（n,3）,例,11.3 Hamilton链和Hamilton圈,第29页,设 G(V,E)是一个连通简单图，若 ，,使得图G*（V，Ee）是非连通图，则称边e是图,G一个桥。,定理11.3.1,带有桥连通图中不存在Hamilton圈。,11.3 Hamilton链和Hamilton圈,第30页,设 G(V,E)是一个简单图，且|V|=n。若,，即x与y不邻接，都有：,deg（x）deg（y）,n,则称图G含有Ore性质。,定理11.3.2,设G是一个满足Ore性质，阶数n,3,简单图，则G中存在Hamilton圈。,11.3 Hamilton链和Hamilton圈,x,y,y,x,第31页,11.4 二 分 多 重 图,11.4 二分多重图,设 G(V,E)是一个多重图，若V存在划分X，Y：,XY=V,XY=,X,Y,使得 (x，y),E，,x，,，则称图G是一个二,分多重图，对应 X，Y称为一个二分划。,第32页,例,11.4 二 分 多 重 图,第33页,11.4 二 分 多 重 图,第34页,定理11.4.1 一个多重图是二分 iff 它任意一个圈,长度均是偶数。,分析,1)G(V,E)是二分多重图 G任意一个圈,长度均是偶数。,因为G是二分，所以G存在一个二分划X,Y。,依据二分图定义，G中任一路径上之顶点必交替于,X和Y之间，故|X|Y|。,所以G任一圈其长度必是偶数。,11.4 二 分 多 重 图,第35页,2)G(V,E)任一圈长度是偶数 G是二分。,设G是连通，任取一个x,V，令,X=y|y到x距离是偶数，y,V,Y=y|y到x距离是奇数，y,V,则X，Y必是G一个分划。不然，则有（a，b）,E，,使a，b,X。即 a-x 和 b-x 长度均是偶数。,于是有圈：,a-x b-x,其长为奇数。这与条件矛盾。故不存在（a，b）,E使,a，b,X；一样，也不存在(a，b),E使a，b,Y。,从而X，Y是G二分划。,若G是不连通，则其每个连通分量均是二分。,11.4 二 分 多 重 图,第36页,例 考虑全部n位二进制数组成集合V，令,E=（x，y）|x，y,V，x与y仅有一位不一样,则Q,n,=（V，E）是二分图。因为令,X=x|x有偶数个1，x V,Y=x|x有奇数个1，x V,则X，Y组成Q,n,一个二分划。,Q,1,Q,2,Q,3,11.4 二 分 多 重 图,第37页,定理11.4.2,设G是一个含有二分划X，Y二分图，,1）假如|X|,|Y|，则G中不存在Hamilton圈；,2）假如|X|,=,|Y|，则G中不存在起始于X（或Y）中,顶点又终止于X（或Y）中顶点Hamilton链；,3）假如|X|,|Y|+2，或|Y|,|X|+2则G中不存在,Hamilton链；,4）假如|X|,=,|Y|+1，则G中不存在起始于X终止于Y,中Hamilton链，反之亦然。,11.4 二 分 多 重 图,第38页,例（骑士问题）给定一个8,8棋盘，棋盘上一个格,子表示一个位置，并遵照以下移动规则：,1 垂直移动2格并水平移动1格，或者,2 垂直移动1格并水平移动2格。,现在问题是：骑士从任意指定位置出现。按照移,动规则，是否存在一个可能，使得骑士在棋盘上每,一格恰好出项一次？骑士周游,假如存在上述可能，那么当骑士抵达最终一格时，,遵照一样移动规则，是否能够回到原来起始置？,重复周游,11.4 二 分 多 重 图,第39页,58,43,60,37,52,41,64,35,49,46,57,42,61,36,53,40,44,59,48,51,38,55,34,63,47,50,45,56,33,62,39,54,22,7,32,1,24,13,18,15,31,2,23,6,19,16,27,12,8,21,4,29,10,25,14,17,3,30,9,20,5,28,11,26,设G(V,E)是一个二分图。G二分划是X，Y。,且|X|=m，|Y|=n，则记该二分图为K,m，n,=(X，Y，E)。,11.4 二 分 多 重 图,第40页,11.5 树,11.5 树,设G(V,E)是n阶连通图，且G中不含圈，则称G,是n阶树。,定理11.5.1,一个n阶连通图最少有n-1条边。另外，对,于任意一个正整数n，存在一个恰好为n-1条边连通图。,从n个顶点，n-1条边连通图中去掉任意一条边，得到,一个不连通图，所以，每条边都是一个桥。,定理11.5.2,一个n,1,阶连通图是树，iff G恰好有,n-1条边。,引理11.5.3,设G是一个连通图，,=（x，y）是G,一条边。,是桥，iff G任何圈中不包含,。,第41页,定理11.5.4,设G是一个n阶连通图，则G是树，iff G,中无圈。,定理11.5.5,一个图G是树，iff 任意一对不一样顶点x，y,之间，都有唯一一条链，且该链是长度为,d（x，y）链。,定理11.5.6,设G是一个n阶n,2树，则G中最少有,2个悬挂顶点。,定理11.5.6,任何连通图都有一个生成树。,11.5 树,第42页,