欧拉图及哈密顿图

数学建模与数学实验主讲：陈六新[e-mail]欧拉回路与哈密顿回路欧拉图(1)定义1给定无孤立结点的无向图G,经过图G的每边一次且仅一次的迹为一条欧拉路.经过图G的每边一次且仅一次的回为一条欧拉回路.说明:(1)由定义,含有欧拉路(回)的图显然是连通的;(2)欧拉路是迹(边互不重复),但不是严格意义上的路.定理1连通图G具有欧拉回路当且仅当其每个顶点的度数为偶数.第二章欧拉图与哈密顿图(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=v0e1v1…eivi已经选出,则用下列方法从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+1i,转(2).定理4若G是Euler图,则Fleury算法终止时得到的迹是Euler回路。定义1给定无向图G,若存在一条路经过图G的每个结点一次且仅一次,这条路称为哈密顿路.若存在一条闭路经过图G的每个结点一次且仅一次,这条闭路称为哈密顿回路.定义2给定有向图D,若存在一条路经过图G的每个结点一次且仅一次,这条路称为哈密顿有向路.若存在一条闭路经过图G的每个结点一次且仅一次,这条有向闭路称为哈密顿有向回路.哈密顿图(1)哈密顿图(1)定义3具有哈密顿回路的无向图与具有哈密顿有向回路的有向图,统称为哈密顿图.例1对于完全图Kn(n3),由于Kn中任意两个顶点之间都有边,从Kn的某一顶点开始,总可以遍历其余节点后,再回到该结点,因而Kn(n3)是哈密顿图.说明:判断一个给定的图是否为哈密顿图,是图论中尚未解决的难题之一,下面介绍若干必要条件和充分条件.哈密顿图(2)定理1设任意n(n3)阶图G,对所有不同非邻接顶点x和y,若deg(x)+deg(y)n,则G是哈密顿图.证明:仅就G是无向图加以证明.假设定理不成立.则存在一个阶为n(n3),满足定理条件且边数最多的非哈密顿图,即G是一个非哈密顿图且对G的任何两个非邻接点x1和x2,图G+边{x1,x2}是哈密顿图.因为n3,所以G不是完全图.设u和v是G的两个顶点.因此G+边{u,v}是哈密顿图.且G+边{u,v}是哈密顿回路一定包含边{u,v}.故在G中存在一条u-v路T=u1u2…un(u=u1,v=un)包含G中每个顶点.若{u1,ui}E(G)(2in),则{ui-1,un}E(G).否则u1uiui+1…unui-1ui-2…u1是G的一个哈密顿回路,故对{u2,u3,…,un-1}中每一个邻接到u1的顶点存在一个{u1,u3,…,un-1}中与un不邻接的顶点,故deg(un)n-1-deg(u1),所以deg(u)+deg(v)n-1矛盾.定理2设u和v是n阶图G的不同非邻接点,且deg(u)+deg(v)n,则G+边{u,v}是哈密顿图当且仅当G是哈密顿图.定义4给定n阶图G,若将图G度数之和至少是n的非邻接点用一条边连接起来得图G’,对图G’重复上述过程,直到不再有这样的结点对存在为止,所得到的图,称为是原图G的闭包,记作C(G).定理3一个图是哈密顿图当且仅当它的闭包是哈密顿图.定理4设G是阶至少为3的图,如果G的闭包是完全图,则G是哈密顿图.定理5如果G是一个n阶(n3)任意图,且对G的每个顶点x,都有deg(x)n/2,则G是哈密顿图.说明:由哈密顿图的定义可知,哈密顿图有向图必是强连通的,哈密顿无向图必无割点.哈密顿图(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),故.)(SSGWW(CS)S..)(SSGW9.哈密顿图(5)说明:定理5只是一个必要条件,如下的皮特森图,尽管有但它不是哈密顿图.SSGW)(10.哈密顿图(6)应用定理5.若G是一个n(n3)阶任意图,且对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个哈密顿回路.55211C12.哈密顿图(8)1(3,2,4,6)57(5,3,2,4)(2,4,6,8)39(7,5,3,2)(4,6,8,10)211(9,7,5,3)(6,8,10,11)410(11,9,7,5)(8,10,11,9)68(10,11,9,7)图11例2.有n个人,任意两个人合起来认识其余的n-2个人,证明:当n≥4时,这n个人能站成一圈,使每一个人的两旁站着自己认识的人.证明:构造简单无向图G=V,E,其中V中的n个结点表示这n个人,G中的边表示他们间的认识关系.对u,vV(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个结点(n≥4,故V-{u,v}),其中每个结点只能与u,v中的一个结点相邻.不妨设aV-{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,由于n≥4,在结点集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,vV(G),都有d(u)+d(v)≥n,因此G中存在一条哈密顿回路,从而这n个人能站成一圈,使得每一个人的两旁站着自己认识的人.一。旅行推销员问题（TSP）旅行推销员问题和中国投递员问题（NPC问题）（最邻近算法给出旅行推销员问题的近似解）步骤如下:（1）由任意选择的结点开始，找出于该结点邻近的点，形成一条有边的初始路。（2）以x表示最新加到这条路上的结点，从不在路上的所有结点中选一个和x最靠近的结点，把连接x与这一结点的边加到这条路上，重复这一步骤直到这条路包含图中所有结点。(3)将连接起点与最后加入的结点之间的边加到这条路上，就得到一条Hamilton回路。(即得近似解)例1用“最邻近算法”给出下面加权图中有充分小权的哈密顿路P76.D1218AFBEC1669715131835132119说明:“最邻近插入方法”是“最邻近法”的一种改进方法.该方法是在每次迭代中都构成一个闭的旅行路线.求解时,在已经建立旅程以外的顶点中,寻找最临近于旅程中某个顶点的顶点,然后将其插入该旅程中,并使增加的距离尽可能小,当全部顶点收入这个旅程后,就找到了所求的最短哈密顿回路的近似解.例2用“最邻近插入方法”找出上图中具有充分小权的哈密顿回路.推销员问题近似算法：二边逐次修正法：(1)任取初始H圈:C0=v1,v2,…,vi,,…,vj,…,vn,v1(2)对所有的i,j，1i+1jn,若w(vi,vj)+w(vi+1,vj+1)w(vi,vi+1)+w(vj,vj+1)则在C0中删去边(vi,vi+1)和(vj,vj+1)而加入边(vi,vj)和(vi+1,vj+1)，形成新的H圈C，即C=v1,v2,…,vi,,vj,vj-1,…,vi+1,vj+1,…,vn,v1(3)对C重复步骤(2)，直到条件不满足为止，最后得到的C即为所求．例对以下完备图，用二边逐次修正法求较优H圈．返回定理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.v1v2v3v4v5v6v7v8v9v10v11v1224553646465447938AV12v104v95v8V26v114v126v7554477V39v43v58v6B445544779938864636C446466654444793836D594444332455364666642例4.设G是分划为X,Y的二分图,且,XY则G一定不是哈密顿图.(利用分支数反证)例5.设简单图G=V,E21,,2,nVnEmmC则G是哈密顿图.证明：G中的任意两点u,v，其度数分别为d(u),d(v)对于图G-{u,v}都有m-d(u)-d(v)=(n-2)(n-3)/2又因为m=Cn-12+2d(u)+d(v)=(n-1)(n-2)/2+2-(n-2)(n-3)/2=n-2+2=n由定理1可得G是哈密顿图。