（运筹学与控制论专业论文）树上的最大顶点覆盖的算法设计和分析.pdf

摘要 组合优化问题是一门古老而又年轻的学科，在人们的生活中起着非常重要 的作用，本文介绍了一类普通的组合优化问题一顶点覆盖。在我们以前的学习 中碰到只是一种展小顶点覆盖，即在无向图g = ( k e ) 中选择尽可能少的点使 其覆盖所有的边。在本文里我们将讨论另一类顶点覆盖一最大顶点覆盖，即在 无向图g = ( k e ) 中，给定非负整数，k i v l ，在g 中选择k 个点，使其覆盖的 边数尽可能的多。鉴于最大项点覆盖问题也是p h a r d 的，除非p = n p ，否 则我们不可能在多项式时间内找到最优的算法。 在这篇文章里，我们考虑一种特殊的图形一树，针对该图形设计一些近似 算法，并分析其性能。 本文共分为三个章节。 第一章是引言部分，介绍了组合优化和算法的一些概念和基本知识。 第二章主要介绍了我们比较熟悉的最小顶点覆盖问题，关于该问题有一些 著名的结论和成果，我们给了一些介绍。 第三章是本文的主要部分，我们详细讨论了树上的最大顶点覆盖问题，基 于贪婪算法的思想，我们给出了两个算法，第一个算法我们称为凡蚴g r e e d y ， 其近似比为2 ，第二个算法我们称为d y n a m i cg r e e d y ，其近似比为；4 。 关键词：组合优化，贪婪算法，近似算法，近似比 a b s t r a c t c o m b i n a t o r i a lo p t i m i z a t i o ni sa l lo l da n di m p o r t a n ts u b j e c t ，t h a ti sr e l a t e d t oo u rd a l l yl i f e a m o n gt h em a n yc o m b i n a t o r i a lp r o b l e m s ，i nt h i sp a p e r ，w e c o n s i d e rv e r t e xc o v e rp r o b l e 瑚 d i f i e r e n tf r o mt h ew e l lk n o w nm i n i m u mv e r t e xc o v e rp r o b l e m t h a tc o v e r s a l le d g e sw i t ham i n i m u mn u m b e ro fv e r t i c e si nag r a p hg = ( k e ) ，w ed e a l w i t had u a lv e r s i o n ，c a l l e dm & x i i n u l x lv e r t e xc o v e r ，i nw h i c ho n ei 8a s k e dt o 砷出 kv e r t i c e sc o v e r i n ga sm a n ye d g e sa sp o s s i b l e ，w h e r eki sa g i v e i lp o s i n v ei n t e g e r ，ec a l lp r o v et h a tt h em a x i l n u i nv e r t e xc o v e rp r o b l e mi sa l ln p h a r d p r o b l e m ，s ow ec a nn o te x p e c tt of i n da no p t i m a ls o l u t i o ni np o l y n o m i a lt i m e ， u n l e s sp = p i nt h i sp a p e rw ej u s tc o n s i d e ras p e c i a lg r a p h - - t r e e w h i c hi s a ni n t e r e s t i n gp r o b l e m f o ri tw ew i l ld e s i g ns o m ea p p r o x i m a t i o na l g o r i t h n l sa n d a n a l y z et h e i rp e r f o r m a n c e t h e r ea r et h r e ec h a p t e r si nt h i sp a p e r i nc h a p t e r1 ，w ed e s c r i b ew h a ti sc o m b i n a t o r i a lo p t i m i z a t i o na n d 百v e s o m ek n o w l e d g ea b o u th o wt od e s i g na n da n a l y z ea na l g o r i t h m i nc h a p t e r2 w ei n t r o d u c et h em i n i m u mv e r t e xc o v e rp r o b l e ma n dp r e s e n t s o m ek n o w nr e s u l t sa b o u ti t i nc h a p t e r3 w ed e s c r i b et h em a x i m u mv e r t e xc o v e ri n8t r e e a c c o r d i n g t h eg r e e d yi d e aw ed e s i g nt w oa p p r o x i m a t i o na l g o r i t h m st h ea p p r o x i m a t i o n r a t i oo ft h ef i r s ta l g o r i t h m ，c a l l e df u l l yg r e e d y ，i s2 ，w h i l et h er a t i oo ft h e s e c o n d ，c a l l e dd y n a m i cg r e e d y ，i s k e y w o r d s ：c o m b i n a t o r i a lo p t i m i z a t i o n ，g r e e d ya l g o r i t h m ，a p p r o x i m a t i o n a l g o r i t h m 第一章引言 1 1 组合优化简介 组合优化又称离散优化，是一门古老而又年轻的学科。说它古老，是因 为一些组合优化问题有着悠久的历史渊源，著名数学家费马( f e r m a t ) ，欧 拉( e u l e r ) 等都对它迸行过相关的研究。说它年轻，是因为其作为运筹学的一个 独立分支而发展起来还是近几十年的事。二十年世纪后半叶，伴随着工业科技 革命和现在管理科学的发展，特别是计算机技术的突飞猛进和在各行业的广泛 的应用，组合优化已壮大成为一门新兴的学科分支。一些数学家们偶然想到的 问题和方法，现在已经在网络通信、物流管理、交通规划等领域发挥了重要作 用，这是他们当时所不曾想到的，这正预示了此科学的巨大前景。 定义1 1 1 ：组合优化是一个极大( 小) 化问题，它由下述三部分组成： ( 1 ) 实例集合； ( 2 ) 对每一个实例，有一个有穷的可行解集合s f n ； ( 3 ) 目标函数，它对每一个实例j 和每一个可行解o s ( o ，赋以一个有 理数f ( 1 ，盯1 ； 如果该问题是极大( 小) 化问题，则实例珀最优解为这样的一个可行 解矿s ( j ) ，它使得对所有的口s ( z ) ，都有i ( t ，矿) f ( 1 ，口) ( 或者i ( i ，矿) 2 f ( z ，口) ) 。 尽管大部分组合优化问题可转化为整数规划( 或混合整数规划) 问题，但 由于整数规划的求解同样也是困难的，而组合优化有的涵盖甚广，因此人们致 力于研究各个问题的组合结构，试图找到一些好的性质和有针对性的求解方 法。常见的组合优化问题有划分问题( p a r t i t i o n ) 、排序问题( s c h e d u l i n 9 1 、装箱 问题( b i np a c k i n g ) 、背包问题( k n a p s a c k ) 、旅行售货商问题( l a v e l i n gs a l e s m a n p r o b l e m l 、斯坦纳最小树问题( s t e i n e rm i n i m a lt r e e ) 等。网络中的组合优化问 题包括最短路问题( s h o r t e s tp a t h ) 、最小生成树问题( m i n i m a ls p a n n i n gt r e e ) 、 最小点覆盖问题( m i n i m a lv e r t e xc o v e r ) 、最大流问题( m a x - f l o wp r o b l e m ) 、最 小费用流问题( m i n - c o s tf l o wp r o b l e m ) 等。 在这篇文章里我们只对顶点覆盖问题做一介绍。 第一章引言2 1 2算法设计与分析 我们要解决上面的一系列问题。就需要某些工具和某些方法。工具可以是 我们的数学工具，软件包。常用的编程软件等。丽方法就是我们接下来要定义 的“算法”。 算法是指一步步求解问题的通用程序，它是解决问题的程序步骤的一个清 晰的描述。 算法又有很多种，比如“分而治之”、动态规划、回溯、分枝定界、贪婪算 法、启发式算法、近似算法等等。本文中只涉及到贪婪算法和近似算法，所以我 们会给出一些相关的知识。 贪婪算法 贪婪算法通常用来求解晟优化问题，即量的最大化或最小化。在和中 关于贪婪算法有详细的讨论，为了文章的连续性，我们给出其简短的介绍。 贪婪算法采用逐步构造最优解的方法，在每个阶段都作出一个看上去最优 的决策( 在一定的标准下) ，决策一旦作出，就不能在更改。 举例：考虑背包问题，定义如下：给出n 个大小分别为s 1 ，s 2 ，s 。，价值分 别为v l ，砚，的物品，并设背包容量为e ，要找到非负整数。l ，x 2 ，。，使 和 n z t 地 = 1 在约束 巩c z = 1 0 1 ，z 2 ，- - ，z 。为非负整数 下最大。 此题可用下面的贪婪算法方便解出。按价值密度警从大到小排序，不妨设 为蛩笔2 嚣然后将物品按口1 ，v 2 ，的顺序放入包中，直到放不下 为止。 近似算法 对于某些组合优化问题，我们并不能在多项式时间内找剑它的最优解，这 时我们采用近似算法也是一个明智的选择。 第一章引言3 定义1 2 1 ：对于一个组合优化问题7 r ，如果给定任意个实例j ，算法a 总 能找到一个可行解口s ( i ) ，那么称a 为7 r 的一个可行算法；如果进一步这个可 行解的目标值总等于最优解值，则称a 为最优算法。 算法求解问题是需要时间的，通常，算法所用的时间是指算法中所含的加、 减、乘、除、比较等基本运算次数。而算法所用的时间与实例的规模有关，为此 我们用输入长度来刻划实例的规模。所谓实例的输入长度通常是指实例所用的 计算机内存单元数。 定义1 2 2 ：算法的时间复杂性是指关于实例输入长度n 的函数，( n ) ，用来 表示算法的时间需求，对每一个可能的输入长度，它是指在最坏情况下该算法 解此输入长度的实例时所需的时间( 基本运算步数1 ，即对于输入长度相同的所 有实例，把该算法对这些实例的最坏情况作为时间复杂性的度量。 如果存在一个多项式函数p ) ，使得算法的时间复杂性为0 扫( n ) ) ，那么称 该算法为多项式时间算法。 计算复杂性理论兴起于二十世纪六十年代，和算法的设计和分析密切相关。 通过几十年来人们在计算复杂性方面的研究，现今p n p 的猜想以被基本接 受。在此前提下，所谓的n p h a r d 问题就不可能在多项式时间内找到最优算法， 反之即为尸问题。从而，人们在解决方法的有效性、精确性和时间可行性上寻求 平衡。这样，一个自然的想法就是放弃对最优解的寻找，而把研究的重点转向 寻找能在较短时间( 多项式时间) 内手寻到接近于最优解的可行解，成为近似解。 同时我们称这种寻找近似解的算法为近似算法( a p p r o x i m a t i o na l g o r i t h m ) 。 我们给出近似算法的确切定义。 定义1 2 3 ：设7 r 是一个组合优化问题，a 是求解它的一个算法，对于某 个20 ，我们称算法a 是问题“的算法，当且仅当对所有问题7 r 的例子f 。有： l 笔i - 丽o p 广t ( i ) o p 丁( ) 。一 其o a ( i ) 是由算法a 得到的解的目标函数值，o p t ( i ) 是j 的最优解。 算法的分析 我们衡量近似算法的优劣可从两个方面来看，一是算法的时间复杂性， 二是算法得到解值与最优解的接近程度。另外一个在实际中常用的方法是 对n p h a r d 问题加些限制从而得到一些子问题，使其具有多项式时问最优算 第一章引言 4 法。这是因为一个问题是n p h a r d 的，并不能排斥它的一些特殊子闯题是多 项式可解的。 定义1 2 4 ：如果7 r 是一个极大( 小) 化问题，是任意实例。设是a 的一个近 似算法，用c a ( j ) 和c b 刀( j ) 分别表示算法a 解实例j 所得的目标函数值和离线情 况下实例，的最优目标函数值记以( d = c a ，( ( ) j ) ( 或者p ( ，) = g a o 丽p r 产1 ) ，则近 似算法a 的最坏情况界( w o r s t - c a s er a t i o ) 定义为 m ( 丌) = i a p 1p a ( i ) p ，v z 而问题的下界( 1 0 w e rb o u n d ) 定义为 ( 7 r ) = r a ( i ) ip a ( i ) p ，v a 在p n p 的假设下，如果肌( 7 r ) = ( 7 r ) ，则称算法a 对于问题7 r 来讲是晟好可能 的( b e s tp o s s i b l e ) 。 在不引起混淆的前提下，我们通常将上述定义中的c _ ( j ) 、c b 刀( j ) 和m ( 丌) 分 别简记为c i 、c 6 p r 和p a 。 定义1 2 5 - 如果某问题有一系列近似算法 a ) ，对于任意给定的e 0 ， 止 是一个多项式时间算法，而r p a 1 + ，则称它为多项式时间近似方 案( p o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e ) ，简记为p t a s 。 进一步，如果 a 。 的时间复杂性是关于输入长度以及；的某个二元多 项式，则称它为完全多项式近似方案( f u l l yp o l y n o m i a lt i m ea p p r o x i m a t i o n s c h e m e ) ，简记为f f t a s 。 1 3 顶点覆盖问题 定义1 3 1 ：对于无向图g = f ve ) ( y 代表顶点集合，e 代表边的集合) 称 顶点集合k ( y ) 为g 的一个覆盖( c o v e r i n g ) ，如果g 中每边至少有一端在中。 顶点数最少的覆盖称为最小点覆盖( m i n i m u mv e r t i c e sc o v e r ) ，记为霞。 g 的最小点覆盖的元素的个数l k l 称为g 的覆盖数( c o v e m n gn u m b e r ) ，记 为卢( g ) 。 关于顶点覆盖问题，【 - 1 、纠、【4 】，【5 】有详细的讨论，在以后的叙述中我们会 给出其主要的结果。 关于顶点覆盖的求解，有许多算法，其中最有名的是贪婪算法和基于最大 匹配的近似算法，在下文中我们会给出介绍。 第一章引言5 1 4 本文的一些结论 在这篇文章里，我们介绍了顶点覆盖的问题，并在此基础上考虑一种特殊 的顶点覆盖问题一“对偶顶点覆盖”，即给定图g = ( k e ) ，非负整数，在y 中 选择k 个点，使得这k 个点覆盖的边数最多。我们称这个问题为最大顶点覆盖问 题。 一般图上的顶点覆盖问题上p h a r d 的，所以我们不能期望在多项式时 间内找到一个最优算法，但是我们可以退而求其次一寻求一个近似解或者寻找 该问题的子问题的解的结构。这里我们选择后者，研究特殊的图一树上的最大 顶点覆盖。基于贪婪算法的思想我们给出两个求解树的最大顶点覆盖的算法， 并分析这两个算法的优劣。 第二章最小顶点覆盖 2 1引言 最小顶点覆盖就是在一个无向图中寻找最少的点，使其能够覆盖所有的边。 虽然在个图g 中寻找最小顶点覆盖比较困难，但要找到一个近似的最小顶点 覆盖不会太难。首先我们想到的是贪婪算法。 2 2最小顶点覆盖的算法 g r e e d y ： ( 1 ) 设冗= 咖 ( 2 ) 当e ( g ) 毋时 选择一个度最大的点t ，v ( c ) r ，令r = ru 口，然后删除所有与口关联的 边；( 3 ) 继续执行( 2 ) 直到所有的边被覆盖； 这个算法看上去比较简单，也比较合理，但它的近似比是多少呢? 很可惜， 该算法没有常数界。 定理2 2 1 1 3 ：对所有的n 3 的点，存在最小顶点覆盖的实例g 使 得n h ( n 一1 ) + 2 i y ( g ) isn h ( n 一1 ) + n ，g 的顶点中最大的度为1 7 , 1 ，o p t ( g 1 = n ，上面的算法能够找到一个项点覆盖，其点数比最优算法多n 个点，日( n ) = 1 + + 1 + - r + ；。 证明：i g ：p n 23 和i 札，定义以= 。l 刊，并且： ，= 2 。 v ( v 。) = a t ，一，n a ：一- ，b l ，- - - ，6 n ，c 1 ，c r i ) n 一1 ： e ( e 。) = ( 瓯，q ) ：i = 1 ，一，礼) uuu ( ，6 k ) 1 = 2 卢 1 + l ( j a 1 一t ) i + 1 k ( j a 1 ) t ) 注意到i y ( g ) 1 = 2 n + a ：一1 ，a ：一1 n h ( n 一1 ) 一n ，并且a ：一1 n h ( n 一1 ) 一 竹一( n 一2 ) 。 第二章最小顶点覆盖 7 如果我们对g k 应用我们的算法，首先会选择点。禽一- ( 因为它的度晟大) ， 然后选择点。船- 1 _ 1 ，o 栅一一2 ，a l 。然后，剩下n 个不相交的边，则还需要n 个 点来覆盖他们。因此我们的算法所形成的点覆盖包含a ：- 1 个点。而最优点覆盖 只包括点b l ，5 2 ，k ，规模为n 。 下面的图形展示了g 6 的情况： 基于最大匹配，下面介绍一个优于贪婪算法的算法。 a p p r o z - v e r t e z - c o v e v ( g ) 3 1 1 c p 西； 2 f e ( g ) ； 3 w h i l e f ； 4 d ol e t ( u ，v ) b ea na r b i t r a r ye d g eo fe 7 ； 5 。c p c u ( “，”) ； 6 r e m o v ef r o mf e v e r ye d g ei n c i d e n tt oe i t h e r 缸o r ： 7r e t u r ne ： 下面是a p p r o x v e r t e x - c o v e r 的操作过程( 相关图形在下一页) ： a ) 具有7 个顶点和8 条边的输入图g ； b ) 边( 6 ，c ) 是被a p p r o x - v e r t e x - c o v e r 所选择的第一条边，顶点b 和c 被加入 集合g ，它包含了正被构造的顶点覆盖，边a ，6 ) 、( c ，e ) 和( c ，d ) 被删除，因为现 在它们由c 中的某个顶点覆盖； c ) 边( e ，) 被选中，顶点e 和，被加入到g 中； d ) 边( d ，g ) 被选中，顶点d 和9 被加入到e 中； e 1 集合c 是a p p r o z v e r t e x - c o v e r 产生的顶点覆盖，它包含6 个顶 点b ，c ，d ，e ，g ； 第二章最小顶点覆盖8 ，) 这个问题的最优顶点覆盖仅包含三个顶点6 ，d 和g b c d b c q气 d b q b cd c d 9 2暑 ， 多 ae fg e 19 定理：a 卯r o x o 垤疗e p c b 口e r 是一个多项式时间的近似比为2 的算法。 证明： 由算法的执行过程知，该算法的运行时间为o ( v + e 1 ，为多项式。下面我 们证明它的近似比为2 。 由a p p w x - 娩疗e d c b 口e r 返回的顶点集合e 是一个顶点覆盖，因为这个算法 会一直循环到e q 中的每条边都被g 中的某个顶点覆盖为止。 为了说明a p p x - 垤n e e r 所返回的顶点覆盖的点数为最优覆盖的两 倍，设a 表示在a p p r o x - 耽庀e p c b 口e r 的第4 行选出的边，任意一个顶点覆盖( 尤 其是最优覆盖口) 都必须包含a 中每条边的至少一个端点。又因为a 中没有两 条边具有共同的端点，因为一旦一条边在第4 行中被选出后，在第6 行中就将 所有与其端点关联的边从f 中去掉。所以，a 中不会有两条边由g 的同一个 第二章晟小顶点覆盖9 顶点覆盖，于是最优顶点覆盖的规模有着如下的下界： l c + j l a l 第4 行的每一次执行都会挑选出一条边，其两个端点都不在g 中，因此，所返 回的顶点覆盖的规模上界( 实际上，是一个上确界) 为： 综合以上两式有： 从而定理得证。 c i = 2 1 a i c i 一2 1 a l 2 1 c + 第三章最大顶点覆盖 最大顶点覆盖的一般性描述为：给定非负整数k ，在无向图g = ( ve ) 中选 择个点，使得这个点覆盖尽可能多的边。关于该问题， s n 了一种半正定规 划的方法，在此我们将考虑近似算法。 3 1 最大顶点覆盖问题的困难性分析 定理3 1 1 ：虽大顶点覆盖是n p h a r d 的。 证明：我们可以通过反证法来证明，假设最大顶点覆盖问题是p 问题，则我 们可阻令k 分别为1 、2 、n ，从中我们可以得到数m ，当k = m 恰好覆盖所有 的点，且m 是最小的覆盖所有点的数，这恰好是最小顶点覆盖所用的点数，这说 明了最小顶点覆盖是p 问题，与展小顶点覆盖是p c o m p l e t e f 题矛盾- 因此，我们不可能期望在多项式时间内找到该问题的最优解，除非p = p 。在此我们只考虑一种特殊的情况一树上的最大顶点覆盖问题。 在给出该问题的算法之前，我们先给出几个引理，它们对我们以后的分析 起着关键的作用。 引理3 1 2 ：给定树g = ( k e ) n i e 整数k ，任意的算法a 在g 中选挥k 个点， 假设这k 个点分别为v 1 ，y 2 ，并且假设它们的度分别为d ( v 1 ) ，d ( v 2 ) ，d ( 巩) ， 定义i a i 为算法覆盖的边数，则有： a i2d ( 口1 ) + d ( 也) + + d ( v k ) 一( k 一1 ) 证明： 定义边集d 为由点”1 ，v 2 ，v k 导出子图的边集，贝i j d e p 的边数为：l d i k l 。 定义边集d 为除了d 以外的所有与 l ，v 2 ，v k i t 关联的边组成的集合，其 所包含的边数为l d 小 注意到： 2 t d f + i = d ( 口1 ) + d ( v 2 ) + - ，+ d ( v k ) 第三章最大瑷点覆盖 则有： a j = j d i + l d j = 2 1 d i + 1 d 7 卜i d i = d ( v 1 ) + d ( 砚) + + d ( v k ) 一i d i d ( v 1 ) + d ( v 2 ) + + d ( v k ) 一 一1 ) 引理得证。 引理3 1 3 ：若树g = ( v e ) q p 的k 个点导出的子图是由m 个连通分枝组成， 定义这女个点分别为： 0 1 ，忱，一，讥，它们的度分别为：d ( 1 ) ，d ( 抛) ，d ( ) ，则 对任意的算法a ，其所覆盖的边数f a f 为： a j d ( v 1 ) + d ( v 2 ) + + d ( v k ) 一 一m ) 证明： 因为这k 个点的生成子图足一个森林，则对每一个分枝来说，是一棵树。假 设对于分枝t ( t m ) ，其e h g i v m 地，”概y 组成，而根据引理3 1 ，2 ，算法 选择的分枝t 所覆盖的边数i a l 为： 1 t s m ，且有 a t i d ( v t l ) + d ( v e ) + + d ( u 衄) 一( a t 一1 ) 1 + 啦+ - + 凸m = 七 因此算法所覆盖的总边数为： i a 【= i a l f + 1 4 2 l + + i d ( v n ) + d ( v 1 2 ) + + d ( v 2 1 ) + d ( v 2 2 ) + + + d ( v l 。) 一( 6 1 1 ) + d ( v 2 d 2 ) 一( 6 2 1 ) 十d ( 珥。1 ) + d ( 坼帕) + + d ( q 瑚h ) 一( a m 1 ) = ( d ( v 1 ) + d ( v 1 ) + + d ( 巩) ) 一( a l + 啦+ + ) + m = d ( v 1 ) + d ( 地) + + d ( v k ) 一( m ) 第三章最大顶点覆盖 1 2 引理得证。 由引理3 1 3 知，若设计一个好的算法应该尽量使选择的k 个点导出子图的 连通分枝数尽量多。 根据贪婪算法的思想，我们将给出两个近似算法。 3 2 f u l l yg r e e d y 算法 第一个近似算法，我们称之) b f u l l yg r e e d y ，其思想如下： f u l l yg r e e d y ( f g ) 将树的点按度从大到小排序，设为d ( v 1 ) 2d ( v 2 ) 2 d ( ) ，选择前个 度展大的点口1 ，v 2 ，“。 定义i d p t ( g ) i 为最优解覆盖的边数，简i g n l o p t bi f g ( g ) i n 算法f u u y g r e e d y 覆盖的边数，简记为i f a l 。 定理3 2 1 ：该算法的近似比为2 ，且为紧界。 证明： ( 1 ) 、若d ( v k ) 22 ： l o p t i d ( v 1 ) + d ( v 2 ) + + d ( v k ) 由引理3 1 2 知： i f g l d ( v t ) + d ( v 2 ) + + d ( v k ) 一( k 一1 ) i o p t f ， 笔。d 堕) 一可可3 曩j 丽丽 d ( v 2 ) d ( v k ) d o i ) 2d ( 呓) 2 2d ( u ：) 当删除点巩时，根据d g 的执行过程，有 d ( v k ) d ( v l ) 则 d ( v k ) d ( ”1 7 ) + 1 第三章 最大顶点覆盖 1 5 因为d g 在执行的过程中每次度最大的点只有一个，从而有 d ( v k 一1 ) d ( v k ) d ( v k 一1 ) 2d ( v k ) + 12d ( v l ) + 22d ( v 2 7 ) + 2 d ( v k 一2 ) d ( v k 1 ) + 1 d ( v 2 ) + 3 d ( v 2 ) + 3 d ( v 1 ) 2d ( v k ) + k 从而： 笔。d ( v 1 ) 2e 坠，d ( v i ) + l + 2 + + k = 难，讯”掣 而在原图中u l ，? j 2 ，v k 所覆盖的边数i o p t i 为： i o p t l 笔1 d ( v 。7 ) + i t l i t i 为边割t 的边数， i t i 2 k 一1 所以有： f o p t s 叁1 d ( v i ) + 2 k 一1 口 i d g i ：警1 d ( v i ) 2 叁l d ( 仇，) + 掣 当k23 时，有 i d g l 1 0 p t i 从而可得到矛盾，结论得证。 引理3 2 3 ：若每次删除点后所形成的子图的度虽大的点只有一个， 则d g 和o p t 所选的点一样。 证明： 假设d g 选择的点为： s = 口l ，v 2 ，“) 第三章最大项点覆盖1 6 0 p t 选择的点为： s ，= 口1 7 ，u 2 7 ， 7 并设d ) 为点v 在d g 执行过程中的度。 ( 1 1 女= l l e 1 显然； f 2 ) k = 2 时，由引理3 2 2 可知d g 与o p t 至少有一个点相同 若y 1 与功7 相同，删除们后，度最大的点为y 2 ，但最优解为 口1 7 ，v 2 7 ，说 n d ( v 2 ) 2d ( 观) ，与题设矛盾； 若v 2 与v 2 7 相同，删除点地和与点u 2 相连的d ( ”2 ) 条边，此时度最大的点为口1 ，但 o p t 选的点是口1 7 ，贝q d ( v 1 7 ) d ( v 1 ) ，与题设矛盾； ( 3 ) 假设选择k 一1 个点时，d g 与o p t 所选的点相同，当选择k 个点时，根据 引理3 22 知，d g 与o p r 所选的点中必有相同的，不妨设为点钆和地。 d g 执行到选择点忱时，此时与饥关联的边数为d ( ) ，不妨设这d ( v d 条边 组成的集合为：w = e 1 ，e 2 ，e d ( u ) ，在原图中删除边集，并将仉归入到 集合k 中，由归纳法知，剩余的k 一1 个点d g 与o p t 相同。而点仇与点饥7 相同， 故d g 与o p t 的点相同。 综上，证明完毕。 定理3 2 4 ：当森林的顶点的最大度为2 时，近似比为：。 证明：此时的图为由一系列的“链”组成，我们只考虑其中的一条链。由引 理3 14 可知，若使d g 覆盖的边越多，则应使其选择点的导出子图的连通分枝数 越多，所以d g 应在每次删除边的时候增加一个分枝。因此在链上d g 每隔两个 点选择一个点，即若对该链从一端到另一端标号”1 ，”2 ，贝l j d c 选择的点 为： 刨3 ，口6 ，一，1 3 3 t ，。 当n 3 k 时， d g 与o p t 所选的点的度都为2 ，点均不相邻。故有： i d g i = l o p t l 当2 k n 3 k 时， o p t i = 2 k 第三章最大顶点覆盖 1 7 i d o l = 【；j - 2 + 一【；j ) = t + 【；j 锗d c = 南k4 - 南4 - 弗2 k j 3 c 躞， li 【i j 一i 一；一十了一； 。7 当t i , 2 或f 1 i o p t i = 【；j 2 + ( 女一【；j ) = + 【；j i d c l = 【；j 2 + 一【；j ) = + 【；j i o p 引一k + 吲，吲- i - 吲 面百2 再面s 南诣， 2 雨了田 n 为奇数时： 留d g 南4 - - i - = 巍 lgi ；一；警一 = 嵩面1 8 = 一9 7 3 )= 亏而三面= 一 8 )一一3 7 当n = 2 ，4 ，6 时可以计算, 出i o p t i = i d g i 总上结论得证! 定理3 2 5 ：算法d y n a m i cg m 匆的近似比为 ，且为紧界( 上界能够取到) 。 证明： 当我们选的点的最小的度大于等于3 时，在算法进行的过程中，若当前度 最大的点不止一个点，任意取一个点，在该点上增加一条边使其变成度最大 第三章最大顶点覆盖1 8 的点唯一的图，设添边后的图为g 7 ，g 中点的度为d h ) 7 ，此时g 中和g 相对应的 点( 未添边时为同一点) y j r 变为d ( v d ，有d ( v d 7 ；d ( 仇) 则： d 。1 ) 7 + d ( 砚) 7 + 一+ d ( t ) 7 ； d ( 口1 ) + d ( 地) + ，+ d 扣 ) 即 i d c ( g ) i ；i d g ( g ) i 而 l o p t ( g ，) i2i o p t ( g ) l 根据引理32 3 j o p t ( g f ) i = i d g ( g 引 从而 i d g ( g ) i2 ；i d a ( c ) i = i i o p t ( c ，) l ；i o m l ( c ) l 即 篙d g 掰( g ) 1 3f 一 当选择的点只剩下度为1 ，2 的点时，根据定理3 2 4 知此时的近似比也是 。 下图说明了该算法的界是紧界： 9 1 _ 芦g l 挚埘s 令 = 2 ，此时d g 选择的点为”3 ， u 2 ，而o p t 选择的点为地，m ，故有： l d p 引4 l d g i 3 综上定理得证1 3 4 最优算法的猜测 受上面两个贪婪算法的启发，我们给出第三个贪婪算法。 o p tg r e e d y 1 设集合k = 出 2 将图中的度从大到小排序； 第三章最大顶点覆盖 1 9 3 令度最大的顶点形成的导出子图为m ， ( 1 ) 、首先确定m 中是否存在孤立点口，若有则令k = k u m ，然后删 除点口和与 关联的所有边； ( 2 ) 、其次选择m 中的连通子图的叶子节点，令k = g u m ，然后删 除点和与u 关联的边； 经过( 1 ) 和( 2 ) 后形成子图m ( 即森林) ； 4 对m 7 重复步骤2 和3 ，直到i k i = ； 猜测： o p tg r e e d y 是最优算法。 参考文献 1 堵丁柱，葛可一，王洁，计算复杂性导论高等教育出版社，书号：7 - 0 4 - 0 1 1 3 0 7 - 4 ，北京，2 0 0 2 2 】t h o m a sh c o r m a n ，c h a r l e sl e l e i s e r s o n ，r o n a l dl r i v e s t ，c l i f f o r ds t e i n 算 法导论( 影印版) 高等教育出版社，书号：i s b n 7 - 0 4 - 0 1 1 0 5 0 - 4 ，北京，2 0 0 5 【3 】b e r n h a r dk o r t e ，j e n sv y g e n c o m b i n a t o r i a lo p t i m i z a t i o nt h e o r ya n da l g o r i t h m s p i n g e r ， 【4 】w t t u t t e g r a p ht h e o r 弘c a m b r i d g eu n i v e r s i t yp r e s s ，i s b n ：0 - 5 2 1 7 9 4 8 9 - 7 ，c a m b r i d g eu n i v e r s i t y ，2 0 0 1 1 5 】j o nk l e i n b e r ge v at a r d o s ，a l g o r i t h md e s i g n 膨印别清华大学出版社， 北京，2 0 0 6 【6 】g e r a r dc o m u e j o l s ，g e o r g el n e m h a u s ea n d l a u r e n c ea w o l s e yw o r s t - c a s e a n dp r o b a b i l i s t i c na n a l y s i so f a l g o r i t h m s i o ral o c a t i o np r o b l e m o p e r a t i o n r e s e a r c h ，v 0 1 2 8 ，n o 4 ，1 9 8 0 ，8 4 7 - 8 5 8 【7 】g e r a r dc o r n u e j o l s ，m a r s h a l ll f i s h e r ，g e o r g el n e m h a u s e ，l o c a t i o no f b a n ka c c o u n t st oo p t i m i z ef l o a t ：a na n a l y t i cs t u d