欧拉图及哈密顿.ppt

第二章 第一节 欧拉图(1),定义1 给定无孤立结点的无向图G,经过图G的每边一次且仅一次的迹为一条欧拉路.经过图G的每边一次且仅一次的回为一条欧拉回路.说明:(1)由定义,含有欧拉路(回)的图显然是连通的;(2)欧拉路是迹(边互不重复),但不是严格意义上的路.定理1连通图G具有欧拉回路当且仅当其每个顶点的度数为偶数.,欧拉路(2),证明:必要性:不妨设C是从顶点x1开始的无向图G的一条欧拉回路.对该回路中的任何一个内部点xi而言,每出现一次,其度数必增加2,对x1来讲,回路最后在该点结束,当然其度数也为偶数.充分性:若G是连通无向图,作G的一条最长回C,并假设C不是欧拉回路.这样,在C中必存在xkV(C)及关联xk的边e=xk,x1 C;又deg(x1)为偶数,所以存在e1=x1,x2,e2=x2,x3,en=xn,xk,这样在G中又找到一条回C,若G=CUC,则结论成立,反之,继续寻找,总可以找到符合条件的回.,第二章 欧拉图与哈密顿图(2),定理2 连通图G具有欧拉路而无欧拉回路,当且仅当G恰有两个奇数度顶点.证:必要性:设连通图G从顶点a到顶点b有欧拉路C,但不是欧拉回路.在欧拉路C中,除第一边和最后一边外,每经过G中顶点xi(包括a和b),都为顶点xi贡献2度,而C的第一边为a贡献1度,C的最后一条边为b贡献1度.因此,a和b的度数均为奇数,其余结点度数均为偶数.,充分性:设连通图G恰有两个奇数度结点,不妨设为a和b,在图G中添加一条边e=a,b得G,则G的每个结点的度数均为偶数,因而G中存在欧拉回路,故G中必存在欧拉路.定义2 给定有向图D,经过D中每边一次且仅一次的有向迹称为D的有向欧拉路.经过D中每边一次且仅一次的有向闭迹(回),称为有向欧拉回路.,第二章 欧拉图与哈密顿图(3),定理3 具有弱连通性的有向图G具有有向欧拉回路,当且仅当G的每个结点的入度等于出度.具有弱连通性的有向图G具有有向欧拉路,当且仅当在G中,一个结点的入度比出度大1,另一个结点的入度比出度小1,而其余每个结点的入度等于出度.定义3 含有欧拉回路的无向连通图与含有向欧拉回路的弱连通有向图,统称为欧拉图.,求Euler图的Euler回路的Fleury算法.,(1)任意选取一个顶点v0,置W0=v0;(2)假定迹(若是有向图,则是有迹)Wi=v0e1v1eivi已经选出,则用下列方法从E(G)-e1,e2,ei中取ei+1;(a)ei+1与vi关联(若是有向图,ei+1 以vi为起点)(b)除非没有别的边可选择,ei+1不是 Gi=G-e1,e2,ei的割边.(3)当(2)不能执行时,停止.否则让i+1 i,转(2).,定理4若G是Euler图,则Fleury算法终止时得到的迹是Euler回路。,定义1 给定无向图G,若存在一条路经过图G的每个结点一次且仅一次,这条路称为哈密顿路.若存在一条闭路经过图G的每个结点一次且仅一次,这条闭路称为哈密顿回路.定义2给定有向图D,若存在一条路经过图G的每个结点一次且仅一次,这条路称为哈密顿有向路.若存在一条闭路经过图G的每个结点一次且仅一次,这条有向闭路称为哈密顿有向回路.,第二节 哈密顿图(1),第二节 哈密顿图(1),定义3 具有哈密顿回路的无向图与具有哈密顿有向回路的有向图,统称为哈密顿图.例1对于完全图Kn(n3),由于Kn中任意两个顶点之间都有边,从Kn的某一顶点开始,总可以遍历其余节点后,再回到该结点,因而Kn(n3)是哈密顿图.说明:判断一个给定的图是否为哈密顿图,是图论中尚未解决的难题之一,下面介绍若干必要条件和充分条件.,第二节 哈密顿图(2),定理1设任意n(n3)阶图G,对所有不同非邻接顶点x和y,若deg(x)+deg(y)n,则G是哈密顿图.证明:仅就G是无向图加以证明.假设定理不成立.则存在一个阶为n(n3),满足定理条件且边数最多的非哈密顿图,即G是一个非哈密顿图且对G的任何两个非邻接点x1和x2,图G+边x1,x2是哈密顿图.,因为n3,所以G不是完全图.设u和v是G的两个顶点.因此G+边u,v是哈密顿图.且G+边u,v是哈密顿回路一定包含边u,v.故在G中存在一条uv路T=u1u2un(u=u1,v=un)包含G中每个顶点.若u1,uiE(G)(2in),则ui-1,unE(G).否则u1uiui+1unui-1ui-2u1是G的一个哈密顿回路,故对u2,u3,un-1中每一个邻接到u1的顶点存在一个u1,u3,un-1中与un不邻接的顶点,故deg(un)n-1-deg(u1),所以deg(u)+deg(v)n-1矛盾.,第二节(3),定理2 设u和v是n阶图G的不同非邻接点,且deg(u)+deg(v)n,则G+边u,v是哈密顿图当且仅当哈密顿图.定义4 给定n阶图G,若将图G度数之和至少是n的非邻接点用一条边连接起来得图G,对图G重复上述过程,直到不再有这样的结点对存在为止,所得到的图,称为是原图G的闭包,记作C(G).定理3 一个图是哈密顿图当且仅当它的闭包是哈密顿图.,定理4 设G是阶至少为3的图,如果G的闭包是完全图,则G是哈密顿图.定理5如果G是一个n阶(n3)任意图,且对G的每个顶点x,都有deg(x)n/2,则G是哈密顿图.说明:由哈密顿图的定义可知,哈密顿图有向图必是强连通的,哈密顿无向图必无割点.,8.哈密顿图(4),定理5 若G是一个哈密顿图,则对于V(G)的每个非空真子集S,其中W(G-S)为G-S的分支数.证明:设C是G的一个哈密顿回路,则对于V(G)的任意一个非空真子集S,均成立 由于C-S为G-S的一个生成子图,因而W(G-S)W(C-S),故,9.哈密顿图(5),说明:定理6只是一个必要条件,如下的皮特森图,尽管有 但它不是哈密顿图.,10.哈密顿图(6),应用定理5.若G是一个n(n3)阶任意图,且对G的每个顶点x,都有deg(x)n/2,则G是哈密顿图.例1.11个学生要共进晚餐,他们将坐成一个圆桌,计划要求每次晚餐上,每个学生有完全不同的邻座.这样能共进晚餐几次.分析:如何将该问题转化成图论中的相关问题.实际上,可以这样来构造一个图,即以每个学生看作图的顶点,以学生的邻座关系作为图的的边,11.哈密顿图(7),这样学生每次进餐的就坐方式就对应一个哈密顿回路.两次进餐中,每个学生有完全不同的邻座对应着两个没有公共边的哈密顿回路.因为每个学生都可以与其余学生邻座,故问题转化为在图K11中找出所有没有公共边的哈密顿回路的个数.K11中共有 条边,而K11中每条哈密顿回路的长度为11,因此K11中最多有55/11=5条没有公共边的哈密顿回路,构造方法为:设第一条哈密顿回路为(1,2,3,11,1),将1固定在圆心,其余固定在圆周上,如图(1)所示,然后将图的顶点旋转i 3600/10(i=1,2,3,4),从而就得到另外4个哈密顿回路.,12.哈密顿图(8),1(3,2,4,6)5 7(5,3,2,4)(2,4,6,8)3 9(7,5,3,2)(4,6,8,10)2 11(9,7,5,3)(6,8,10,11)4 10(11,9,7,5)(8,10,11,9)6 8(10,11,9,7)图1,例2.有n个人,任意两个人合起来认识其余的n-2个人,证明:当n4时,这n个人能站成一圈,使每一个人的两旁站着自己认识的人.证明:构造简单无向图G=,其中V中的n个结点表示这n个人,G中的边表示他们间的认识关系.对u,vV(G),显然d(u)+d(v)n-2,即其余n-2个结点必与u或v邻接.(1)若u,v相邻,则d(u)+d(v)2+n-2=n;,(2)若u与v不相邻,如果d(u)+d(v)=n-2,则V-u,v中恰有n-2个结点(n4,故V-u,v),其中每个结点只能与u,v中的一个结点相邻.不妨设aV-u,v,且a与u相邻,a与v不相邻,此时对于结点a与u来说,都不与v相邻,这与已知矛盾,所以 d(u)+d(v)n-2,即d(u)+d(v)n-1.,若d(u)+d(v)=n-1,由于n4,在结点集V-u,v中至少有两个结点a和b,其中a与u和v都相邻,而b只与u和v中的一个相邻,不妨设b与u相邻,此时v与b和u都不相邻,显然与已知矛盾,因此d(u)+d(v)n-1,即 d(u)+d(v)n 综上所述,对u,vV(G),都有d(u)+d(v)n,因此G中存在一条哈密顿回路,从而这n个人能站成一圈,使得每一个人的两旁站着自己认识的人.,第三节 并行运算图论模型与格雷码 串行计算机:传统的计算机一般称为串行计算机,即执行程序是一次完成一个操作.实际上,为解决问题而写的算法都设计成一次执行一步,这样的算法称为串行的.到目前为止,几乎所有书本描述的算法都是串行的.然而在有些问题上,如气象模拟,医学图像及密码分析等许多高强度计算问题,即使在超计算机上,也不能通过串行操作在合理时间范围内解决;而且对计算机的运行速度来讲,还,存在着物理上的限制,即总有问题不能用串行操作在合理长度的时间之内解决.另外,随着硬件价格的下降,使得制造并行计算机成为可能.并行计算机就是使用多个处理器实现在同一时间执行多条指令.并行算法就是把问题分成可同时解决的若干子问题,其单个指令流控制着算法的执行,包括把子问题送到不同的处理器,以及把子问题的输入和输出定向到适当的处理器.,采用并行处理,一个处理器需要另一个处理器产生的输出.因此.处理器需要互联.用图来描述带有多重处理器的计算机里处理器的互联网络,是一种十分便利的方法,即所谓的并行运算图论模型.在第一章中介绍的n维立方体Qn中,有2n(n0)个处理器,每个处理器有自己的内存,在一个单位时间内,n维立方体中的每个处理器同时处理一条指令,然后与相邻的处理器通信.若一个处理器要与一个不相邻的处理器通信,第一个处理器要发送一些信息,这包括路径信息及接受者的最终目的地.当然这要花费数个时间段.,许多计算机已经根据n维立方体Qn的模型制造和运行.下面将证明n维立方体Qn中存在哈密顿回路,为此先介绍格雷码.格雷码是以弗兰克.格雷的名字命名的,在20世纪40年代,他为了把传送数字信号过程中的错误的影响降到最低而发现的.下面介绍格雷码的有关定义和构造定理.,定义1 n 阶格雷码是序列s1,s2,st,(t=2n),其中每个si是n位二进制串，满足（1）每个n位二进制串都出现在序列中；（2）si与si+1只有一位不同；（3）st和s1只有一位不同。,定理1令G1表示序列，由Gn-1根据以规则来定义Gn:（1）令 表示序列Gn-1的逆序；（2）令 表示在序列G的每个成员前加0所得的序列；（3）令 表示在序列 的每个成员前加1所得的序列；（4）令G为由 后加上 组成的序列。,例1从G1开始构造G3。,推论.对于每个正整数n2，n维立方体都包含一个哈密顿回路。,0000,0001,1001,1000,0010,0011,1011,1010,0110,0111,1111,1110,0100,0101,1101,1100,例2 证明任一个有限集合的全部子集可以这样排列顺序使任何相邻的两个子集仅相差一个元素.证明:设此有限集为A=a1,a2,an,用长为n的二进制数列对应它的2n个子集:当且仅当子集中含有A的第i个元素时,数列的第二个数码为1,否则为0.以这2n个数列为顶点,当且仅当数列仅一个同位数码相异时,该两顶点间连一边,得到一个图G.显然图G为n维立方体.而n维立方体为哈密顿图.按照一条哈密顿回路的顺序排列对应子集即可.,第四节 算法的时间复杂性,一个算法是有限指令的集合有限性:任何算法都会在有限条指令执行完 后结束。确定性:算法的每一步有精确的定义。输入有零个或多个输入，且输入取自特定 的对象集合。,输出:有一个或多个输出与输入有某种特定关系。唯一性:每一步执行后所得到的中间结果是唯一的，且仅依赖于输入和先前步骤的结果.。通用性:算法适用于一类输入。问题是要求回答的提问通常有几个参数它们的值是特定的，取自定义域。,问题的描述:是对参数进行描述，指出其解是满足什么性质的命题。实例:给问题的全体参数都指定了确定的值便得到一个问题的实例。A是问题P的算法，若算法A对问题P的每个实例都给出正确答案。问题P算法可解，若存在一个算法解答问题P。,算法分析 是指通过分析得到算法所需的时间和空间的估计量。算法的复杂度是指执行算法所需的时间和空间的量。,定义1令f和g为从整数集合或实数集合到实数集合的函数，如果存在常数c和k，使得只要xk就有f(x)cg(x)则称f(x)是O(g(x)记为f(x)=O(g(x)读作f(x)是O(g(x),定理1:令f(x)=an xn+an-1 xn-1+a1 x+a0其中a0、a1、an-1、an为实数，则f(x)=O(xn)定理2 设f1(x)=O(g1(x)、f2(x)=O(g2(x)，则f1(x)+f2(x)=O(max(g1(x)、g2(x)）。,定理3 设f1(x)=O(g1(x)、f2(x)=O(g2(x)，则f1(x)*f2(x)=O(g1(x)*g2(x)。例1对于正整数n，给出n!和logn!的大O估计.解:n!=1*2*3*nnn,故n!=O(nn),又logn!lognn=nlogn,所以logn!=O(nlogn).,例2 给出f(n)=3n*logn!+(n2+3)*logn的大O估计,其中n是正整数。解:logn!=O(nlogn),故3n*logn!=O(n2logn)所以f(n)=O(n2logn).例3 给出f(x)=(x+1)log(x2+1)+3x2的大O估计。解:当x1时,x2+12x2;当x2时,Log(x2+1)log(2x2)3logx,故Log(x2+1)=O(logx),所以(x+1)Log(x2+1)=O(xlogx)又x1时,xlogx x2,所以f(x)=O(x2).,易处理的，能用多项式最坏情况复杂性的算法解决的问题，否则称为不易处理的.P问题:易处理的问题.NP问题：至今没有找到多项式算法，又不能证明它不存在多项式算法的一类问题.NPC问题：其中任何一个问题能用一个多项式时间最坏情况算法解答的一类问题。,例4 冒泡排序 它把一个列表排列成升序；相继地比较相邻的元素，若它们顺序不对，则交换它们。试分析冒泡排序 的最坏时间复杂度。O(n2),第五节 最短路路问题,1.加权图:边上有数的图称为加权图;该数称为边的权。2.最短路问题:如何求两个结点之间的最短路.3.迪克斯曲拉算法:这是荷兰计算机科学教授Edsger W.Dijkstra(1930-)在1959年发现的一个算法.他在1972年获得计算机协会授予的图灵奖,这是计算机科学中最具声望的奖项.迪克斯曲拉算法是求出一个连通加权简单图中从结点a到结点z的最短路.边i,j的权(i,j)0,且结点x的标号为L(x),结束时,L(z)是从x到z的最短路的长度.,4.迪克斯曲拉算法流程,Procedure Dijkstra(G:所有权为正的加权连通简单图)G带有顶点a=v0,v1,vn=z和权w(vi,vj),若vi,vj不是G中的边,则w(vi,vj)=)For i:=1 to n L(vi):=L(a):=0 S:=初始化标记,a的标记为0,其余结点标记为,S是空集While zS beginu:=不属于S的L(u)最小的一个顶点 S:=SuFor 所有不属于S的顶点v If L(u)+w(u,v)L(v)then L(v):=L(u)+w(u,v)这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记End L(z)=从a到z的最短路的长度.,例1.用迪克斯曲拉算法求下图所示的加权图中顶点a与z之间最短路的长度.（见65页）,定理1 迪克斯曲拉算法求出连通简单无向图的中两点之间的最短路的长度。定理2 迪克斯曲拉算法使用O(n2)次运算（加法和比较）来求出n阶连通简单无向加权图中两个顶点之间的最短路的长度。迪克斯曲拉算法可以推广到求加权有向图的最短路。（p68）定理3 设有向图G中不含长度非正的有向圈，并且从点1到其余各点都有有限长的有向路，那么式（2）有唯一有限解。定理4-5见p69.,Floyd算法,Dijkstra算法只求出一个特定顶点到其他各顶点的最短路.但在许多实际问题中,需求出任意两点之间的最短路,如全国各城市之间最短的航线,选址问题等.Floyd算法可以比较好地解决这一问题.为介绍Floyd算法,先定义矩阵的两种运算.定义1.已知矩阵A=(aij)ml,B=(bij)ln,规定C=AB=(cij)mn,其中cij=min(ai1+b1j,ai2+b2j,ail+blj).,定义2.已知矩阵A=(aij)mn,B=(bij)mn,规定D=AB=(dij)mn,其中dij=min(aij,bij).可以利用上面定义的运算求任意两点间的最短距离.已知n阶加权简单图G,设D=(dij)nn是图G的边权矩阵即dij=w(i,j)(若G是有向图,则dij=w),若结点i到结点j无边相连时,则取dij=.然后依次计算出矩阵D2,D3,Dn及S,其中,D2=DD=(dij2)nnD3=D2 D=(dij3)nn,Dn=Dn-1 D=(dijn)nnS=DD2D3Dn=(Sij)nn 由定义可知,dijk表示从结点i到结点j经k边的路(在有向图中即为有向路)中的长度最短者.这就是Floyd算法.请同学们分析一下Floyd算法的时间复杂度.,例2.利用Floyd算法求下图中任意两点间最短有向路的长度.(p71-73),Warshall算法,实质上是考虑经过n次结点转换每一次保留最短路的长度。见P74.,第六节旅行推销员问题和中国投递员问题（NPC问题）一。旅行推销员问题,（最邻近算法给出旅行推销员问题的近似解）步骤如下（1）由任意选择的结点开始，找出于该结点邻近的点，形成一条有边的初始路。（2）以表示最新加到这条路上的结点，从不在路上的所有结点中选一个和最靠近的结点，把连接与这一结点的边加到这条路上，重复这一步骤直到这条路包含图中所有结点。,例1 用“最邻近算法”给出下面加权图中有充分小权的哈密顿路P76.,说明:“最邻近插入方法”是“最邻近法”的一种改进方法.该方法是在每次迭代中都构成一个闭的旅行路线.求解时,在已经建立旅程以外的顶点中,寻找最临近于旅程中某个顶点的顶点,然后将其插入该旅程中,并使增加的距离尽可能小,当全部顶点收入这个旅程后,就找到了所求的最短哈密顿回路的近似解.例2用“最邻近插入方法”找出上图中具有充分小权的哈密顿回路.,定理1 设P是加权连通图G中一条包含G的所有边至少一次的闭链，则P最优的充要条件（具有最小长度）是：（1）P中无二重以上的边；（2）在G的每个圈中C中，重复边集E的长度之和不超过这个圈的长度的一半，即W（E）1/2W（C）.,二.中国邮路问题,奇偶点作业法（1）把G中所有奇度顶点配成对，将每对奇度顶点之间的一条路上的每边改为二重边，得到一个新图G1，新图G1中无奇度顶点，即G1为多重欧拉图.（2）若G1中某对结点间有多于两条边连接，则去掉其中偶数条边，留下一条或两条边连接这两个结点，直到每对相邻结点至多由2条边连接。得到图G2.,（3）检查G2的每个圈C，若某个圈C上重复边集E的权和超过这个圈的权和的一半，则将C按定理1必要性证明中的方法进行调整，直到对G2所有的圈其重复边的权和不超过此圈权和的一半，得到图G3.（4）用Fleury算法求G的Euler回路.,例3 求下图G的最优环游p81.,v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12,2 4 5,5 3 6 4,6 4 6,5 4 4 7,9 3 8,A,V1 2 v10 4 v9 5 v8,V2 6 v11 4 v12 6 v7,5 5 4 4 7 7,V3 9 v4 3 v5 8 v6,B,44,5 5 4 4 7 7,99,8 8,6 4 6,3 6,C,44,6 4 66 6,5 4 4 4 4 7,9 3 8,3 6,D,44,4,3 3,4 5,25 3 6 4,66,66,4,2,例4.设G是分划为X,Y的二分图,且,则G一定不是哈密顿图.(利用分支数反证),例5.设简单图G=,则G是哈密顿图.,证明：G中的任意两点u,v，其度数分别为d(u),d(v)对于图G-u,v都有 m-d(u)-d(v)=Cn-12+2 d(u)+d(v)=(n-1)(n-2)/2+2-(n-2)(n-3)/2=n-2+2=n由定理1 可得 G是哈密顿图。,