图论课件第一章 图的基本概念.ppt

单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,图论及其应用,应用数学学院,1,图论及其应用,作者:张先迪、李正良,购买地点：教材科,2,参考文献,1 美，帮迪图论及其应用,2 美，,Gary,Chartrand,图论导引,，人民邮电出版社，200,7,3,Bela,Bollobas,，现代图论,，科学出版社，,2001,中国科学院研究生教学丛书,4 美，,Fred Buckley,图论简明教程,，清华大学出版社，200,5,李慧霸 王风芹译,3,5 李尉萱，图论，湖南科学技术出版社，,1979,6 美，,Douglas,B.West,图论导引,机械工业出版社，200,7,李建中，骆吉洲译,7 杨洪，图论常用算法选编，中国铁道出版社，198,8,8 陈树柏，网络图论及其应用，科学出版社，19,82,4,9,Chris,Godsil,，,Gordon,Royle,Algebraic Graph Theory,，世界图书出版公司北京公司，,2004,10 王朝瑞，图论，高等教育出版社，198,3,5,第一章 图的基本概念,本次课主要内容,图的概念与图论模型,(,一,),、图论课程简介,(,二,),、图的定义与图论模型,(,三,),、图的同构,(,五,),、顶点的度与图的度序列,(,四,),、完全图、偶图与补图,6,1,、研究对象,图论是研究点与线组成的“图形”问题的一门科学。属于应用数学分支。,(,一,),、图论课程简介,2,、发展历史,图论起源于,18,世纪的,1736,年，标志事件是“哥尼斯堡七桥问题,数学家欧拉被称为“图论之父”,20,世纪,30,年代出版第一本图论著作,7,3,、应用状况,图论的应用已经涵盖了人类学、计算机科学、化学、环境保护、流体动力学、心理学、社会学、交通管理、电信以及数学本身等。,目前，图论已形成很多分支：如结构图论、网络图论、代数图论、拓扑图论等,4,、教学安排,主要介绍图的一些基本概念、基本理论和图论的典型应用。,60,学时。,8,1,、图的定义,(,二,),、图的定义与图论模型,一个图是一个序偶,，记,为,G=(V,E),其中：,(1)V,是一个有限的非空集合，称为顶点集合,其,元素称为顶点或点。用,|V|,表示顶点数；,(2)E,是由,V,中的点组成的无序对构成的集合，称,为边集，其元素称为边，且同一点对在,E,中可以,重复出现多次。用,|E|,表示边数。,9,图可以用图形表示：,V,中的元素用平面上一个黑点表示，,E,中的元素用一条连接,V,中相应点对的任意形状的线表示。,例,1,、设图,G,。这里,V,v,1,v,2,v,3,v,4,E,e,1,e,2,e,3,e,4,e,5,e,6,，,e,1,(v,1,v,2,),，,e,2,(v,1,v,3,),，,e,3,(v,1v,4,),，,e,4,(v,2,v,3,),，,e,5,(v,3,v,2,),，,e,6,(v,3,v,3,),。,v,1,v,2,v,3,v,4,e,1,e,2,e,3,e,4,e,5,e,6,10,图的相关概念：,有限图：顶点集和边集都有限的图称为有限图；,平凡图：只有一个顶点的图称为平凡图；,空图：边集为空的图称为空图；,n,阶图：顶点数为,n,的图称为,n,阶图；,(n,m),图：顶点数为,n,边数为,m,的图称为,(n,m),图；,边的重数：连接两个相同顶点的边的条数称为边的重数；,重数大于,1,的边称为重边；,环：端点重合为一点的边称为环；,简单图：无环无重边的图称为简单图；其余的图称为,复合图；,11,顶点,u,与,v,相邻接：顶点,u,与,v,间有边相连接；其中,u,与,v,称为,该边的两个端点；,顶点,u,与边,e,相关联：顶点,u,是边,e,的端点；,边,e,1,与边,e,2,相邻接：边,e,1,与边,e,2,有公共端点；,2,、图论模型,为了抽象和简化现实世界，常建立数学模型。图是关系的,数学表示，为了深刻理解事物之间的联系，图是常用的数学,模型。,(1),化学中的图论模型,19,世纪，化学家凯莱用图论研究简单烃,即碳氢化合物,12,用点抽象分子式中的碳原子和氢原子，用边抽象原子间,的化学键。,通过这样的建模，能很好研究简单烃的同分异构现象,例如：,C,4H,10,的两种同分异构结构图模型为：,h,h,h,h,h,h,h,h,h,h,h,h,h,h,h,h,h,h,h,h,13,(2),商业中的图论模型,商业中，经常用图来对仓库和零售店进行建模,例如：令,V=w,1,w,2,w,3,r,1,r,2,r,3,r,4,r,5,代表,3,个仓库和,5,个零售点,E=w,1,r,1,w,1,r,2,w,2,r,2,w,2,r,3,w,2,r,4,w,3,r,3,w,3,r,5,代表每个仓库和每个,零售店间的关联。则图模型图形为：,w,1,r,1,r,2,w,2,r,3,r,4,w,3,r,5,(3),最短航线问题,14,用点表示城市，两点连线当且仅当两城市有航线。为了,求出两城市间最短航线，需要在线的旁边注明距离值。,例如：令,V=a,b,c,d,e,代表,5,个城市,E=a b,ad,b c,be,de,代表城市间的直达航线,则航线图的图形为：,a,b,c,d,e,500,320,140,430,370,请求出从,d,到,c,的最短路,15,(4),任务分配问题,有一个旅行团要组织一批人去旅游，其中一些人是朋友,他们要乘坐公共汽车去，而车上的位子是成对的。因此,为了让大家旅途更愉快，旅行团负责人需要将成对的朋,友安排在一起。给出一种安排方案。,该问题可以建立一个图论模型来解决：旅行团的人抽象,为图的顶点，两个顶点连线，当且仅当两个顶点代表的,人是朋友。,问题归结于在模型图中求所谓的“匹配”，关于图的匹配,将在第五章介绍。,16,(5),考试时间安排问题,一个教授需要对期末考试时间进行安排，使得学生们,不会有相互冲突的考试。如何解决？,该问题可以建立一个图论模型来解决：待考的课程可,抽象为图的顶点，连接两个顶点的边表示至少有一个学生,同时选择了这两门课程。,问题归结于在模型图中求所谓的“顶点着色方案”问题，,该问题将在第七章讨论。,例如：有,a,b,c,d,e,f,六门课程。按照上面方法建立,的模型图如下：,17,一种可行的安排方案为：第一时间：,a,d,e;,第二时间：,b,f,；最后：,c.,a,b,c,e,f,d,另一种可行的安排方案为：第一时间：,a,e;,第二时间：,c,d,；最后：,b,f.,(6),旅行售货员问题,一电脑代理商要从她所在城市出发，乘飞机去六个城市，,然后回到出发点，如果要求每个城市只经历一次，能否办,到？给出行走方案。,18,问题归结为在模型图中寻求所谓的“哈密尔顿圈”问题。,将在第四章介绍。,例如：如果模型图如下：,该问题可以建立一个图论模型来解决：城市抽象为,图的顶点，边代表城市间的直达航线。,a,b,c,d,e,f,可行方案,:(1)h,d,e,c,b,a,h (2)h,d,e,c,a,b,h,19,在图论中，一个很值得研究的问题是如何比较两个,图的异同，这就是图的同构问题。,定义：设有两个图,G,1,=(V,1,E,1,),和,G,2,=(V,2,E,2,),若在其顶点,集合间存在双射，使得边之间存在如下关系：设,u,1,u,2,v,1,v,2,u,1,v,1,V,1,u,2,v,2,V,2,;u,1,v,1,E,1,当且仅当,u,2,v,2,E,2,且,u,1,v,1,与,u,2,v,2,的重数相同。称,G,1,与,G,2,同构，记为：,由定义可以得到图同构的几个必要条件：,(,三,),、图的同构,(1),顶点数相同；,(2),边数相同；,(3),关联边数相同的顶点,个数相同。,20,判定图的同构是很困难的，属于,NP,完全问题。对于规模,不大的两个图，判定其是否同构，可以采用观察加推证的,方法。,例,2,证明下面两图不同构。,u,1,v,1,证明,:u,1,的两个邻接点与,v,1,的两个邻接点状况不同。所以，,两图不同构。,21,例,3,证明下面两图同构。,证明,:,作映射,f:v,i,u,i,(i=1,2.10),容易证明，对,v,i,v,j,E(a),有,f(v,i,v,j,),u,i,u,j,E,(b,),(1,i,10,1,j,10),由图的同构定义知，图,(a),与,(b),是同构的。,22,例,4,指出,4,个顶点的非同构的所有简单图。,分析：四个顶点的简单图最少边数为,0,，最多边数为,6,，所以,可按边数进行枚举。,23,(,四,),完全图、偶图与补图,1,、每两个不同的顶点之间都有一条边相连的简单图称为,完全图,.,在同构意义下，,n,个顶点的完全图只有一个，记为,K,n,K,2,K,3,K,5,容易求出：,24,2,、所谓具有二分类（,X,Y,）的偶图（或二部图）是指一个图，,它的点集可以分解为两个,(,非空,),子集,X,和,Y,，使得每条边的一个,端点在,X,中，另一个端点在,Y,中,.,完全偶图是指具有二分类（,X,Y,）的简单偶图，其中,X,的每个顶点与,Y,的每个顶点相连，若,|,X|=m,，,|,Y|=n,，则这样的偶图记为,K,m,n,图,1,图,2,图,1,与图,2,均是偶图，图,2,是,K,2,3,25,3,、对于一个简单图,G,=,（,V,E,），令集合,则图,H,=,（,V,，,E,1,E,）,称为,G,的补图，记为,例如，如下两个图是互补的。,定理：若,n,阶图,G,是自补图,(),则有：,证明：,n,阶图,G,是自补图，则有：,26,所以：,由于,n,是正整数，所以：,(,五,),、顶点的度与图的度序列,G,的顶点,v,的度,d,(,v,),是指,G,中与,v,关联的边的数目，,每个环计算两次。,1,、顶点的度及其性质,分别用,(G),和,(G),表示图,G,的最小与最大度。,27,奇数度的顶点称为奇点，偶数度的顶点称偶点。,设,G,=(,V,E,),为简单图，如果对所有 ，有,d,(,v,)=,k,，称图,G,为,k,-,正则图,定理：图,G,=(,V,E,),中所有顶点的度的和等于边数,m,的,2,倍，即：,证明：由顶点度的定义知：图中每条边给图的总,度数贡献,2,度，所以，总度数等于边数,2,倍。,注：该定理称为图论第一定理，是由欧拉提出的。,欧拉一身发表论文,886,篇，著作,90,部。该定理还有,一个名字：“握手定理”。,28,推论,1,在任何图中，奇点个数为偶数。,证明：设,V,1,V,2,分别是,G,中奇点集和偶点集,.,则由,握手定理有：,是偶数，由于 是偶数，所以 是,偶数，于是 是偶数。,推论,2,正则图的阶数和度数不同时为奇数。,证明：设,G,是k,-,正则图，若,k,为奇数，则由推论,1,知,正则图,G,的点数必为偶数,例,4,与,是简单图,G,的最大度与最小度，求证：,29,证明：由握手定理有：,所以有：,2,、图的度序列及其性质,一个图,G,的各个点的度,d,1,d,2,d,n,构成的非负整数组,(,d,1,d,2,d,n,),称为,G,的度序列。,任意一个图,G,对应唯一一个度序列，图的度序列是,刻画图的特征的重要“拓扑不变量”。,30,图,G,的“拓扑不变量”是指与图,G,有关的一个数,或数组,(,向量,),。它对于与图,G,同构的所有图来说，不会发生改变。,一个图,G,可以对应很多拓扑不变量。如果某组不变,量可完全决定一个图，称它为不变量的完全集。,定理：非负整数组,(d,1,d,2,.,d,n,),是图的度序列的,充分必要条件是：为偶数。,证明：必要性由握手定理立即得到。,如果 为偶数，则数组中为奇数的数字个数,必为偶数。按照如下方式作图,G:,若,d,i,为偶数，则在,与之对应的点作,d,i,/2,个环；对于剩下的偶数个奇数，,31,两两配对后分别在每配对点间先连一条边，然后,在每个顶点画,d,j,-1/2,个环。该图的度序列就是已知,数组。,一个非负数组如果是某简单图的度序列，我们称,它为可图序列，简称图序列。,关于图序列，主要研究,3,个问题：,(1),存在问题：什么样的整数组是图序列？,(2),计数问题：一个图序列对应多少不同构的图？,(3),构造问题：如何画出图序列对应的所有不同构图？,研究现状,:(1),彻底解决了，,(2),解决得不好，,(3),没有解决。,32,定理：非负整数组,是图序列的充分必要条件是：,是图序列。,证明：,设,G,是,对应的简单图，,d(v,i,)=,d,i,情形,1,：点,v,1,与点,v,2,v,3,v,d1+1,邻接，则,G-v,1,的度序列正好,为,1,33,情形,2,：点,v,1,与点,v,d1+2,，,.,v,n,的某些顶点邻接。在这种,情况下，作如下假设：设,v,1,与,v,j0,邻接，但当,kj,0,时，,v,1,与,v,k,不邻接；又设,v,1,与,v,i0,不邻接，但当,ki,0,时，,v,1,与点,v,k,邻接。,v,1,v,2,v,3,v,i0-1,v,j0,v,i0,v,n,则在图中，必然存在点,v,m,，使得,v,m,与,v,i0,邻接，但是,它与,v,j0,不邻接，否则，有,d,j0,d,i0,+1,矛盾！,现在，在图中去掉边,v,1,v,j0,和,v,i0,v,m,加上边,v,j0,v,m,和,v,1,v,i0,显然新图与原图度序列相同，但,j,0,减小了，,i,0,增大了！,34,如此进行下去，最后可以变情形,2,为情形,1,。,是显然的。,例,5,是否为图序列？如果是，,作出对应的一个简单图。,解：,由于 是图序列，所以原序列是,图序列。,35,定理,:(,厄多斯,1960),非负整数组,是图序列的充分必要条件是：,该定理证明很难！,上世纪,60,年代以来，人们又研究所谓的唯一图序列问题。,例,5,就是一个唯一图序列！,36,定理,:,一个满足,d,2,=d,n-1,的图序列,是唯一图序列的充分必要条件是下列条件之一满足：,37,3,、图的频序列及其性质,定理：一个简单图,G,的,n,个点的度不能互不相同,证明：因为图,G,为简单图,，,所以,：,(,G,),n,-1,。,情形,1,：若,G,没有孤立点，则,由鸽笼原理：必有两顶点度数相同；,情形,2,：若,G,只有一个孤立点，设,G1,表示,G,去掉孤立点后的部分，则：,由鸽笼原理：在,G,1,里必有两顶点度数相同；,情形,3,：若,G,只有两个以上的孤立点，则定理显然成立。,38,定义：设,n,阶图,G,的各点的度取,s,个不同的非负整数,d,1,d,2,d,s,。又设度为,d,i,的点有,b,i,个,(,i,=1,2,s,),，则,故非整数组,(,b,1,b,2,b,s,),是,n,的一个划分，称为,G,的频序列。,定理：一个,n,阶图,G,和它的补图有相同的频序列。,39,作业,P29P30 3,4,5,6,8,9,10,11,40,Thank You!,41,