图论及其应用(14)

1、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图定义为：图定义为：,2()m nmmnmCKKK 例如，作出例如，作出C1,5与与C2,53 3、Cm,n的性质的性质1K1K3KC1,52K2K1KC2,5 引理引理1 对

2、于对于1mn/2m|S|=m,(G-S)=m+1|S|=m,所以，所以，由由H H图的性质知，图的性质知，G G是非是非H H图。图。 4、度极大非度极大非H图的特征图的特征4 定理定理1 (Chvtal,1972) 若若G是是n33的非的非H H单图，则单图，则G G度弱于某个度弱于某个C Cm,nm,n图。图。 证明：证明： 设设G是度序列为是度序列为 (d1,d2,dn)的非的非H单图，单图，且且d1d2dn,n33。 由度序列判定法：存在由度序列判定法：存在mn/2,使得使得dmm,m,且且d dn-mn-mn-m.n-m.于是，于是，G G的度序列必弱于如下序列：的度序列必弱于如下序

3、列：2( ,.,1,1,.,1,1,1,.,1mnmmm mm nmnmnmnnn 而上面序列正好是图而上面序列正好是图Cm,n的度序列。的度序列。 注注： (1) 定理定理1刻画了非刻画了非H单图的特征：单图的特征：Cm,n图族中图族中每个图都是某个每个图都是某个n阶非阶非H单图的极图。单图的极图。5 (2) 定理的条件是充分条件而非必要条件。定理的条件是充分条件而非必要条件。 例如：当例如：当n=5时，其度极大非时，其度极大非H图族是：图族是：C1,5与与C2,51K1K3KC1,52K2K1KC2,5 C1,5的度序列是：的度序列是：(1,3,3,3,4), C2,5的度序列是的度序列是

4、(2,2,2,4,4)。 而而5阶圈阶圈C5的度序列是的度序列是: (2,2,2,2,2),它度弱于它度弱于C2,5,但是但是C5是是H图。图。6 (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且且1()12nE G7 则则G是是H图；并且，具有图；并且，具有n个顶点个顶点 条边

5、条边的非的非H图只有图只有C1,n以及以及C2,5.112n 证明证明: (1) 先证明先证明G是是H图。图。 若不然，由定理若不然，由定理1，G度弱于某个度弱于某个Cm,n,于是有：于是有：2,1()()(2)(1)(1)2111(1)(2)(1)(21)2211.2m nE GE Cmnmnmm mnmmmnmn 这与条件矛盾！所以这与条件矛盾！所以G是是H图。图。8 (2) 对于对于C1,n,有：有： 除此之外，只有当除此之外，只有当m=2且且n=5时有：时有：1,1()()1.2nnE GE C 这就证明了这就证明了(2)。,1()()1.2m nnE GE C 注：推论的条件是充分而

6、非必要的。注：推论的条件是充分而非必要的。 例如：在例如：在C1,7的任意不相邻顶点间连一边后可得的任意不相邻顶点间连一边后可得H图：图：9 但是，在下图中，尽管但是，在下图中，尽管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. 故，老鼠最后不能到达中心点。故，老鼠最后不能到达中

7、心点。13 例例3 对对m条边的条边的n阶图阶图G，若，若G的每两个顶点都由的每两个顶点都由一条一条H路连接着，称路连接着，称G是哈密尔顿连通图。是哈密尔顿连通图。 (1) 证明：若证明：若G是是H连通图且连通图且n4,4,则则1(31)2mn (2) 对于对于n4,4,构造一个构造一个H H连通图连通图G,G,使得：使得：1(31)2mn证明：证明： (1) 可以证明，可以证明，(G)3.(G)3.于是有：于是有：1(31)2mn事实上事实上,若存在若存在v，有，有d(v)=2,设设v1与与v2分别是分别是v的两个的两个邻接点，则由邻接点，则由n44知，不存在知，不存在v v1 1为起点为起

8、点v v2 2为终点的为终点的H H路，与条件矛盾。路，与条件矛盾。14 (2) 下面下面构造一个构造一个H H连通图连通图G,G,使得：使得：1(31)2mnn为偶数时为偶数时n为奇数时为奇数时15 例例4 写出下列问题的一个好算法：写出下列问题的一个好算法： (1) 构作一个图的闭包；构作一个图的闭包； (2) 若某图的闭包是完全图，求该图的若某图的闭包是完全图，求该图的H圈。圈。 解：解：(1) 构作一个图的闭包。构作一个图的闭包。 根据图的闭包定义，构作一个图的闭包，可以通过不断在根据图的闭包定义，构作一个图的闭包，可以通过不断在度和大于等于度和大于等于n的非邻接顶点对间添边得到。据此

9、设计算法的非邻接顶点对间添边得到。据此设计算法如下：如下： 图的闭包算法：图的闭包算法： 1) 令令G0=G ,k=0; 2) 在在Gk中求顶点中求顶点u0与与v0，使得：，使得：00()()m ax()( )()kkkkGGGGkdudvdudvuvE G16 3) 如果如果 ，则转，则转4);否则，停止，此时否则，停止，此时得到得到G的闭包；的闭包；00()()kkGGdudvn 4) 令令Gk+1=Gk+u0v0, k=k+1,转转2). 复杂性分析：在第复杂性分析：在第k次循环里，找到点次循环里，找到点u0与与v0，要做如下运，要做如下运算算: (a) 找出所有不邻接点对找出所有不邻接

