《第四章-欧拉图与哈密尔顿图-3论及其应用课件.ppt》由会员分享，可在线阅读，更多相关《第四章-欧拉图与哈密尔顿图-3论及其应用课件.ppt（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Email:图论及其应用图论及其应用任课教师：杨春任课教师：杨春1本次课主要内容本次课主要内容(一一)、度极大非哈密尔顿图、度极大非哈密尔顿图(二二)、TSP问题问题度极大非哈密尔顿图与度极大非哈密尔顿图与TSP问题问题2 1、定义、定义(一一)、度极大非哈密尔顿图、度极大非哈密尔顿图 定义定义1 图图G称为度极大非称为度极大非H图，如果它的度不弱图，如果它的度不弱于其它非于其它非H图。图。2、C m,n图图 定义定义2 对于对于1 m n/2,C m n/2,C m,nm,n图定义为：图定义为：例如，作出例如，作出C1,5与与C2,53 3、Cm,n的性质的性质C1,5C2,5 引理引理1
2、对于对于1mn/2m|S|=m,(G-S)=m+1|S|=m,所以，所以，由由H H图的性质知，图的性质知，G G是非是非H H图。图。4、度极大非度极大非H图的特征图的特征4 (2)定理的条件是充分条件而非必要条件。定理的条件是充分条件而非必要条件。例如：当例如：当n=5时，其度极大非时，其度极大非H图族是：图族是：C1,5与与C2,5C1,5C2,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图。图。6 (3)如果如果
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 推论推论 设设G是是n阶单图。若阶单图。若n33且且7 则则G是是H图；并且，具有图；并且，具有n个顶点个顶点 条边条边的非的非H图只有图只有C1,n以及以及C2,5.证明证明:(1)先证明先证明G是是H图。图。若不然，由定理若不然，由定理1，G度弱于某个度弱于某个Cm,n,于是有：于是有：这与条件矛盾！
4、所以这与条件矛盾！所以G是是H图。图。8 但是，在下图中，尽管但是，在下图中，尽管C2,7+uv的边数不满足推的边数不满足推论不等式，可它是论不等式，可它是H图。图。C1,7+eeuvC2,7+uv10 例例1 设设G是度序列为是度序列为(d1,d2,dn)的非平凡单图，且的非平凡单图，且d1d2dn。证明：若。证明：若G不存在小于不存在小于(n+1)/2的正的正整数整数m，使得：，使得：dmm且且dn-m+1|S|=13.-S)|S|=13.故，老鼠最后不能到达中心点。故，老鼠最后不能到达中心点。13 (2)下面下面构造一个构造一个H H连通图连通图G,G,使得：使得：n为偶数时为偶数时n为
5、奇数时为奇数时15 例例4 写出下列问题的一个好算法：写出下列问题的一个好算法：(1)构作一个图的闭包；构作一个图的闭包；(2)若某图的闭包是完全图，求该图的若某图的闭包是完全图，求该图的H圈。圈。解：解：(1)构作一个图的闭包。构作一个图的闭包。根据图的闭包定义，构作一个图的闭包，可以通过不断在根据图的闭包定义，构作一个图的闭包，可以通过不断在度和大于等于度和大于等于n的非邻接顶点对间添边得到。据此设计算法如的非邻接顶点对间添边得到。据此设计算法如下：下：图的闭包算法：图的闭包算法：1)令令G0=G,k=0;2)在在Gk中求顶点中求顶点u0与与v0，使得：，使得：16 方法：采用边交换技术把
6、闭包中的一个方法：采用边交换技术把闭包中的一个H圈逐步转圈逐步转化为化为G的一个的一个H圈。圈。(2)若某图的闭包是完全图，求该图的若某图的闭包是完全图，求该图的H圈。圈。该方法是基于如下一个事实：该方法是基于如下一个事实：在闭包算法中，在闭包算法中，Gk+1=Gk+u0v0,u0与与v0在在Gk中不邻接，中不邻接，且度和大于等于且度和大于等于n.如果在如果在Gk+1中有中有H圈圈Ck+1如下：如下：u0v0v1vivi+1vn-3vn-2Ck+118 我们有如下断言：我们有如下断言：u0v0v1vivi+1vn-3vn-2Ck+1 若不然，设若不然，设dGk(u0)=r,那么在那么在Gk中，
7、至少有中，至少有r个顶点与个顶点与v0不邻接，则不邻接，则dGk(v0)(n-1)-r n-r，这样与，这样与u0，v0在在Gk中度和大于等于中度和大于等于n矛盾！矛盾！上面结论表明：可以从上面结论表明：可以从Ck+1中去掉中去掉u0v0而得到新的而得到新的H圈，圈，实现实现H圈的边交换。圈的边交换。由此，我们设计算法如下：由此，我们设计算法如下：19 1)在闭包构造中，将加入的边依加入次序记为在闭包构造中，将加入的边依加入次序记为ei(1iN),iN),这里，这里，N=n(n-1)/2-m(G).N=n(n-1)/2-m(G).在在G GN N中任意取出一个中任意取出一个H H圈圈C CN
8、N,令令k=N;k=N;2)若若ek不在不在Ck中，令中，令Gk-1=Gk-ek,Ck-1=Ck;否则转否则转3);3)设设ek=u0v0 Ck,令令Gk-1=Gk-ek;求求Ck中两个相邻点中两个相邻点u与与v使使得得u0,v0,u,v依序排列在依序排列在Ck上，且有：上，且有：uu0,vv0 E(Gk-1),令：令：4)若若k=1,转转5)；否则，令；否则，令k=k-1,转转2);5)停止。停止。C0为为G的的H圈。圈。复杂性分析：复杂性分析：一共进行一共进行N次循环，每次循环运算量主要在次循环，每次循环运算量主要在3),找满足要求的找满足要求的邻接顶点邻接顶点u与与v,至多至多n-3次判
9、断。所以总运算量：次判断。所以总运算量：N(n-3),属于属于好算法。好算法。20(二二)、TSP问题问题 TSP问题即旅行售货员问题，是应用图论中典型问题之问题即旅行售货员问题，是应用图论中典型问题之一。问题提法为：一售货员要到若干城市去售货，每座城一。问题提法为：一售货员要到若干城市去售货，每座城市只经历一次，问如何安排行走路线，使其行走的总路程市只经历一次，问如何安排行走路线，使其行走的总路程最短。最短。已经使用过的近似算法很多，如遗传算法、最邻近算已经使用过的近似算法很多，如遗传算法、最邻近算法、最近插值法、贪婪算法和边交换技术等。法、最近插值法、贪婪算法和边交换技术等。在赋权图中求最
10、小在赋权图中求最小H圈是圈是NP难问题。理论上也已经难问题。理论上也已经证明：不存在多项式时间近似算法，使相对误差小于或等证明：不存在多项式时间近似算法，使相对误差小于或等于某个固定的常数于某个固定的常数,即便是即便是=1000也是如此。也是如此。下面介绍边交换技术。下面介绍边交换技术。21 1、边交换技术、边交换技术 (1)、在赋权完全图中取一个初始、在赋权完全图中取一个初始H圈圈C=v1v2,vnv1；(2)、如果存在下图中红色边，、如果存在下图中红色边，且且w(vivi+1)+w(vjvj+1)w(vivj)+w(vi+1vj+1),则把则把C修改为：修改为：C1=v1v2,vivjvi
11、+1vj+1,vnv1v1v2viVi+1vjvj+1vn初始初始H圈圈Cv1v2viVi+1vjvj+1vn22 解：取初始圈为：解：取初始圈为：132156603651TPePaNYMCL278132170603651TPePaNYMCL27824132170353651TPePaNYMCL251132170356856TPePaNYMCL251 于是，求出一个近似最优解为：于是，求出一个近似最优解为：W(H)=192 注：为了得到进一步的优解，可以从几个不同的初始圈注：为了得到进一步的优解，可以从几个不同的初始圈开始，通过边交换技术得到几个近似最优解，然后从中选取开始，通过边交换技术得到
12、几个近似最优解，然后从中选取一个近似解。一个近似解。25 2、最优、最优H圈的下界圈的下界 可以通过如下方法求出最优可以通过如下方法求出最优H圈的一个下界：圈的一个下界：(1)在在G中删掉一点中删掉一点v(任意的任意的)得图得图G1;(2)在图在图G1中求出一棵最小生成树中求出一棵最小生成树T;(3)在在v的关联边中选出两条权值最小者的关联边中选出两条权值最小者e1与与e2.若若H是是G的最优圈，则：的最优圈，则：26 例例6 设设G是赋权完全图，对所有的是赋权完全图，对所有的x,y,z V(G),满足三满足三角不等式：角不等式：W(x y)+W(y z)W(xz)W(xz).证明：证明：G中
13、最优圈的中最优圈的权最多是权最多是2W(T)，这里，这里T是是G中一棵最小生成树。中一棵最小生成树。证明：设证明：设T是是G的一棵最小生成树，将的一棵最小生成树，将T的每条边添上的每条边添上一条平行边得图一条平行边得图T1,显然显然T1是欧拉图。是欧拉图。v1v2v3v4v5v6Tv1v2v3v4v5v6T1 设设Q是是T1的一个欧拉环游：的一个欧拉环游：Q=v1v2.vkv128 则：则：W(T1)=W(Q)=2W(T)现在，从现在，从Q的第三点开始，删掉与前面的重复顶点，得的第三点开始，删掉与前面的重复顶点，得到到G的顶点的一个排列的顶点的一个排列。由于由于G是完全图，所以该排列对应是完全图，所以该排列对应G的一个的一个H圈。圈。在在中任意一条边中任意一条边(u,v),(u,v),在在T T中有一条唯一的中有一条唯一的(u,v)(u,v)路路P,P,而该路正好是在而该路正好是在Q Q中的中的u u与与v v间的部分。间的部分。由三角不等式知：由三角不等式知：W(uv)W(P)W(P)所以：所以：W()W(Q)=2W(T)W(Q)=2W(T)即最优圈即最优圈H的权值满足：的权值满足：W(H)W()W(Q)=2W(T)29Thank You!31