资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,离散数学,第七章,图论,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,离散数学-第七章-图论,离散数学-第七章-图论离散数学-第七章-图论图论的起源问题:能否从河岸或小岛出发,不重复地经过所有的桥回到原地。Konigsberg(哥尼斯堡)七桥问题3/26/20212,图论的起源,问题:能否从河岸或小岛出发,不重复地经过所有的桥回到原地。,Konigsberg(哥尼斯堡)七桥问题,10/18/2026,2,Euler将河岸和小岛作为图的结点,七座桥为边,构成一个无向重图,问题化为图论中简单道路的问题。,Euler,(欧拉),1736年对这个问题给出了否定的回答。,10/18/2026,3,一、图的基本概念,洛杉矶,旧金山,芝加哥,丹佛,华盛顿,底特律,纽约,10/18/2026,4,设A、B是两个集合,称,A&B=a,b|a,A,b,B,为A与B的,无序积,。,为方便起见,常将无序对a,b记为(a,b),定义1.1,一个,无向图,是一个有序的二元组,记为G,其中,(1),称为,结点,集,,元素称为,结点,或,顶点,;,(2)称为,边集,,它是无序积V&V的多重子集,其元素称为,无向边,,简称为,边,。,常把无向图记为G=,10/18/2026,5,例1、G,1,=,V,v,0,v,1,v,2,v,3,E,(v,0,v,2,),(v,0,v,3,),(v,1,v,2,),(v,1,v,3,),(v,2,,v,3,),v,0,v,3,v,2,v,1,G,1,10/18/2026,6,G,2,v,0,v,1,v,2,v,3,例2、,G,2,=,V,v,0,v,1,v,2,v,3,E,(v,0,v,3,),(v,1,v,3,),(v,1,v,3,),(v,2,,v,3,),(v,0,v,0,),平行边,环,G,简单图,(,不含平行边也不含环),多重图,10/18/2026,7,洛杉矶,旧金山,芝加哥,丹佛,华盛顿,底特律,纽约,10/18/2026,8,定义1.2,一个,有向图,是一个有序的二元组,记为D,其中,(1)同无向图;,(2)称为,边集,,它是笛卡尔积VV的多重子集,其元素称为,有向边,,简称为,边,。,v,0,v,1,v,2,D,D=,V,v,0,v,1,v,2,,,E,10/18/2026,9,例3、,D=,其中,V=,v,1,,v,2,,v,3,,v,4,E=,v,1,v,2,v,3,v,4,平行边,10/18/2026,10,有时用G泛指图(有向的或无向的),|V(G)|表示G的结点数,|E(G)|表示G的边数,有限图,|V(G)|和|E(G)|均有限,n阶图,|V(G)|=n,零图,E(G)=,洛杉矶,旧金山,芝加哥,丹佛,华盛顿,底特律,纽约,平凡图,1阶零图,空图,V(G)=,10/18/2026,11,标定图,非标定图,在无向图G=中,若e,k,=(v,i,,v,j,),,则,称v,i,,v,j,为边e,k,的,端点,e,k,与v,i,或e,k,与v,j,是,彼此关联的,;,关联次数,邻接点、邻接边,v,1,v,2,v,3,v,4,v,5,孤立点,e,1,e,0,e,4,e,3,e,2,e,5,(v,3,,v,4,),10/18/2026,12,在有向图D=中,若e,k,=,,则,称v,i,为e,k,的,起点,,v,j,为e,k,的,终点,;并称v,i,邻接到,v,j,,v,j,邻接于,v,i,。,v,1,v,2,v,3,v,4,10/18/2026,13,定义1.3,在图G=中,,与结点v(vV)关联的边数称为结点,v的,度数,,简称,度,,记为deg(v)。,(结点上的环关联次数为2),e,2,v,1,v,2,v,3,v,4,e,4,e,3,e,5,e,1,v,2,e,3,v,4,v,1,v,3,e,1,e,2,e,4,e,5,设D=为有向图,,以结点v(vV)作为始点的边数称为,v的,出度,,记作,deg,+,(v);,以v作为终点的边数称为,v的,入度,,记作,deg,-,(v),称,deg,+,(v)+deg,-,(v),为v的度数,记作,deg(v),deg(v,1,)=deg(v,4,)=2 deg(v,2,)=deg(v,3,)=3,deg,+,(v,1,)=3 deg,+,(v,2,)=deg,+,(v,4,)=1 deg,+,(v,3,)=0,deg,-,(v,1,)=deg,-,(v,2,)=deg,-,(v,4,)=1 deg,-,(v,3,)=2,10/18/2026,14,在无向图G中,,令(G)=maxdeg(v)|v,V(G),(G)=mindeg(v)|v,V(G),最大度,最小度,类似可定义有向图的,最大出度,和,最小出度,、,最大入度,和,最小入度,。,有向图中,所有结点的入度之和等于所有结点的出度之和。,10/18/2026,15,定理1.1,设G=为无向图,|V(G)|=n,|E(G)|=m,则,e,2,v,1,v,2,v,3,v,4,e,4,e,3,e,5,e,1,对图的所有顶点的度求和时,得出了什么?,即使出现多重边和环,这个式子仍然成立,握手定理,n=4,m=4,顶点度之和为8,n=4,m=5,结点度之和为10,一个具有10个顶点,每个结点的度都为6的图,有多少条边?,10/18/2026,16,定理1.2,设D=为,有,向图,|V(D)|=n,|E(D)|=m,则,v,2,e,3,v,4,v,1,v,3,e,1,e,2,e,4,e,5,n=4,m=5,结点入度之和为5,结点出度之和为5,10/18/2026,17,推论,无向图中度数为奇数的结点个数是偶数。,证明:,设V,1,和V,2,分别是偶度结点和奇度结点的集合,则,偶数,偶数,偶数,因此|,V,2,|为偶数,任何图,e,2,v,1,v,2,v,3,v,4,e,4,e,3,e,1,10/18/2026,18,例4、,已知无向图G中结点数n与边数m相等,2度结点与3度结点各2个,其余结点的度数均为1,试求G的边数m。,=2,2+3,2+1,(n-4),=n+6,2m=n+6,m=n,m=6,解:由握手定理,10/18/2026,19,定义1.4,设G为n阶无向简单图,若G中每一对结点之间都有边,则称G为,n阶无向完全图,,简称,n阶完全图,,记作,K,n,(n1),k,1,k,2,k,3,k,4,k,5,10/18/2026,20,定义1.4,设D为n阶有向简单图,若D中每个结点都邻接到其余的n-1个结点,又邻接于其余的n-1个结点,则称D为,n阶有向完全图,。,k,1,k,3,k,2,10/18/2026,21,定义1.5,设为n阶无向简单图,以V为结点集,以所有使G成为完全图K,n,的添加边组成的集合为边集的图,称为,的相对于完全图的,补图,,记作,k,4,G,定理1.3,n阶无向完全图,K,n,的边数为n(n-1)/2;,n阶有向完全图的边数为,?,。,n(n-1),10/18/2026,22,图 K,5,图 G,e,d,c,b,a,图 G,1,图 G,3,10/18/2026,23,k,4,G,10/18/2026,24,定义1.6,设G=,G=为两个图,若V,V且E,E,则称,为的,子图,,G为G的,母图,,记作,;,又若V,V或E,E,则称,为的,真子图。,若V,=,V,则称,为的,生成子图,k,4,G,2,G,1,10/18/2026,25,在下图中,,G,1,,,G,2,,,G,3,均是,G,的真子图,其中,G,2,、,G,是,G,的生成子图。,e,3,e,2,e,1,e,4,e,5,e,7,e,6,a,b,d,e,G,e,3,e,2,e,1,e,4,a,b,d,G,1,c,c,e,3,e,4,e,6,a,b,d,e,G,2,c,e,4,e,5,a,d,e,G,3,10/18/2026,26,定义1.7,设G=是的子图,若给定另外一个图,使得=E-E,且中仅包含的边所关联的结点,则称为是子图相对于图G的,补图,。,G,d,b,a,e,c,d,b,e,c,G,d,b,a,e,G,d,b,a,e,G,10/18/2026,27,定义1.8,设G,1,=,G,2,=为两个无向图,若存在一一映射,g:V,1,V,2,对于,v,i,v,j,V,1,,,(v,i,v,j,)E,1,当且仅当 (g(v,i,),g(v,j,)E,2,并且(v,i,v,j,)与(g(v,i,),g(v,j,)的重数相同,,则称,G,1,与,G,2,是,同构,的,记作,G,1,G,2,怎样定义有向图的同构?,10/18/2026,28,例7、,(d),10/18/2026,29,彼得松图(petersen),1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,8,9,7,10,10/18/2026,30,10/18/2026,31,两个图同构必有:,(1)结点数相同;,(2)边数相同;,(3)度数列相同,但不是充分条件,(满足这三个条件的两图不一定同构),10/18/2026,32,例8、画出,K,4,的所有非同构的生成子图。,解:,K,4,的所有非同构的生成子图如下图所示。,10/18/2026,33,二、路与回路,定义2.1,设,为无向标定图,G中结点与边的交替序列,=,v,i0,e,j1,v,i1,e,j2,e,jl,v,il,称为,v,i0,到v,il,的,路,。,v,i0,,v,il,分别称为,的始点和终点,,中边的条数称为它的,长度。,当,v,i0,=v,il,时,该路称为,回路,。,e,2,v,1,v,2,v,3,v,4,e,4,e,3,e,5,e,1,10/18/2026,34,若路中没有重复的边,则称为,迹,。,若,路,中没有重复的点,则称为,通路,。,闭的通路称为,圈,。,e,2,v,1,v,2,v,3,v,4,e,4,e,3,e,5,e,1,10/18/2026,35,(,5,,,1,,,2,,,3,,,4,)是迹,不是通路,因为(,)中,均出现了两次。(c,d,b,c)是圈。,有向图中,路、回路等概念与无向图类似,10/18/2026,36,定理2.1,在n阶图中,若从结点v,i,到v,j,(v,i,v,j,)存在一条路,则从v,i,到v,j,存在长度不大于n-1的路。,推论,在n阶图中,若从,结点,v,i,到,v,j,(v,i,v,j,),存在一条路,则从,v,i,到,v,j,存在长度小于,n,的通路。,10/18/2026,37,定义2.2,设无向图,,u,v,,若,u,v,之间存在路,则称,u,v,是,连通,的,记作,uv,。,定义,2.3,设无向图是平凡图或G中任何两个结点都是连通的,则称G为,连通图,,否则称G为,非连通图,或,分离图,。,任意一个连通无向图的,任两个不同结点都存在一条通路。,10/18/2026,38,k,4,W(G)=1,W(G)=2,非连通图可分为几个不相连通的子图,每一子图本身都是连通的。称这几个子图为的连通分支,G的连通分支数记为W(G)。,10/18/2026,39,设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,。,e,10/18/2026,40,定义2.4,设无向图为连通图,若存在V,1,V,且V,1,,使得W(G-V,1,)1,而对于任意的,V,2,V,1,,均有,W(G-V,2,)=1,则称,V,1,是G的,点割集,,若是,V,1,=v,则称v为,割点,。,W(G),W(G),10/18/2026,41,定义2.5,设无向图,若存在E,E,且E,,使得W(G-E,)W(G),而对于任意的,E,E,,均有,W(G-E,)=W(G),则称,E,是G的,边割集,,若是,E,=e,则称e为,割边,或,桥,。,10/18/2026,42,定义2.6,设为非完全的无向连通图,称,(G)=min|V,|V,为G的点割集,为G的,点连通度,(或连通度),设为无向连通图,称,(G)=min|E,|E,为G的边割集,为G的,边连通度,。,为了产生一个不连通图需要删去的最少的点数,易见:非连通图的点连通度为0,边连通度也为0。,完全图K,n,的点连通度为n-1。,10/18/2026,43,定理2.2,对于任何无向图G,有,(G)(G)(G),证明:,若G不连通,则,(G)=(G)=0(G),若G连通,1)证(G)(G),若G是平凡图,则(G)=0(G),若G不是平凡图,则因每个结点的所有关联的边必含一个边割集,所以(G)(G),10/18/2026,44,2)证(G)(G),设,(G),=1,即有一割边,则,(G)=1,设(G)2,,10/18/2026,45,定理2.3,一个连通无向图G中的结点v是割点的充分必要条件是存在两个结点u和w,使得结点u和w的每一条路都通过v。,10/18/2026,46,定义2.7,设D=为有向图,,v,i,,,v,j,V,若从,v,i,到,v,j,存在路,则称,v,i,可达,v,j,,,记作,v,i,v,j,,规定,v,i,v,i,,如果,v,i,v,j,,且,v,j,v,i,,则称,v,j,与,v,i,是互相可达的,,记作,v,i,v,j,定义2.8,设D,为有向图,,,v,i,,,v,j,,若,v,i,v,j,,,称,v,i,到,v,j,长度最短的路称为,v,i,到,v,j,的,短程线,,,短程线的长度称为,v,i,到,v,j,的距离,,记作d。,易见 d,0,d+d,d,如果从,v,i,到,v,i,不可达,则记为,d=,10/18/2026,47,定义2.9,设D=为简单有向图,,若,v,i,,,v,j,V,,v,i,v,j,与,v,j,v,i,至少有一个成立,则称D是,单侧连通图,。若对,v,i,,,v,j,V,均有,v,i,v,j,,则称D为,强连通图,。,若在D中略去边的方向,将它看成无向图后是连通图,,则称为,弱连通图,。,10/18/2026,48,定理2.4,设D为有向图,D是强连通图当且仅当D中存在经过每个结点至少一次的回路,。,D是单向连通图当且仅当D中存在经过每个结点至少一次的路,。,10/18/2026,49,定义2.10,在简单有向图中,具有强连通性质的最大子图,称为强分图;具有单侧连通性质的最大子图,称为单侧分图;具有弱连通性质的最大子图,称为弱分图,。,定理2.5,在有向图D中,它的每个结点位于且只位于一个强分图中,。,10/18/2026,50,三、图的矩阵表示,图G的三种表示方法:,(1)集合表示,(2)图形表示,(3)矩阵表示,1、邻接矩阵表示,2、关联矩阵表示,10/18/2026,51,定义3.1,设无向图G=是简单图,V=v,1,v,2,v,n,称(a,ij,),nn,为G的,邻接矩阵,,记作A(G),其中,v,1,v,2,v,3,v,4,0 1 1 0,1 0 1 1,1 1 0 1,0 1 1 0,A(G)=,此矩阵有何特征?,对称,a,ij,=,1 (v,i,,v,j,),E,0 (v,i,,v,j,),E 或i=j,第i行上1的个数等于结点v,i,的度数,10/18/2026,52,定义3.1,设有向图D=,V=v,1,v,2,v,n,E=e,1,e,2,e,m,令a,ij,为顶点v,i,邻接到顶点v,j,的边的条数,则称(a,ij,),nn,为D的,邻接矩阵,,记作A(D)。,v,1,v,2,v,3,v,4,V,1,V,2,V,3,v,4,v,1,v,2,v,3,v,4,0 1 1 1,1 0 0 0,0 0 0 0,0 0 1 0,此矩阵有何特征?,A(D)=,第i行上1的个数等于结点v,i,的出度,,第j行上1的个数等于结点v,j,的入度,10/18/2026,53,v,1,v,2,v,3,v,4,0 1 1 1,1 0 0 0,0 0 0 0,0 0 1 0,A(D)=,计算(A(D),2,,(A(D),3,v,1,v,2,v,3,v,4,对无向图G,,计算(A(G),2,,(A(G),3,10/18/2026,54,定理3.1,设A为图G的邻接矩阵,V=v,1,v,2,v,n,为G的结点集,,则A的k次幂A,k,(k1)中元素a,ij,(k),为G中v,i,到v,j,长度为k的路数,,其中a,ii,(k),为到自身长度为k的回路数,而,a,ij,(k),i=1 j=1,n n,为G中长度为k的路的总数,,a,ii,(k),i=1,n,其中,为G中长度为k的回路总数。,10/18/2026,55,定义3.2,设简单有向图D=,V=v,1,v,2,v,n,令,p,ij,=,1 v,i,可达 v,j,0 否则,则称(p,ij,),nn,为D的,可达矩阵,,记作P(D)。,v,1,v,2,v,3,v,4,e,1,e,2,e,3,e,4,e,5,V,1,V,2,V,3,v,4,v,1,v,2,v,3,v,4,1 1 1 1,1 1 1 1,0 0 1 0,0 0 1 1,P(D)=,10/18/2026,56,无向简单图G,定义3.3,设无向图G=,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)。,v,1,v,2,v,3,v,4,e,1,e,4,e,3,e,2,e,5,0 0 0 1,1 1 1 0 0,0 0 1 1 1,0 1 0 1 0,M(G)=,此矩阵有何特征?,10/18/2026,57,有向简单图D,定义3.3,设有向图D=,V=v,1,v,2,v,n,E=e,1,e,2,e,m,令,则称(m,ij,),nm,为D的,关联矩阵,,记作M(D)。,1 v,i,为e,j,的始点,0 v,i,与e,j,不关联,-1 v,i,为e,j,的终点,m,ij,=,10/18/2026,58,v,1,v,2,v,3,v,4,e,1,e,2,e,3,e,4,e,5,V,1,V,2,V,3,v,4,e,1,e,2,e,3,e,4,e,5,1 0 1 -1 1,0 0 0 1 -1,0 -1 -1 0 0,-1 1 0 0 0,M(D)=,10/18/2026,59,【例8.1.4】证明在,n,(,n,2)个人的团体中,总有两个人在此团体中恰好有相同个数的朋友。,解 以结点代表人,二人如果是朋友,则在代表他们的结点间连上一条边,这样可得无向简单图,G,,每个人的朋友数即图中代表它的结点的度数,于是问题转化为:,n,阶无向简单图,G,中必有两个结点的度数相同。,用反证法,设,G,中各顶点的结数均不相同,则度数列为0,1,2,,n,-1,说明图中有孤立结点,这与有,n,-1度结点相矛盾(因为是简单图),所以必有两个结点的度数相同。,10/18/2026,60,【例8.2.1】一个人带着一只狼、一只羊和一捆草要渡河,由于船太小,人做摆渡者一次只能运送一个“乘客”,很显然,如果人不在,狼要吃羊,羊要吃草,问人怎样才能把它们平安地渡过河去?,10/18/2026,61,解 这是通路问题的一个典型实例。用,f,表示人,,w,表示狼,,s,表示羊,,h,表示草。,集合,f,,,w,,,s,,,h,中能平安在一起的子集有:,f,,,w,,,s,,,h,,,f,,,w,,,s,,,f,,,s,,,h,,,f,,,w,,,h,,,f,,,w,,,f,,,s,,,f,,,h,,,w,,,h,,,f,,,w,,,s,,,h,。用顶点表示渡河过程中的状态,状态是二元组:第一元素是集合,f,,,w,,,s,,,h,在渡河过程中留在原岸的子集,第二元素是在彼岸的子集,将一次渡河后代表状态变化的顶点间连边,得图8.2.1。容易看出,一条路径就是一种渡河方案。,10/18/2026,62,图 8.2.1,10/18/2026,63,【例8.2.4】在一次国际会议中,由七人组成的小组,a,b,c,d,e,f,g中,,a,会英语、阿拉伯语;,b,会英语、西班牙语;,c,会汉语、俄语;,d,会日语、西班牙语;,e,会德语、汉语和法语;,f,会日语、俄语;g会英语、法语和德语。问:他们中间任何二人是否均可对话(必要时可通过别人翻译)?,10/18/2026,64,解 用顶点代表人,如果二人会同一种语言,则在代表二人的顶点间连边,于是得到图8.2.3。问题归结为:在这个图中,任何两个顶点间是否都存在着通路?由于图8.2.3是一个连通图,因此,必要时通过别人翻译,他们中间任何二人均可对话。,在连通图中,如果删去一些顶点或边,则可能会影响图的连通性。所谓从图中删去某个顶点,v,,就是将顶点,v,和与,v,关联的所有的边均删去,我们用,G,-,v,记之,并用,G,-,V,表示从,G,中删去,V,的子集,V,。用,G,-,e,表示删去边,e,,用,G,-,E,表示从,G,中删去,E,的子集,E,。,10/18/2026,65,【例8.4.1】判断下列各命题是否是真命题。,(1)任何有相同顶点数和边数的无向图都同构。,(2)图中的初级回路均是简单回路。,(3)任一图,G,的最大度数,(,G,)必小于,G,的顶点数。,(4)在,n,(,n,2)个人中,不认识另外奇数个人的有偶数个人。,10/18/2026,66,解答与分析,(1)假命题。两个图有相同顶点数和边数是二图同构的必要条件,而非充分条件。,(2)真命题。由初级回路和简单回路的定义可知。,(3)假命题。当,G,非简单图时,,(,G,)可大于顶点数。,(4)真命题。将,n,个人抽象成,n,个顶点,若两个人不认识,则在他们的对应顶点之间画一条边,得到无向图,G,。,G,中每个顶点的度数就是该顶点所对应的人不认识的其他人的个数,由握手定理的推论可知,,G,中奇度数的顶点必有偶数个。故在,n,个人中,不认识另外奇数个人的有偶数个人。,10/18/2026,67,【例8.4.2】在六个人的团体中,至少有三个人彼此认识或彼此不认识。,分析 将六个人抽象成六个顶点,若两个人认识,则在他们的对应顶点之间画一条边,得到无向图,G,,则,G,是6阶无向简单图,中的边则表示他们关联的两个顶点代表的人彼此不认识,本题即:证明,G,或它的补图 中存在3个顶点彼此邻接。,10/18/2026,68,图 8.4.1,10/18/2026,69,解 因为,K,6是5,-,正则图,所以,v,V,(,G,)(,v,(),,d,(,v,)在,G,中或在 中大于等于3。不妨设在,G,中,d,(,v,)3,则,v,在,G,中至少关联三个顶点设为,a,、,b,、,c,(见图8.4.1),若此三顶点在,G,中彼此不邻接,则必有三边(,a,,,b,)、(,a,,,c,)、(,b,,,c,)均在 中(图中虚线),亦即,a,、,b,、,c,三点在 中彼此邻接,否则三顶点至少有两个在,G,中邻接,不妨设(,a,,,b,),E,(,G,),则,v,、,a,、,b,为在,G,中彼此邻接的三顶点,故在,G,或 中存在3个顶点彼此邻接。,10/18/2026,70,【例8.4.3】证明无向图,G,与其补图 至少有一个是连通图。,分析 是,G,的补图,即,G,是一个无向完全图。对,G,中任一边,e,,若,e,E,(,G,),则,e,E,();反之若,e,E,(),则,e,E,(,G,)。又,G,与 有相同的顶点集,故只需考虑,G,中的任意二顶点。若,G,是连通图,则命题已成立,所以不妨设,G,不是连通图。,10/18/2026,71,解 假设,G,不是连通图,则,G,至少有两个连通分支,不妨设为,G,1,、,G,2,。对于,G,中的任意二顶点,u,、,v,,设,u,G,1,,此时若,v,G,2,,则必有边(,u,,,v,),所以,u,、,v,在 中连通。此时若,v,G,2,,即,v,G,1,则必存在顶点,w,G,2,,使得(,u,,,w,)且(,v,,,w,),所以,u,、,v,仍在 中连通。故 是连通图。所以,,G,与其补图 至少有一个是连通图。,10/18/2026,72,习 题 八,3设图,G,有,n,个顶点,,n,+1条边,证明,G,中至少有一个顶点的度数大于等于3。,4在简单图中若顶点数大于等于2,则至少有两个顶点的度数相同。,10/18/2026,73,6,G,是,n,阶无向简单图,,n,2为奇数,则,G,与,G,所含的奇度数顶点数相等。,7证明图8.1中,图(,a,)与(,b,)同构,图(,c,)与(,d,)不同构。,8画出4阶无向完全图,K,4,的所有非同构的子图,并指出哪些是生成子图和生成子图的互补情况。,9画出3阶有向完全图的所有非同构的生成子图,指出每个图的补图和生成子图的互补情况。,10/18/2026,74,图 8.1,10/18/2026,75,10如果一个图,G,同构于自己的补图,G,,则称该图为自补图。,(1)有几个非同构的4阶和5阶的自补图?,(2)是否有3阶和6阶的自补图?,11,G,是,n,(,n,3)阶连通图,,G,没有桥,当且仅当对,G,的每一对顶点和每一条边,有一条连接这两个顶点而不含这条边的通路。,12一个连通无向图,G,中的顶点(是割点的充分必要条件是存在两个顶点,u,和w,使得顶点,u,和w之间的每一条路都通过,v,。,10/18/2026,76,13试求图8.2中有向图的所有强分图、单分图和弱分图。,10/18/2026,77,图 8.2,10/18/2026,78,15证明:图的每一个顶点和每一条边都只包含在一个弱分图中。,16有向图,G,如图8.3所示,计算,G,的邻接矩阵的前4次幂,回答下列问题。,(1),G,中,v,1,到,v,4,的长度为4的通路有几条?,(2),G,中,v,1,到,v,1,的长度为4的回路有几条?,10/18/2026,79,(3),G,中长度为4的通路总数是多少?其中有多少条是回路?,(4),G,中长度小于等于4的通路有几条?其中有多少条是回路?,(5)写出,G,的可达矩阵。,10/18/2026,80,图 8.3,10/18/2026,81,Konigsberg(哥尼斯堡)七桥问题,问题:能否从河岸或小岛出发,通过每一座桥,而且仅仅通过一次回到原地。,离散数学,第十五章,欧拉图与哈密顿图,四、欧拉图与哈密顿图,欧拉图,10/18/2026,82,Euler(欧拉)1736年对这个问题,给出了否定的回答。将河岸和小岛作为图的结点,七座桥为边,构成一个无向重图,问题化为图论中迹的问题。,定义4.1,通过图中,所有边,一次且仅一次的路称为,欧拉路,。,通过图中,所有边,一次且仅一次的回路称为,欧拉回路,。,具有欧拉回路的图称为,欧拉图,,具有,欧拉路,而无欧拉回路的图称为,半欧拉图,。,离散数学,第十五章,欧拉图与哈密顿图,10/18/2026,83,离散数学,第十五章,欧拉图与哈密顿图,e,2,v,1,v,2,v,3,v,4,e,4,e,3,e,5,e,1,10/18/2026,84,定理4.1,无向图G是欧拉图当且仅当G是连通的,且G中没有奇度结点。,定理4.2,无向图G是半欧拉图当且仅当G是连通的,且G中恰有两个奇度结点。,离散数学,第十五章,欧拉图与哈密顿图,哥尼斯堡七桥问题,由于四个结点都是奇度结点,不可能有欧拉回路。,e,2,v,1,v,2,v,3,v,4,e,4,e,3,e,5,e,1,10/18/2026,85,如下图中(a)是欧拉图,图(b)是半欧拉图,图(c)既非欧拉图也非半欧拉图。,10/18/2026,86,离散数学,第十五章,欧拉图与哈密顿图,定义4.1,通过图中,所有边,一次且仅一次的单向路称为,单向,欧拉路,。,通过图中,所有边,一次且仅一次的回路称为,欧拉回路,。,具有欧拉回路的图称为,欧拉图,,具有,单向欧拉路,而无欧拉回路的图称为,半欧拉图,。,10/18/2026,87,离散数学,第十五章,欧拉图与哈密顿图,定理4.3,有向图D是欧拉图当且仅当D是强连通的且每个结点的入度都等于出度。,定理4.4,有向图D是半欧拉图当且仅当D是单向连通的,且D中恰有两个奇度结点,其中一个的入度比出度大1,另一个的出度比入度大1,其余结点的入度都等于出度。,10/18/2026,88,当给定了一个欧拉图后,如何找出它的一条欧拉回路?下面的Fleury(于1921年提出)算法解决了这个问题,这个算法的实质是“避桥”。,设,G,是欧拉图。,(1)任选,G,的一个结点,v,0,为起点,并设零条边的路为,l,0,=,v,0,。,(2)设已选好的迹为,l,i,=,v,0,e,1,v,1,e,2,v,2,e,i,v,i,,则按下述方法从,E,-,e,1,,,e,2,,,e,i,中选取边,e,i,+1,:,e,i,+1,与,v,i,关联;,除非没有别的边可选择,否则,e,i,+1,不是,G,i,=,G,-,e,1,,,e,2,,,e,i,的割边(桥)。,(3)当第(2)步不能继续进行时(所有的边已走遍),算法终止。,10/18/2026,89,例 找出下图的一条欧拉回路。,解 从,v,0,出发,先找到,l,3,=,v,0,e,1,v,1,e,2,v,4,e,3,v,5,,因为此时在,G,3,=,G,-,e,1,,,e,2,,,e,3,中,关联,v,5,的边,e,9,和,e,10,均是割边,所以只能选取,e,4,,继续下去,最后可得一条欧拉回路:,e,1,0,e,1,e,9,e,3,e,4,e,2,e,5,e,6,e,7,e,8,1,0,5,4,3,2,v,0,e,1,v,1,e,2,v,4,e,3,v,5,e,4,v,2,e,5,v,4,e,6,v,3,e,7,v,2,e,8,v,1,e,9,v,5,e,10,v,0,10/18/2026,90,离散数学,第十五章,欧拉图与哈密顿图,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,e,1,e,2,e,3,e,4,e,5,e,6,e,8,e,7,e,9,e,10,e,11,e,12,e,13,e,14,v,2,e,2,v,3,e,3,v,4,e,14,v,9,e,10,v,2,e,1,v,1,e,8,v,8,e,9,v,2,能不能走出欧拉回路?,e,10,10/18/2026,91,应用与推广:,一笔画问题,离散数学,第十五章,欧拉图与哈密顿图,10/18/2026,92,中国邮递员问题,(,欧拉回路的应用)(带权图),问题:,邮递员从邮局出发,走遍投递区域的所有街道,送完邮件后回到邮局,怎样使所走的路线全程最短。,若街道图(街道的交叉口为结点)存在欧拉回路,显然此路是全程最短。,离散数学,第十五章,欧拉图与哈密顿图,10/18/2026,93,哈密顿图,哈密顿图的概念源于1859年爱尔兰数学家威廉哈密顿爵士(SirWillianHamilton)提出的一个“周游世界”的游戏。这个游戏把一个正十二面体的二十个结点看成是地球上的二十个城市,棱线看成连接城市的道路,要求游戏者沿着棱线走,寻找一条经过所有结点(即城市)一次且仅一次的回路,如图(a)所示。也就是在图(b)中找一条包含所有结点的圈。,10/18/2026,94,定义4.2,经过图中所有结点一次且仅一次的路称为,哈密顿路,,经过图中所有结点一次且仅一次的回路称为,哈密顿回路,。,具有哈密顿回路的图称为,哈密顿图,具有哈密顿路但不具有哈密顿回路的图称为,半哈密顿图,。,离散数学,第十五章,欧拉图与哈密顿图,图 不存在欧拉路,但有,哈密顿,路。,图存在欧拉路,不存在,哈密顿,路。,10/18/2026,95,乍一看,哈密顿图与欧拉图有某种对偶性,但实际上,前者的存在性问题比后者难得多。迄今为止,寻找到一个判断哈密顿图的切实可用的充分必要条件仍是图论中尚未解决的主要问题之一。人们只是分别给出了一些必要条件和充分条件。,10/18/2026,96,离散数学,第十五章,欧拉图与哈密顿图,定理4.5,若无向图具有哈密顿回路,对于任意V,1,V且V,1,,均有,W(G-,V,1,)|,V,1,|,其中W(G-,V,1,)是G-,V,1,中连通分支数。,a,b,c,d,e,f,10/18/2026,97,证明 设,C,是图,G,中的一条哈密顿回路,,V,1,是,V,的任意非空子集,,a,1,V,1,,,C,-,a,1,是一条通路,若再删去,a,2,V,1,,则当,a,1,、,a,2,邻接时,,W,(,C,-,a,1,,,a,2,)=12;而当,a,1,、,a,2,不邻接时,,W,(,C,-,a,1,,,a,2,)=2,即,W,(,C,-,a,1,,,a,2,)2=|,a,1,,,a,2,|,如此做下去,归纳可证,W,(,C,-,V,1,)|,V,1,|,因为,C,-,V,1,是,G,-,V,1,的生成子图,所以,W,(,G,-,V,1,),P,(,C,-,V,1,)|,V,1,|。,10/18/2026,98,这个定理给出的只是一个无向图是哈密顿图的必要条件,亦即哈密顿图必满足这个条件,满足这个条件的不一定是哈密顿图。,例如,著名的彼得森(,Pe,t,e,rs,e,n)图不是哈密顿图,但对任意的,S,V,,,S,,均满足,W,(,C,-,S,)|,S,|,然而,不满足这个条件的必定不是哈密顿图。,10/18/2026,99,定理4.6,设是阶无向简单图,如果对于G中任意不相邻的结点v,i,v,j,,均有,d(v,i,)+d(v,j,),则中存在哈密顿路。,离散数学,第十五章,欧拉图与哈密顿图,推论1,设是n()阶无向简单图,,如果对于G中任意不相邻的结点v,i,v,j,,均有,d(v,i,)+d(v,j,),则中存在哈密顿回路。,推论2,设G是n(n3)阶无向简单图,若(G)n/2,则G是哈密顿图。,推论3,完全图Kn(n3)均是哈密顿图。,10/18/2026,100,例、设,n,2,有2,n,个人参加宴会,每个人至少认识其中的,n,个人,怎样安排座位,使大家围坐在一起时,每个人的两旁坐着的均是与他相识的人?,解:每个人用一个结点表示,若二人相识,则在其所表的结点间连边。这样得到一个2,n,阶的无向图,因为,(,G,),n,,所以,u,,,v,V,(,G,),,d,(,u,)+,d,(,v,)2,n,,故图中存在一条哈密顿回路,这条回路恰好对应一个座位的适当安排。,10/18/2026,101,货郎担问题,与哈密顿图密切相关的是货郎担问题。设有,n,个村镇,已知每两个村镇之间的距离。一个货郎自某个村镇出发巡回售货,问这个货郎应该如何选择路线,使每个村镇经过一次且仅一次,并且总的行程最短。即在一个带权完全图中,找一个权最小的哈密顿图。,10/18/2026,102,离散数学,第十五章,欧拉图与哈密顿图,带权图,4,28,20,9,25,16,7,5,30,32,15,12,10/18/2026,103,应用问题:,旅行商问题(TSP),问题:从某地出发,恰好一次经过个城市回到,原地,寻找最短的道路。,实质:无向简单带权图,寻找最短的哈密顿回路。,说明:,(1)不一定存在,若无向图是完全图则存在。,(2)图是,连通的,两个城市间总有路,若以两城市间交通费用作为边的权,则是无向图的哈密顿回路。,10/18/2026,104,无向加权完全图的,最近邻域算法,:,从任一顶点出发,记为,1,,找一个与,1,最近的结点,2,,(,1,,,2,)为两个结点的迹。,若找出有个结点的,迹,(,1,,,2,,,p,),在迹外找一个离,p,最近的结点,记为,p+1,,将其加入则得到具有P+1个
展开阅读全文