10、点对-需要需要n(n-1)/2次比较运算；次比较运算；(b) 计算不邻接点对度和计算不邻接点对度和-需要做需要做n(n-1)/2-m(G)次加法运算次加法运算;(c ),选出度和最大的不邻接点对选出度和最大的不邻接点对-需要需要n(n-1)/2-m(G)次比较运算。次比较运算。所以，总运算量为：所以，总运算量为：211(1)2(1)()()22n nn nmGOn 所以，上面的闭包算法是好算法。所以，上面的闭包算法是好算法。17 方法：采用边交换技术把闭包中的一个方法：采用边交换技术把闭包中的一个H圈逐步转圈逐步转化为化为G的一个的一个H圈。圈。 (2) 若某图的闭包是完全图，求该图的若某图的

11、闭包是完全图，求该图的H圈。圈。 该方法是基于如下一个事实：该方法是基于如下一个事实： 在闭包算法中，在闭包算法中，Gk+1=Gk+u0v0, u0与与v0在在Gk中不邻接，中不邻接，且度和大于等于且度和大于等于n. 如果在如果在Gk+1中有中有H圈圈Ck+1如下：如下：100120(,.,)knCu v vvuu0v0v1vivi+1vn-3vn-2Ck+118 我们有如下断言：我们有如下断言：u0v0v1vivi+1vn-3vn-2Ck+111001,()kiiiikCv vu v v vE G在上，使得 若不然，设若不然，设dGk(u0)=r,那么在那么在Gk中，至少有中，至少有r个顶点

12、与个顶点与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 N, ,令令k=N

13、;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),令：令： 10000,kkCCu v uvuu vv 4) 若若k=1,转转5)；否则，令；否则，令k=k-1,转转2); 5) 停止。停止。C0为为G的的H圈。圈。 复杂性分析：复杂性分析： 一共进行一共进行N次循环，每次循环运算量主要在次循环，每次循环运算量主要在3),找满足要求

14、找满足要求的邻接顶点的邻接顶点u与与v,至多至多n-3次判断。所以总运算量：次判断。所以总运算量：N(n-3),属属于好算法。于好算法。20(二二)、TSP问题问题 TSP问题即旅行售货员问题，是应用图论中典型问题问题即旅行售货员问题，是应用图论中典型问题之一。问题提法为：一售货员要到若干城市去售货，每座之一。问题提法为：一售货员要到若干城市去售货，每座城市只经历一次，问如何安排行走路线，使其行走的总路城市只经历一次，问如何安排行走路线，使其行走的总路程最短。程最短。 已经使用过的近似算法很多，如遗传算法、最邻近算已经使用过的近似算法很多，如遗传算法、最邻近算法、最近插值法、贪婪算法和边交换技

