离散数学图论部分.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四部分 图论,1,图论问题的起源,18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块,它们通过七座桥相互连接,如下图.当时该城的市民热衷于这样一个游戏:“一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点？”,S,N,A,B,2,陆地,岛屿 岛屿,陆地,哥尼斯堡七桥问题,如何不重复地走完七桥后回到起点？,。,。,。,A,B,C,D,3,当时人们热衷于这样的游戏：设想从任一个地方出发通过每座桥一次且仅一次后回到原地,这是否可能?但多次实践都发现不行。,1727 年欧拉的朋友向欧拉提出了这个问题是否有解？,1736 年欧拉用图论的方法解决了这个问题,写了第一篇图论的论文,成为图论的,创始人,。,后来称此问题为,哥尼斯堡七桥问题,。,4,但在此之后100年间，没有大的进展。,直到Kirchhoff(克希霍夫)用树的理论解决了电网络问题。这些结果引起了人们的重视,图论的研究进入了一个发展时期。,直到1920年,科尼格(Konig)撰写了许多图论方面的论文。在1936年科尼格(Konig)发表了第一本图论书籍有限图与无限图理论,总结了200年来图论研究的主要成果。,此后的50年,图论经历了一场爆炸性的发展,成为数学科学中一门独立的学科。,5,几十年来图论在理论上和应用上都得到很大 的发展,特别是在近30多年来由于计算机的广泛应用而又得到飞跃的发展。,在,计算机科学、运筹学、化学、物理和社会科学,等方面都取得了不少成果，对计算机学科中的操作系统研究、编译技术、人工智能和计算机网络等方面都有广泛的应用。,这里主要讨论,图的基本概念和算法,为今后的学习和研究打下基础。,6,本章首先给出图、简单图、完全图、子图、路和图的同构等概念，接着研究了连通图性质和规律，给出了邻接矩阵、可达性矩阵、连通矩阵和完全关联矩阵的定义。最后介绍了欧拉图与哈密尔顿图。,7,图的定义,8,9,例,画出下列图形。,G=,其中,V=v,1,v,2,v,3,v,4,v,5,E=(v,1,v,1,),(v,1,v,2,),v,2,v,3,),(v,2,v,3,),(v,1,v,5,),(v,2,v,5,),(v,4,v,5,),。,v,1,v,2,v,3,v,4,v,5,e,1,e,2,e,3,e,4,e,5,e,6,10,例：,画出下列图形。,(2)D=,其中V=v,1,v,2,v,3,v,4,E=,。,v,1,v,2,v,3,v,4,e,1,e,2,e,3,e,4,e,5,e,6,e,7,11,图相关的概念和规定,设 G=为一有向图或无向图。,V,、,E,分别表示,G,的,顶点集,、,边集,，,|V|,、,|E|,分别表示,G,的顶点数、边数。若,|V|=n,则称,G,为,n,阶图,。,(2),若,|V|E|,均为有限数，则称,G,为,有限图,这是本书讨论的重点。,(3),在图,G,中，若,E=,则称,G,为,零图,。此时,若,|V|=n,，,则称,G,为,n,阶零图,，记作,N,n,。,若,|V|=1,，,则称,G,为,平凡图,。,12,(a)图,(b)零图,(c)完全图,没有任何边的图称为,零图,；,只有一个点，没有边的图称为,平凡图,；,任意两点之间都有边的图称为,完全图,。,13,v,1,v,2,v,3,v,4,v,5,e,1,e,2,e,3,e,4,e,5,e,6,在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为,平行边,，平行边的条数称为,重数,。,例：,下图中 e,4,与 e,5,是平行边。,14,v,1,v,2,v,3,v,4,v,5,e,2,e,3,e,4,e,5,e,6,e,7,e,8,在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点与终点相同(即方向相同)，则称这些边为,平行边,。,例,：下图中e,3,与e,4,是平行边,e,7,与e,8,不是平行边（,因为e,7,与e,8,方向不同,）,15,含平行边的图称为,多重图,；,既不含平行边也不含环的图称为,简单图,。,本书主要讨论,简单图,的相关结论。,16,设,G=,为无向图，,e,k,=E,则称,v,i,v,j,为,e,k,的端点，,e,k,与,v,i,或,e,k,与,v,j,是,彼此关联,的。,无边关联的顶点称为,孤立点,。若一条边所关联的两个顶点重合，则称此边为,环,。,v,i,v,j,，,则称,e,k,与,v,i,或,e,k,与,v,j,的,关联次数,为,1,，若,v,i,=,v,j,，,则称,e,k,与,v,i,的关联次数为,2,；若,v,i,不是,e,k,的端点，则称,e,k,与,v,i,的关联次数,0,。,17,设G=为无向图，v,i,v,j,V,e,k,e,l,E,若存在一条边,e,以,v,i,v,j,端点，即,e=(,v,i,v,j,),则称,v,i,与,v,j,是,彼此相邻,的。简称,相邻的。,(2),若,e,k,与,e,l,至少有一个公共端点，则称,e,k,与,e,l,是,彼此相邻的。,简称,相邻,的。,设,D=,为有向图,v,i,v,j,V,e,k,e,l,E,若,e,k,=,除称,v,i,v,j,是,e,k,的端点外，还称,v,i,为,e,k,的,起点,，,v,j,为,e,k,的,终点,，并称,v,i,邻接到,v,j,v,j,邻,接于,v,i,。,18,顶点的度,设G=为一无向图，v,i,V,称v,i,作为边的端点的次数之和为v,i,的,度数,，简称为,度,，记作,deg(v,i,)（或d(v,i,)）。,设D=为一有向图，v,j,V,称v,j,作为边的始点的次数之和,为v,j,的,出度,，记作d,+,(v,j,);称v,j,作为边的终点的次数之和,为v,j,的,入度,，记作d,-,(v,j,);称d,+,(v,j,)+d,-,(v,j,)为v,j,的,度数,，记作d(v,j,)。,称度数为1的顶点为,悬挂顶点,它所对应的边为,悬挂边,。,19,例,：在上图(1)中,d(v,1,)=4,d(v,2,)=4,d(v,5,)=0,在图(2)中,d,+,(v,1,)=2,d,-,(v,1,)=1,d(v,1,)=3,d,+,(v,2,)=1,d,-,(v,2,)=3,d(v,2,)=4,v,1,v,2,v,3,v,4,v,5,e,1,e,2,e,3,e,4,e,5,e,6,(1),v,1,v,2,v,3,v,4,v,5,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,(2),20,在无向图G中,令,(G)=maxd(v)|vV(G);,(G)=mind(v)|vV(G),称(G)和,(G)分别为G的,最大度,和,最小度,。,在有向图D中,可类似定义(D)、,(G)。另外,令,+,(G)=maxd,+,(v)|vV(D),+,(G)=mind,+,(v)|vV(D),-,(G)=maxd,-,(v)|vV(D),-,(G)=mind,-,(v)|vV(D),分别为D的,最大出度、最小出度、最大入度、最小入度,。简记作、,、,+,、,+,、,-,、,-,。,21,v,1,v,2,v,3,v,4,v,5e,1,e,2,e,3,e,4,e,5,e,6,(1),v,1,v,2,v,3,v,4,v,5,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,(2),例,在上图(1)中,最大度=6,最小度,=0,在图(2)中,最大度=4,最小度,=2,最大出度,+,=4,最大入度,-,=3,最小出度,+,=1,最小入度,-,=0。,22,握手定理,设G=为无向图或有向图，,V=v,1,v,2,v,n,|E|=m(m为边数)则,证明,：G中每条边（包括环）均提供2个端点，故在计算各顶点度数的和时，每条边均提供2度，m条边共提供2m度。,=2m。,即每个顶点度数之和等于边数的2倍。,推论,在任何图,G,=,V,E,中，度数为奇数的结点必为偶数个。,23,设,G,=,V,E,是有向图，,v,V,，射入(出)结点,v,的边数称为结点,v,的入(出)度。记为deg,(,v,)(deg,(,v,)。显然，任何结点的入度与出度的和等于该结点的度数，即deg(,v,)=deg,(,v,)+deg,(,v,)。,定理：,在有向图中，所有结点入度的和等于所有结点出度的和。,证明：在有向图中每一条边对应一个入度和一个出度，为图的入度和出度各增加1。所以，所有结点入度的和等于边数，所有结点出度的和也等于边数。,24,设V=v,1,v,2,v,n,为图的顶点集，称(d(v,1,),d(v,2,),d(vn,)为G的,度数序列。,例：,在下图中的度数序列为（4,4,3,1,0)。,v,1,v,2,v,3,v,4,v,5,e,1,e,2,e,3,e,4,e,5,e,6,25,例,(3,3,2,3),(5,2,3,1,4)能成为图的,度数序列吗？为什么？,已知图G中有10条边,4个3度顶点,其,余顶点的度数均不大于2,问G中至少,有多少个顶点?为什么？,解:,由于这两个序列中,奇数个数均为奇数,它们都不能成为图的度数序列。,图中边数m=10,由握手定理可知,G中各顶,点度数之和为20，4个3度顶点占去12度，,还剩8度若其余全是2度顶点,还需要4个顶,点来占用这8度，所以G至少有8个顶点。,26如：,K,3,K,6,K,n,的边数为m=C,n,2,=n(n-1)/2,完全图,设G为n阶无向简单图，若G中每个顶点均与其余的n-1个顶点相邻，则称G为n阶,无向完全图,，简称n阶完全图，记作K,n,(n1)。,27,如：,3阶有向完全图,n阶有向完全图的边数m=,n(n-1）,。,有向完全图,设D为n阶有向简单图，若D中每个顶点都邻接到其余的n-1个顶点，又邻接于其余的n-1个顶点，则称D为,n阶有向完全图,。,28,正则图,在一个无向简单图中，如果每个结点的度数均为,k,，则该图称为,k-,正则图,。,下图所示的图称为彼得森（Petersen）图，是,3-正则图,。完全图是,n-1-正则图,。,29,如：,(1),(3),补图,设G=为n阶无向简单图,以V为顶点集，以所有使G成为完全图 K,n,的添加边组成的集合为边集的图，称为G的,补图,，记作 G。,(2),30,(1),(2),例：,在下图中,(1)是(2)的补图,当然(2)也是(1)的补图,就是说,(1),(2)互为补图 同样,(3),(4)互为补图。,(3),(4),31,子图与生成子图,设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的,生成子图,。,生成子图非常重要。,32,导出子图,V,1,V,且,V,1,以,V,1,为顶点集,以两端点均在,V,1,中的全体边为边集的,G,的子图,称为,V,1,导出的,导出子图,，,记为,GV,1,。,E,1,E,且,E,1,以,E,1,为边集,以,E,1,中边关联的顶点的全体为顶点集的,G,的子图,称为,E,1,导出的,导出子图,记为,GE1,。,33,例：,在上图中，G是母图，G,1,是G的子图，且是真子图；G,2,是G的生成子图；G,3,是由边子集e,4,e,5,的导出子图，记为G e,4,e,5,;G,3,也是由结点子集a,d,e的导出子图，记为G a,d,e,;,34,(1)a,b,d,c,e,1,e,2,e,3,e,4,e,5,e,6,b,d,c,e,3,e,4,e,5,(2),(3),母图同时也是(1)的生成子图。,(2）是(1)子图、真子图。,（3）是（1）的子图、真子图、,生成子图。,c,a,b,d,e,3,e,4,e,5,e,2,例：,判断下列各图的母子关系。,35,图的同构,设G,1,=,G,2,=为两个无(有)向图，若存在双射函数f:V,1,V,2,于,v,i,v,j,V,1,(v,i,v,j,)E,1,(E,1,),(f(v,i,),f(v,j,)E,2,(E,2,)，并且(v,i,v,j,)()与(f(v,i,),f(v,j,)()重数相同，则称G,1,与是G,2,同构,的，记作,G,1,G,2,。,36,换言之：,两个图G,1,=,G,2,=,如果它们的节点间存在一一对应关系（双射），而且这种对应关系也反映在表示边的结点对中(如果是有向边则对应的结点对还保持相同的顺序),则称此两图是,同构,的。,两个图同构的判断非常困难，需要仔细考察图的结点和边的关联关系。,37,如何判断两个图是否同构呢？,答案,：迄今为止还没有有效的算法。,根据定义，则我们得到两个图同构的必要条件：,(1)结点数目相等；,(2)边数相等；,(3)度数相同的结点数目相同（度数序列相同）。,注意：,但这仅仅是G,1,G,2,的必要条件,。两个图就算这三点同时满足也不一定同构。,38,(1)G,(2)G,例：,在下图中,(1)和(2)结点集的元素一一对应,v,1,b,v,2,d,v,3,e,v,4,c,v,5,a,;,边集,(,v,1,v,2,),(b,d),(,v,2,v,3,),(d,e),(,v,3,v,4,),(e,c),(,v,4,v,5,),(c,a),(,v,5,v,1,),(a,b);,度数相同的结点数目相同,是同构的。,(3)-G,a,v,3,v,1,v,2,v,4,v,5,e,d,c,b,v,2,39,a,b,c,d,d,1,a,1,b,1,c,1,a,b,c,d,d,1,a,1,b,1,c,1,a,b,c,d,d,1,a,1,b,1c,1,判断下列三个图是否同构？,40,上图中G,1,和G,2,同构，G,3,和G,4,同构。,41,。,。,。,例,：试证下列两个有向图G,1,=和,G,2,=同构？,a,b,c,d,。,。,v,1,G,1,v,2,v,3,v,4,G,2,证明:,由图可知,V,1,=,a,b,c,d和,V,2,=,v,1,v,2,v,3,v,4,令映射 g:,V,1,V,2,即结点和边的对应关系分别为:g(a),V,1,g(b),V,2,g(c),V,3,g(d),V,4,。显然,映射g是双射,G,1,和,G,2,同构。,42,下图中（a)与（b），（c）与（d）分别顶点数相同、边数相同、度数序列都相同；但它们不同构。,(c),(d),43,图的简单操作,设G=为无向图,(1)设,e,E,用G-,e,表示,从G中去掉边,e,称为,删除边,e,.,又设E,E,用G-E,表示,从G中删除E,中所有边，,称为删除E,；,(2)设,v,V,用G-,v,表示,从G中去掉,v,及所关联的一切边,称为,删除顶点,v,.,又设V,V,用G-V,表示,从G中删除V,中所有顶点，,称为删除V,。,44,(3)设边e=(,u,v,)E,用Ge表示从G中去掉,e,后，,将e的两个端点,u,v,用一个新的顶点,w,(或用,u,或,v,充当,w,)代替，,使,w,关联,e,以外,u,v,关联的所有边，,称为,边,e,收缩4)设,u,v,V,(,u,v,可能相邻也可能不相邻)，,用G(,u,v,),(或G+(,u,v,),表示在,u,v,之间加一条边(,u,v,),称为,加新边,45,图,G,G-,e,5,G-,e,1,e,4,例：,46,G-,v,5,G-,v,4,v,5,G,e,5,47,通路与回路,设G为无向标定图，,G中顶点与边的交替序列,=,v,0,e,1,v,1,e,2,e,l,v,l,称为,v,0,到,v,l,的,通路（路）,，,其中,v,r-1,v,r,为,e,r,的端点。,r,=1,2,l,v,0,v,l,分别称为的起点与终点，,中边的条数,l,称为它的,长度,。,若,v,0,=,v,l,则称通路为,回路,。,若的所有边各异，,则称为,简单通路,，,则称为,简单回路,。,又若,v,0,=,v,l,，,48,若的所有顶点,各异，,所有边也各异，,则称为,初级通路,或,路径,，,则称为,初级回路或圈。,将长度为奇数的圈称为,奇圈,，,长度为偶数的圈称为,偶圈,此时又若,v,0,=,v,l,，,(除,v,0,与,v,l,可能相同外),在初级通路与初级回路的定义中，,仍将初级回路看成初级通路(路径)的特殊情况，,只是在应用中初级通路(路径)都是始点与终点不相同，,长为1的圈只能由环生成，,长为2的圈只能由平行边生成，,因而在简单无向图中，,圈的长度至少为3,若中有边重复出现，,则称为,复杂通路,，,则称为,复杂回路。,又若,v,0,=,v,l,，,49,在有向图中，,通路、回路及分类的定义与无向图中非常类似，,只要注意有向边方向的一致性,在上述定义中，,将回路定义成通路的特殊情况，,即回路也是通路，,又初级通路(回路),是简单通路(回路)，,但反之不真,在简单图中也可以只用顶点序列表示通路(回路)。,可以先将非标定图标成标定图，,为了写出非标定图中的通路(回路)，,再写出通路与回路。,=,v,0,v,1,v,l,v,2,50,定理,在n阶图G中，,若从顶点,v,0,到,v,l,(,v,0,v,l,),存在通路，,则v,0,到v,l,存在长度小于或等于(n-1)的通路。,证：,设,为G中一条长度为,l,的通路，,=,v,0,e,1,v,1,e,2,e,l,v,l,若,l,n,-1,则 满足要求，,否则必有,l,+1,n,即上的顶点数大于G中的顶点数,必存在,k,s,0,k,s,l,使得,v,s,=v,k,即在上存在,v,s,到自身的回路,C,sk,在上删除,C,sk,上的一切边,得=,v,0,e,1,v,1,e,2,v,k,e,s+1,e,l,v,l,仍为,v,0,到,v,l,的通路,且长度至少比,减少1.,若 还不满足要求,则 重复上述过程，,由于G是有限图,经过有限步后,及除,v,s,外的一切顶点,必得,v,0,到,v,l,存在长度小于或等于(,n,-1)的通路。,51,推论,：在n阶图G中，若从顶点,v,i,到,v,j,(,v,i,v,j,)存在通路，则,v,i,到,v,j,存在长度小于或等于(,n,-1)的初级通路(路径)。,定理：,在n阶图G中，若存在从v,i,到自身的回路，,则一定存在v,i,到自身度小于或等于n的回路,推论,：在n阶图G中，若存在从,v,i,到自身的简单回路，则一定存在,v,i,到自身度小于或等于n的初级回路。,52,图的连通性,一个无向图(有向图忽略其方向)G=,如果它的任何两点均是可达的,则称图G为,连通图,，否则称为,非连通图,。,v,1,v,2,v,3,v,5,v,4,v,1,v,2,v,3,v,4,v,5,v6,v,1,v,2,v,3,v,4,v,5,v,6,左图和中图均是连通图，但右图则是非连通图，因为结点v,1,v,2,v,3,与结点v,4,v,5,v,6,间是不可达的。,53,在一个无向图G中，若从顶点v,i,到v,j,存在通路(当然从v,j,到v,i,也存在通路),则称v,i,与v,j,是,连通的,。规定v,i,到自身总是,连通的,。,在一个有向图D中，若从顶点v,i,到v,j,存在通路，则称v,i,可达,v,j,。规定v,i,到自身总是,可达的。,设v,j,v,i,为无向图G中任意两点,若v,j,与v,i,是连通的,则称v,j,与v,i,之间长度最短的通路为v,j,与v,i,之间的,短程线,并称为v,j,与v,i,之间的,距离,记作d,当v,j,不可达v,i,时，规定d=。,54,距离有以下,性质,：,1.d0，v,j,=v,i,时，等号成立。,2.在无向图中还有对称性:d(v,j,v,i,)=d(v,j,v,i,),3.满足三角不等式：d+dd,55,v,3,。,。,。,v,1,e,4,v,2,v,4,v,5,e,1,e,3,e,5,e,6,e,7,v,3,。,。,。,v,1,v,2,v,4,v,5,e,1,e,3,e,5,e,6,连通图,分离图,若无向图G是平凡图或G中任何两个顶点都是连通的，则称G为,连通图,，否则称G为,非连通图,或,分离图,。显然，一个图G是连通的当且仅当G中任意两点都是相连的。,56,v,3,。,。,。,v,1,e,4,v,2,v,4,v,5,e,1,e,3,e,5,e,6,e,7,v,3,。,。,。,v,1,v,2,v,4,v,5,e,1,e,3,v,3,。,。,V,1,v,2,1,3,3,无向图中,顶点之间的连通关系是,等价关系,设G是一个无向图,R是G中顶点之间的连通关系，按着R可将V(G)划分成k(k1)个等价类，记成V,1,V,2,V,k,由它们导出的导出子图GV,i,(i=1,2,k)称为G的,连通分支,，连通分支数个数记为 。,例,:下列图的连通分支数分别为:,57,设D=为一个有向图。,若略去,D,中各有向边的方向后所得无向图,G,是连通图,则称,D,是,连通图,，或称,D,是,弱连通图,，简称为连通图。,若,D,中任意两点至少一个可达另一个,则称,D,是,单向连通图,。,若,D,中任何一对顶点都是相互可达的,则称,D,是,强连通图,。,(1),(2),(3),(1)为,强连通图,(2)为,单向连通图,(3)为,弱连通图,58,一个有向图如果其任何两点间均是互相可达的则称图G是,强连通的,；如果其任何两点间至少存在一向是可达的则称图G是,单向连通的,；如果忽略边的方向后其无向边连通的则称图G是,弱连通的,。,(1),(2),(3),(1)为强连通图 (2)为单向连通图,(3)为弱连通图 (4)为非连通图,4),v,1,v,2,v,3,v,1,v,2,v,3,v,1,v,2,v,3,v,1,v,2,v,3,59,定理：,一个有向图,G,是强连通的充分必要条件是,G,中有一个回路至少包含,G,的每个结点一次。,证明：,设,G,中有一个回路至少包含,G,的每个结点一次，下证,G,是强连通的。,G,中有一个回路至少包含每个结点一次，则,G,中的任意两个结点通过回路互相可达。所以,G,是强连通的。,设,G,是强连通的，下证,G,中有一个回路至少包含,G,的每个结点一次。,若不然，存在结点,v,不在,G,的任何回路上，则,v,与其它任何结点不能互相可达，这与,G,是强连通的矛盾。故,G,中有一个回路至少包含,G,的每个结点一次。,定理：,一个有向图,G,是单向连通的充分必要条件是,G,中有一个路至少包含每个结点一次。,证明略。,60,设无向图 G=,若存在V,V,且V,使得 ,而对于,V的,任意真子集V，即V,V,均有 ，则称V是 G 的,点割集,，若点割集中只有一个顶点v，则称v为,割点,。,v,3,v,2,v,1,v,4,v,5,v,6,v,7,e,2,e,1,e,3,e,4,e,5,e,6,e,7,e,8,e,9,在右图中v,3,v,5,v,2,v,6,为点割集。v,4,v,2,不是点割集,因为它的真子集v,2,已经是点割集了，类似地,v,1,v,6,也不是点割集。,61,设无向图G=若存在E,E,且E,，使得 ，而对于E的任意的真子集E,即E,E,均有,则称E是G的,边割集,，或简称为,割集,。若边割集中只有一条边e,则称e为,割边,或,桥,。,v,3,v,2,v,1,v,4,v,5,v,6,v,7,e,2,e,1,e,3,e,4,e,5,e,6,e,7,e,8,e,9,在左图中e,3,e,4,e,1,e,2,e,3,e,1,e,2,e,4,e,9,等都是边割集,其中e,9,是,割边,。e,6,e,7,e,9,不是边割集,因为它的真子集e,9,已是割边集，类似地,e,6,e,8,e,1,e,2,e,5,也不是割边集。,62,设G=,V,E,是无向连通图，如果G不是完全图k(G)=min,|V,1,|,V,1,是G的点割集,称为图G的,点连通度,。如果G是完全图，规定n阶无向完全图K,n,的点连通度为n1，即,k(K,n,)=n1,。规定不连通图G的点连通度为,0,。即k(G)=0。,无向连通图的点连通度的物理意义是：要使G成为不连通的最少要删除的结点数。如果一个图的点连通度是1，最少删除一个结点，图变为不连通的。,63,设G=,V,E,是无向连通图，如果G是非平凡图，,(G)=min,|E,1,|,E,1,是G的边割集,称为G的,边连通度,。,如果G是平凡图，规定G的边,连通度为0,。规定不连通图G的,边连通度为0,，即,(G)=0。有割边的图的边连通度是1。,无向连通图的边连通度的物理意义是：要使G成为不连通的最少要删除的边数。,64,无向图G的点,连通度k(G),、,边连通度,(G),和,最小度,(G),有下列的关系：,定理：,设G=,V,E,为任意无向图，则,k(G),(G),(G),证明：,如果G是不连通的，由点连通度和边连通度的定义有k(G)=,(G)=0，所以 k(G),(G),(G),如果G是连通图。,先证明,(G),(G),如果G是平凡图，,(G)=0,(G)，即,(G),(G),如果G是非平凡图，设n=,(G)=min,deg(v)|v,V,，则存在G的一个结点v，它关联了n条边，而其它结点关联的边数大于等于n，将v关联的这n条边删除，G成为不连通的。从而这n条边或这n条边中的几条边组成一个边割集，即存在一个边割集的基数小于等于n，所以,65,min,|,E,1,|,E,1,是,G,的边割集,n,=min,deg(,v,)|,v,V,，即,(,G,),(,G,),再证k(,G,),(,G,),设,(,G,)=1，,G,有一条割边，此边的任一端点是割点，k(,G,)=1。所以k(,G,),(,G,)成立。,设,(,G,)2，则可删除某,(,G,)条边，使,G,成为不连通的，而删除其中的,(,G,)1条边，它仍然是连通的且有一个桥，设该桥为,e,=(,u,v,)。对这,(,G,)1条边选取一个不同于,u,，也不同于,v的端点，把这些端点删除，则必至少删除了这,(,G,)1条边。若这样产生的图是不连通的，则k(,G,),(,G,)1,(,G,)。若这样产生的图是连通的，则,e,=(,u,v,)仍是桥。此时再删除,u,或,v,，就必产生了一个不连通图，故k(,G,),(,G,)。,由和得k(,G,),(,G,),(,G,)。,66,下图是无向连通图，点连通度k(G)=1，边连通度,(,G,)=2，最小度,(,G,)=3，此图满足k(,G,),(,G,),(,G,)。,67,例：,在无向连通图G中，结点v是割点的充分必要条件是存在两个结点u和w，使结点u和w之间的每一条路都通过v。,证明：,设v是割点，证明存在两个结点u和w，使结点u和w之间的每一条路都通过v。,v是割点，删除v得G，G至少包含两个连通分支，设其中的两个为G,1,=,V,1,E,1,和G,2,=,V,2,E,2,，,u,V,1,，,w,V,2,，因为G连通，在G中u和w之间必有路，设L是它们之间任意一条路。在G中，由于u和w属于两个不同连通分支，所以，u和w之间必没有路。故L必通过v。,设存在两个结点u和w，使结点u和w之间的每一条路都通过v，证明v是割点。,删除v得子图G，因为结点u和w之间的每一条路都通过v，所以在G中结点u和w之间必无路，即结点u和w不连通。由连通图的定义知，G是不连通的，故v是G的割点。,68,扩大路径法,设G=为n阶无向图,E,设,l,为G中一条路径,若此路径的始点,u,或终点,v,与通路外的顶点相邻,就将它们扩到通路中来,继续这一过程,直到最后得到的通路的两个端点,不与通路外的顶点相邻为止,设最后得到的路径为,l,+k,(长度为,l,的路径扩大成了长度为,l+k,的路径),称,l,+k,为“极大路径”,称使用此种方法证明问题的方法,为“,扩大路径法,”。,v,1,v,u,u,1,u,3,v,3,v,2,u,2,l,+k,为“极大路径”,则与,l,+k,的,最外面的两个端点相邻,的点肯定在,l,+k,上,69,70,二部图(偶图),如果无向图的结点集V分成两个子集V,1,V,2,(即满足V,1,V,2,=,V,1,V,2,=V),使得G中任意一边的两个端点分属于V,1,和V,2,则称G为,二部图,或偶图(或称二分图),V,1,和V,2,称为互补结点子集,常记图G为G=。,若V,1,中的每个结点与V,2,的每个结点都有且只有一个一条边相关联,称G为,完全二分图,记为,K,n,m,其中|V,1,|=n,|V,2,|=m。,71,例：,下面的图均是二部分。,72,例,：完全二分图,K,3,2,z,y,x,a,b,73,例,：完全二分图K,3,3,的两种形式,K,3,3,x,y,z,a,b,c,x,y,z,a,b,c,74,二部图判定定理：,一个无向图G=V,E是二部图当且仅当G中无奇数长度的回路。,证明：必要性,。若G中无回路，结论显然成立。若G中有回路，只需证明G中无奇圈。设C为G中任意一圈，令C=，易知,l,2。不妨设,V1，则必有 V-V1=V2，而,l,必为偶数，于是C为偶圈，由C的任意性可知结论成立。,75,充分性。,不妨设G为连通图，否则可对每个连通分支进行讨论。设v,0,为G中任意一个顶点，令V,1,=v|vV(G)d(v,0,v)为偶数，V,2,=v|vV(G)d(v,0,v)为奇数。,易知，V,1,V,2,V,1,V,2,=，V,1,V,2,=V(G)。下面只要证明V,1,中任意两顶点不相邻，V2中任意两点也不相邻。若存在v,i，,v,j,V1相邻，令（v,iv,j,）=e，设v0到v,i,，v,j,的短程线分别为,i,和,j,，则它们的长度d(v,0,v,i,)，d(v,0,v,j,)都是偶数，于是,i,j,e中一定含奇圈，这与已知条件矛盾，类似可证，V,2,中也不存在相邻的顶点，于是G为二部图。,76,画二部图时，人们习惯于将互补顶点子集V,1,，V,2,分开画，画成下图中（5）,（6）的形式。请读者将图中（1）,（2）,（3）也画成（5）,（6）的形式。有许多实际问题可用二部图表示，并且用二部图的性质来研究和解决实际问题，特别是本书后续章节将专门介绍基于二部图的匹配问题等。,77,图的矩阵表示,设无向图G=,V=v,1,v,2,v,n,Ee,1,e,2,e,m,令m,ij,为顶点v,i,与边e,j,的关联次数，则称(m,ij,),nm,为G的,关联矩阵,，记作M(G)。结点数为距阵的行数，边为距阵的列数。,。,。,。,v,3,v,1,e,4,v,2,v,4,v,5,e,1,e,3,e,5,e,6,e,7,v,6,e,2,1 0 0 0 1 0 0,0 0 0 0 0 1,0 0 1 0 0 1 0,0 0 1 1 0 0 1,0 0 0 1 1 0 0,0 2 0 0 0 1 0,v,1,v,2,v,3,v,4,v,5,v,6,e,1,e,2,e,3,e,4,e,5,e,6,e,7,78,设G=,V,E,是无向图，G的完全关联矩阵M(G)有以下的,性质,：,每列元素之和均为2。这说明每条边关联两个结点。,每行元素之和是对应结点的度数。,所有元素之和是图各结点度数的和，也是边数的2倍。,两列相同，则对应的两个边是平行边。,某行元素全为零，则对应结点为孤立点。,79,1,v,i,为e,j,的始点,m,ij,=0，v,i,与e,j,是不关联的,-1，v,i,为e,j,的终点,则称(m,ij,),nm,为D的,关联矩阵,，记作M(D)。,设有向图D=中,无环,V=v,1,v,2,v,n,E=e,1,e,2,e,m,令m,ij,为顶点v,i,与边e,j,的,关联次数,，则称(m,ij,),nm,为G的,关联矩阵,，记作M(G)。,80,1 -1 0 0 0,-1 0 1 -1 1,0 0 0 0 -1,0 1 -1 1 0,M(D)=,v,1,v,2,v,3,v,4,e,1,e,2,e,3,e,4,e,5,e,1,e,2,e,3,e,4,e,5,V,1,V,2,V,3,v,4,81,-1 -1 1 1 0 0 0,0 1 -1 0 1 0 0,0 0 0 -1 0 1 -1,1 0 0 0 -1-1 1,e,3,e,1,e,2,e,4,e,5,e,6,e,7,例:,如右下有向图的关联矩阵为：,M(D)=,82,设,G,=,V,E,是,有向图,，,G,的完全关联矩阵,M,(,G,)有以下的,性质,：,每列有一个1和一个-1，这说明每条有向边有一个始点和一个终点。,每行1的个数是对应结点的出度，-1的个数是对应结点的入度。,所有元素之和是0，这说明所有结点出度的和等于所有结点入度的和。,两列相同，则对应的两边是平行边。,返回章目录,83,设,有向图,D=，V=v,1,v,2,v,n,n阶方阵A=a,ij,称为G的,邻接矩阵,记作A(D)或A,其元素,1 2 1 0,0 0 1 0,0 0 0 1,0 0 1 0,A=,例,:左图的邻接矩阵为：,v,1,v,2,v,3,v,4,84,有向图邻接矩阵的性质,：,若邻接矩阵的元素全为零,则其对应的图是零图；,若对角线元素为1,则表其对应结点上有环；,若对角线元素为零外全为1则其对应图为完全图；,矩阵某结点行的和为出度,列的和为入度；,矩阵所有元素之和为图的边的总数。,85,设,无向图,G=，V=v,1,v,2,v,n,n阶方阵A=a,ij,称为G的,邻接矩阵,记作A(D)或A,其元素,例,:左图的邻接矩阵为：,86,无向图的邻接矩阵与有向图的邻接矩阵的最大不同在于它是对称的；,且矩阵的每行（每列）的元素的和等于对应结点的度；,其它性质都是类似的，这里就不再重复。,87,定理：,设A(G)是图G的邻接矩阵，A(G),k,=A(G)A(G),k-1,，A(G),k,的第i行，第j列元素 等于从v,i,到v,j,长度为k的路的条数。其中 为v,i,到自身长度为k的回路数。,推论：,设G=,V,E,是n阶简单有向图，A是有向图G的邻接矩阵，B,k,=AA,2,A,k,，B,k,=(),nn,，则 是G中由v,i,到v,j,长度小于等于k的路的条数。是G中长度小于等于k的路的总条数。是G中长度小于等于k的回路数。,88,由邻接矩阵的的积 A,l,可以得到v,i,到v,j,的长度为L的路的总数a,ij,(L),且由 B=A+A,1,+A,2,+A,N,，判断D是否为连通图。,简化运算可用以下定义来表示结点间的可达性,设 D=为有向图,V=v,1,v,2,v,n,令,1,v,i,可达v,j,0，v,i,不可达v,j,A(D)=,p,ij,=,称为D的可达矩阵,记作P(D)简记作P。,89,v,1,v,2,v,3,v,4,例:,求图D=的可达距阵,其中,V=v,1,v,2,v,3,v,4,E=(v,1,v,2,),(v,2,v,3,),(v,2,v,4,),(v,3,v,2,),(v,3,v,4,),(v,3,v,1,),(v,4,v,1,),解：,图D=的邻接距阵：,90,图的可达矩阵为P为：,由P可知,图D的任意两点间均可达,并且每个结点均有回路通过,它是一个强连通图，该结果与图D的可达矩阵所示结果一致。,B,4,=A,1,+A,2,+A,3,+A,4,91,Warshall算法,求可达矩阵,：,设M为有向图D的长度为1的可达矩阵，则1),置新矩阵N=M;,(2),置i=1;,(3),对j(1jn),若N的第j 行第i 列处为1，则对 k=1,2,n 做如下计算：,将N 的第j 行k 列处元素与第i 行k 列处元素进行逻辑加，然后将结果放到第j 行k 列处，即 N j,k=N j,k+N i,k;,(4),i=i+1;,(5),若in,go(3),否则停止。,最终得到的矩阵N即为所求。,92,欧拉图与哈密顿图,93,欧拉图,陆地,岛屿 岛屿,陆地,哥尼斯堡七桥问题:,18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块,它们通过七座桥相互连接,如下图.当时该城的市民热衷于这样一个游戏:“一个散步者怎样才能从某块陆地出发，经每座