图论课件-度极大非哈密尔顿图与TSP问题.ppt

1,图论及其应用,应用数学学院,2,本次课主要内容,(一)、度极大非哈密尔顿图,(二)、TSP问题,度极大非哈密尔顿图与TSP问题,3,1、定义,(一)、度极大非哈密尔顿图,定义1图G称为度极大非H图，如果它的度不弱于其它非H图。,2、Cm,n图,定义2对于1mn/2,Cm,n图定义为：,例如，作出C1,5与C2,5,4,3、Cm,n的性质,引理1对于1m|S|=m,所以，由H图的性质知，G是非H图。,4、度极大非H图的特征,5,定理1(Chvtal,1972),若G是n3的非H单图，则G度弱于某个Cm,n图。,证明：设G是度序列为(d1,d2,dn)的非H单图，且d1d2dn,n3。,由度序列判定法：存在mn/2,使得dmm,且dn-mn-m.于是，G的度序列必弱于如下序列：,而上面序列正好是图Cm,n的度序列。,注：(1)定理1刻画了非H单图的特征：Cm,n图族中每个图都是某个n阶非H单图的极图。,6,(2)定理的条件是充分条件而非必要条件。,例如：当n=5时，其度极大非H图族是：C1,5与C2,5,C1,5的度序列是：(1,3,3,3,4),C2,5的度序列是(2,2,2,4,4)。,而5阶圈C5的度序列是:(2,2,2,2,2),它度弱于C2,5,但是C5是H图。,7,(3)如果n阶单图G度优于于所有的Cm,n图族，则G是H图。,G的度序列是(2,3,3,4,4),优于C1,5的度序列(1,3,3,3,4)和C2,5的度序列(2,2,2,4,4)。所以可以断定G是H图。,例如：,推论设G是n阶单图。若n3且,8,则G是H图；并且，具有n个顶点条边的非H图只有C1,n以及C2,5.,证明:(1)先证明G是H图。,若不然，由定理1，G度弱于某个Cm,n,于是有：,这与条件矛盾！所以G是H图。,9,(2)对于C1,n,有：,除此之外，只有当m=2且n=5时有：,这就证明了(2)。,注：推论的条件是充分而非必要的。,例如：在C1,7的任意不相邻顶点间连一边后可得H图：,10,但是，在下图中，尽管C2,7+uv的边数不满足推论不等式，可它是H图。,11,例1设G是度序列为(d1,d2,dn)的非平凡单图，且d1d2dn。证明：若G不存在小于(n+1)/2的正整数m，使得：dmm且dn-m+1|S|=13.,故，老鼠最后不能到达中心点。,14,例3对m条边的n阶图G，若G的每两个顶点都由一条H路连接着，称G是哈密尔顿连通图。,(1)证明：若G是H连通图且n4,则,(2)对于n4,构造一个H连通图G,使得：,证明：(1)可以证明，(G)3.于是有：,事实上,若存在v，有d(v)=2,设v1与v2分别是v的两个邻接点，则由n4知，不存在v1为起点v2为终点的H路，与条件矛盾。,15,(2)下面构造一个H连通图G,使得：,16,例4写出下列问题的一个好算法：,(1)构作一个图的闭包；,(2)若某图的闭包是完全图，求该图的H圈。,解：(1)构作一个图的闭包。,根据图的闭包定义，构作一个图的闭包，可以通过不断在度和大于等于n的非邻接顶点对间添边得到。据此设计算法如下：,图的闭包算法：,1)令G0=G,k=0;,2)在Gk中求顶点u0与v0，使得：,17,3)如果，则转4);否则，停止，此时得到G的闭包；,4)令Gk+1=Gk+u0v0,k=k+1,转2).,复杂性分析：在第k次循环里，找到点u0与v0，要做如下运算:(a)找出所有不邻接点对-需要n(n-1)/2次比较运算；(b)计算不邻接点对度和-需要做n(n-1)/2-m(G)次加法运算;(c),选出度和最大的不邻接点对-需要n(n-1)/2-m(G)次比较运算。所以，总运算量为：,所以，上面的闭包算法是好算法。,18,方法：采用边交换技术把闭包中的一个H圈逐步转化为G的一个H圈。,(2)若某图的闭包是完全图，求该图的H圈。,该方法是基于如下一个事实：,在闭包算法中，Gk+1=Gk+u0v0,u0与v0在Gk中不邻接，且度和大于等于n.,如果在Gk+1中有H圈Ck+1如下：,19,我们有如下断言：,若不然，设dGk(u0)=r,那么在Gk中，至少有r个顶点与v0不邻接，则dGk(v0)(n-1)-rn-r，这样与u0，v0在Gk中度和大于等于n矛盾！,上面结论表明：可以从Ck+1中去掉u0v0而得到新的H圈，实现H圈的边交换。,由此，我们设计算法如下：,20,1)在闭包构造中，将加入的边依加入次序记为ei(1iN),这里，N=n(n-1)/2-m(G).在GN中任意取出一个H圈CN,令k=N;,2)若ek不在Ck中，令Gk-1=Gk-ek,Ck-1=Ck;否则转3);,3)设ek=u0v0Ck,令Gk-1=Gk-ek;求Ck中两个相邻点u与v使得u0,v0,u,v依序排列在Ck上，且有：uu0,vv0E(Gk-1),令：,4)若k=1,转5)；否则，令k=k-1,转2);,5)停止。C0为G的H圈。,复杂性分析：,一共进行N次循环，每次循环运算量主要在3),找满足要求的邻接顶点u与v,至多n-3次判断。所以总运算量：N(n-3),属于好算法。,21,(二)、TSP问题,TSP问题即旅行售货员问题，是应用图论中典型问题之一。问题提法为：一售货员要到若干城市去售货，每座城市只经历一次，问如何安排行走路线，使其行走的总路程最短。,已经使用过的近似算法很多，如遗传算法、最邻近算法、最近插值法、贪婪算法和边交换技术等。,在赋权图中求最小H圈是NP难问题。理论上也已经证明：不存在多项式时间近似算法，使相对误差小于或等于某个固定的常数,即便是=1000也是如此。,下面介绍边交换技术。,22,1、边交换技术,(1)、在赋权完全图中取一个初始H圈C=v1v2,vnv1；,(2)、如果存在下图中红色边，且w(vivi+1)+w(vjvj+1)w(vivj)+w(vi+1vj+1),则把C修改为：C1=v1v2,vivjvi+1vj+1,vnv1,23,例5采用边交换技术求下赋权完全图的一个最优H圈。,24,解：取初始圈为：,25,于是，求出一个近似最优解为：W(H)=192,注：为了得到进一步的优解，可以从几个不同的初始圈开始，通过边交换技术得到几个近似最优解，然后从中选取一个近似解。,26,2、最优H圈的下界,可以通过如下方法求出最优H圈的一个下界：,(1)在G中删掉一点v(任意的)得图G1;,(2)在图G1中求出一棵最小生成树T;,(3)在v的关联边中选出两条权值最小者e1与e2.,若H是G的最优圈，则：,27,例如，估计例5中最优H圈的下界,解：在G中删掉点NY,求得G-NY的一棵最优生成树为：,所以，W(H)122+35+21=178.,28,例6设G是赋权完全图，对所有的x,y,zV(G),满足三角不等式：W(xy)+W(yz)W(xz).证明：G中最优圈的权最多是2W(T)，这里T是G中一棵最小生成树。,证明：设T是G的一棵最小生成树，将T的每条边添上一条平行边得图T1,显然T1是欧拉图。,设Q是T1的一个欧拉环游：Q=v1v2.vkv1,29,则：W(T1)=W(Q)=2W(T),现在，从Q的第三点开始，删掉与前面的重复顶点，得到G的顶点的一个排列。,由于G是完全图，所以该排列对应G的一个H圈。,在中任意一条边(u,v),在T中有一条唯一的(u,v)路P,而该路正好是在Q中的u与v间的部分。,由三角不等式知：W(uv)W(P),所以：W()W(Q)=2W(T),即最优圈H的权值满足：W(H)W()W(Q)=2W(T),30,作业,P97-99习题4：13,14，17,31,ThankYou!,