15、术等。法、最近插值法、贪婪算法和边交换技术等。 在赋权图中求最小在赋权图中求最小H圈是圈是NP难问题。理论上也已经难问题。理论上也已经证明：不存在多项式时间近似算法，使相对误差小于或等证明：不存在多项式时间近似算法，使相对误差小于或等于某个固定的常数于某个固定的常数, ,即便是即便是=1000也是如此。也是如此。 下面介绍边交换技术。下面介绍边交换技术。21 1、边交换技术、边交换技术 (1)、在赋权完全图中取一个初始、在赋权完全图中取一个初始H圈圈C=v1v2,vnv1； (2)、如果存在下图中红色边，、如果存在下图中红色边，且且w(vivi+1)+ w(vjvj+1)w(vivj)+ w(

16、vi+1vj+1),则把则把C修改为：修改为： C1=v1v2,vivjvi+1vj+1,vnv1v1v2viVi+1vjvj+1vn初始初始H圈圈Cv1v2viVi+1vjvj+1vn22 例例5 采用边交换技术求下赋权完全图的一个最优采用边交换技术求下赋权完全图的一个最优H圈。圈。13221705651607835365168576861TPePaNYMCL23 解：取初始圈为：解：取初始圈为：132156603651TPePaNYMCL278132170603651TPePaNYMCL27824132170353651TPePaNYMCL251132170356856TPePaNYMCL

17、251 于是，求出一个近似最优解为：于是，求出一个近似最优解为：W(H) =192 注：为了得到进一步的优解，可以从几个不同的初始圈注：为了得到进一步的优解，可以从几个不同的初始圈开始，通过边交换技术得到几个近似最优解，然后从中选取开始，通过边交换技术得到几个近似最优解，然后从中选取一个近似解。一个近似解。25 2、最优、最优H圈的下界圈的下界 可以通过如下方法求出最优可以通过如下方法求出最优H圈的一个下界：圈的一个下界： (1) 在在G中删掉一点中删掉一点v(任意的任意的)得图得图G1; (2) 在图在图G1中求出一棵最小生成树中求出一棵最小生成树T; (3) 在在v的关联边中选出两条权值最

18、小者的关联边中选出两条权值最小者e1与与e2. 若若H是是G的最优圈，则：的最优圈，则：12()( )()()W HW TW eW e26 例如，估计例例如，估计例5中最优中最优H圈的下界圈的下界 解：在解：在G中删掉点中删掉点NY,求得求得G-NY的一棵最优生成树为：的一棵最优生成树为：5113MC562PaLPeT3521 所以，所以，W(H)122+35+21=178.122+35+21=178.27 例例6 设设G是赋权完全图，对所有的是赋权完全图，对所有的x, y, z V(G),满足三满足三角不等式：角不等式：W(x y)+ W (y z)W(xz)W(xz) .证明：证明：G中最优圈的中最优圈的权最多是权最多是2W(T)，这里，这里T是是G中一棵最小生成树。中一棵最小生成树。 证明：设证明：设T是是G的一棵最小生成树，将的一棵最小生成树，将T的每条边添上的每条边添上一条平行边得图一条平行边得图T1,显然显然T1是欧拉图。是欧拉图。v1v2v3v4v5v6Tv1v2v3v4v5v6T1 设设Q是是T1的一个欧拉环游：的一个欧拉环游：Q=v1v2.vkv128 则：则：W(T1)=W(Q)=2W(T) 现在，从现在，从Q的第三点开始，删掉与前面的重复顶点，得的第三点开始，删掉与前面的重