（管理科学与工程专业论文）几类steiner树问题的研究.pdf

几类s t e i n e r 树问题的研究 摘要 本文主要对几类s t e i n e r 树问题进行了详细的论述。欧氏平面上的 s t e i n e r 树问题是这样描述的，在欧氏平面内给定一个点集，连接这些点的 最小的树叫做最小s t e i n e r 树。求解最小s t e i n e r 树的问题叫做s t e i n e r 树 问题。s t e i n e r 树问题在v l s i 设计、网络流、无线电通信等方面都有很重 要的应用。而s t e i n e r 树问题是p 一难的，除非p = n p ，否则s t e i n e r 树 问题没有多项式时间的算法。本文对区域网络问题和瓶颈s t e i n e r 树问题进 行了描述，并给出了这些问题的研究现状。 给定一个连通无向图，在该图中存在一个子图是森林，森林中的若 干个不相交的树称为若干个区域。区域网络问题就是把该森林子图( 若干 个区域) 连结成一棵树，且使增加的边的权和最小。我们对区域网络问题 进行了研究，把该问题归结为图的s t e i n e r 树问题。我们知道s t e i n e r 树问 题是n p 一难的，进而说明了区域网络问题也是n p 一难的，因此给出求解该 问题的一个近似算法，并证明时间复杂性，最后用实例说明该算法的准确 性。 瓶颈s t c i n e r 树问题就是找出最大的边，权值最小的s t e i n e r 树问题。 瓶颈s t e i n e r 树问题是有多项式时间算法的，并且知道目前最好的算法是由 c h i a n g ，s a r r a f z a d e h 和w o n g1 3 1 给出的，其算法的时间复杂性为 o ( m i n v 2 l ，旧l o g l og | e ) 。我们对瓶颈s t e i n e r 树问题进行了讨论，并给出了 求解瓶颈s t e i n e r 树问题的多项式时间算法，并将时间复杂性改进为d d 邴。 关键词：s t e i n e r 树问题，近似算法，多项式时间算法，时间复杂性 t h er e s e a r c ho fs e v e r a ik i n d so fs t e i n e rt r e e p r o b l e m a b s t r a c t i nt h i sp a p e r , w em a m l yd i s c u s ss e v e r a lk i n d so fs t c i n 盯t r e ep r o b l e mi ng r a p h p c o p l ed e s c r i b et h ee a r l i e s ts t e i n e rt r e ep r o b l e m a sf o l l o w i n g g i v e nas e to f p o i n t si n e u c l i d e a np l a n e ，j o i na l lt h ep o i n t si nt h es e ti sat r e e w ec a l lt h em i n i m u n lt r e ei sa m i n i m u ms t e i n e rt r e e 。t h ep r o b l e mo ff i n d i n gam i n i m u ms t e i n e rt r e ei ss t e i n e rt r e e p r o b l e m t h es t c i n e rt r e ep r o b l e mo r i g i n a t e sf r o mp r a c t i c el i f e ，c l a l l s sf i r s t l ys t u d i e d t h es t e i n e rt r e ep r o b l e m , h eg a v ea l lp o s s i b i l i t yt o p o l o g yf o r t h es t e i n e rt r e ep r o b l e m o ff o u rp o i n t s t h es t e i n e rt r e ep r o b l e mh a sm a n yi m p o r t a n ta p p l i c a t i o n si nv l s i d e s i g n , n e t w o r kr o u t j n g w i r e l e s sc o m m u n i c a t i o n s ，c o m p u t a t i o n a lb i o l o g ya n d s o0 1 1 t h i s p r o b l e m i sn p h a r d , e x c e p t p = n p ，t h es t e i n e r t r e e p r o b l e m h a s n o p o l y n o m - i a l - t i m ea l g o r i t h m w ec o n s i d e rt h er e g i o n a ln e t w o r kp r o b l e ma n dt h eb o t t l e n e c k s t e i n e rt r e ep r o b l e mi nt h i sp a p e r , a n dw eg i v et h ed e v e l o p m e n ts i t u a t i o na b o u tt h e s e p r o b l e m s g i v e na l lu n d i r e c t e dg r a p h , t h e r ei sa s u b g r a p hw h i c hi sa f o r e s ti nt h eg r a p h a n u m b e ro fd i s j o i n e dt r e e sa r en a m e dr e g i o n si nt h ef o r e s t t h er e g i o n a ln e t w o r k p r o b l e mi sb ed e f i n e dt oj o i nan u m b e ro f r e g i o n st ob eat r e e ，a n dt h el e n g t ho f a d d e d e d g e si sm i n i l n u n l w ed i s c u s st h er e g i o n a ln e t w o r kp r o b l e ma n dc h a n g et h ep r o b l e m i n t o s t e i n a r t r e e p r o b l e m w e k n o w s t e i n e r t r e e p r o b l e m i sn p l r a r d , s o t h er e g i o n a l n e t 、v o r kp r o b l e mi sa l s on p - h a r d g i v ea na p p r o x i m a t i o na l g o r i t h mo fs o l v i n gt h e p r o b l e m , a n da p p r o v i n gt h et i m e - c o m p l e x i t y , a tl a s tw eg i v et h ea c c u r a c yo ft h e a l g o r i t h mb yu s i n gt h ef a c t t h eb o t t l e n e c ks t e i n e rt r e ep r o b l e mi st of i n das t e i n e rt r e es u c ht h a tt h el e n g t h o f t h el a r g e s te d g ei sm i n i m i z e d t h eb o t t l e n e c ks t e i n e rt r e ep r o b l e mh a sp o l y n o m i a l - t i m ea l g o r i t h r a , f o rn o wt h eb e s ta l g o r i t h mi sg i v e nb yc h i a n g , c ，s a r r a f z a d c h , m a n dw o n g , c k a n dt h et i m e - c o m p l e x i t yi s o ( m i n v 2 旧l o g l o g l e l ) w ed i s c u s s t h eb o t t l e n e c ks t e i n a rt r e ep r o b l e ma n dg i v eap o l y n o m i a l - t i m ea l g o r i t h m 、】i ，i t ht h e t i m e - c o m p l e x i t yi so ( e ) k e yw o r d s ：s t e i n e rt r e ep r o b l e m ，a p p r o x i m a t i o n a l g o r i t h m ，p o l y n o m i a l - t i m ea l g o r i t h m t i m e - c o m p l e x l t y 几类s t e i n e r 树问题的研究 第一章引言 s t e i n e r 树问题是组合优化问题。近些年来，s t e i n e r 树问题在理论和 应用上都引起了极大的关注，尤其在日渐成熟的近似算法设计理论方面， 该问题占有一定的中心地位。 一、欧氏平面上的s t e i n e r 树问题的来源和问题描述 在欧氏平面内给定一个点集，连接点集 r 中所有点的最小的树叫做 最小s t e i n e r 树。最小s t e i n e r 树中除了给定点集以外的点叫做s t e i n e r 点，给定点集中的点叫做目标点。求解最小s t e i n e r 树的问题叫做s t e i n e r 树 问题。与s t e i n e r 点连接的边的条数叫做这个s t e i n e r 点的度。连接点集中 所有点的连接方式称为拓扑。 三个目标点一个s t e i n e r 点的最短网络问题是由f e r m a t ( 1 6 0 1 - 1 6 6 5 ) 提出来的。f e r m a t 假定在欧氏平面内有三个点，他要找到一个点使得这个 点到其他三个点的距离之和最小。在1 6 4 7 年，t o r r i c e l l i 解决了这个问题， 以已知三点做三角形，以这个三角形的每一条边为边向外做三个等边三角 形，三个等边三角形的外接圆的交点即为所求。h e i n e n 在1 8 3 7 年第一个证 得，如果以已知三点做三角形，记为a a b c ，如果这个三角形中有一个角大 于等于1 2 0 0 ，那么这个角的顶点即为所求【l 】。如果在这个三角形中，它的 三个内角均小于1 2 0 。，也就意味着满足z a s b = s b c = 么c s a = 1 2 0 。的点s 即为所求。由这一问题直接引出的一个问题就是找到一个点使得这个点到 欧氏平面内的疗个点的距离之和最小，这一问题也叫做f e r m a t 问题。 s t e i n e r 树问题也是由此产生的，最近研究数学史的专家称最早研究s t e i n e r 树问题的人是高斯。在1 8 3 6 年3 月1 9 日，s c h u m a c h e r 写了一封信给高斯， 其中提出了一个与f e r m a t 问题的目标点个数有关的自相矛盾的问题。对于 凸四边形的四个顶点，对角线的交点是f e r m a t 问题的解。当凸四边形的四 个顶点中有两个顶点重合于一点时，那么四点的f e r m a t 问题就转化为三点 的f e r m a t 问题，对角线的交点也在这个点，但这点并不是三点的f e r m a t 问 题的解。s c h u m a c h e r 不明白这是为什么。在1 8 3 6 年3 月2 1 日，高斯给 s c h u m a c h e r 写了回信，并解释了这个问题。高斯用一个网络结构来代替 f e r m a t 问题中的r 个点的距离最小的那个点，他还讨论了四个点的最小 s t e i n e r 树的所有可能拓扑。 几类s t e i n e r 树问题的研究 二、欧氏平面上的s t e i n e r 树问题的问题描述及研究 现状 众所周知，s t e i n e r 树问题是n p 一难的，除非p = n p ，否则s t e i n e r 树 问题没有多项式时间的算法。当输入规模很大时，那么就不可能在多项式 时间内找到它的精确最优解。因此，人们开始致力于找到一个好的近似算 法，给出好的近似解。为了判别算法的好坏，人们把用近似算法得到的 s t e i n e r 树的长度与最小s t e i n e r 树( 最优s t e i n e r 树) 的长度的比叫做近似 比。显然，近似比越接近于1 越好。目前，大多数人都在讨论近似比的上 确界，很少有人研究它的下确界。在过去的十年里，在s t e i n e r 树问题的研 究上人们已经取得了很大的进步，解决了关于s t e i n e r 比的g i l b e r tp o l l a k 猜想。s t e i n e r 比的g i l b e r tp o l l a k 猜想，是在1 9 6 8 年提出来的。它的内容 是欧氏平面内最小s t e i n e r 树与最小支撵树的比即s t e i n e r 比至少是3 2 。 这个猜想最终由堵丁柱，黄光明证得1 2 | 。这个证明的意义也在于证明中所 提到的新方法应用广泛。由于s t e i n e r 树问题是胛一难的，而最小支撑树 可以在多项式时间内求得。因此，人们就想到了用最小支撑树来代替最小 s t e i n e r 树，但它的近似程度并不高。2 0 多年以来，人们对此问题又给出了 许多近似算法，但是没有一个比最小支撑树更好的。在1 9 9 3 年，a l e x a n d e r z e l i k o v s k y 做出了突破，对于s t e i n e r 树问题他给出了一个多项式时间的 近似比为1 1 6 的近似算法，这个近似算法将原来的近似比由2 改进到1 1 6 1 3 】。 s t e i n e r 树问题来源于生活实践，比如，在一所大学里，学校为了办 公方便，要在校园内建内网，而在校园内建内网是要向电话公司交费的， 那么怎样收费更合理呢? 每部电话机所在的位置用点集中的点来表示， 最初人们先计算出点集的最小支撑树的长度，然后用这个长度乘以每米 的费用就得到了收费标准。这个标准一直延续到1 9 6 7 年有人发现最小支撑 树要比连接点集中每一个点的最小距离要大，为了减少自己的费用支出， 就有很多人关注这个问题。那么电话公司就不得不改变自己的收费标准，因此， 电话公司就面临这样一个问题，怎样选取这个距离才是最小的，才能合理收费。 而连接点集n 中的每一个点的最小距离就是最小s t e i n e r 树问题。此外， s t e i n e r 树问题在计算机电路板、长距离电话线、邮递路径的设计方面都有 着广泛的应用。它在通讯、交通、v l s i 设计中也起到了非常重要的作用。 虽然在实际生活中存在着多种多样可以用最早的s t e i n e r 树问题解决 的问题，但也存在许多问题只有对最早的s t e i n e r 树问题加以约束才可以解 决。为了解决这类问题，人们又对不同类型的有约束的s t e i n e r 树问题进行 了大量的研究。 几类s t e i n e r 树问题的研究 s t e i n e r 点个数最小的s t e i n e r 树问题( s t e i n e rt r e ew i t hm i n m u m n u m b e ro fs t e i n e rp o i n t s ) ：在欧氏平面r 2 内，给定一个点集 x = p ，p 2 ，“，以) 和一个正整数r ，找到一个连接x 中的每一个点的树， 使它满足树中每一条边的长度都不大于r ，且s t e i n e r 点的个数最少。其中 我们把树中除石中点以外的点叫做s t e i n e r 点1 4 。 s t e i n e r 点个数最小的s t e i n e r 树问题已经被证明是肿一难的。目前最 好的近似算法是由陈东辉、堵丁柱等人给出的，他们给出了多项式时间的 近似算法并证明了它的近似比小于等于3 。此外，他们还证明了由最小支 撑树产生的多项式时间的近似算法的近似比为4 。s t e i n e r 点个数最小的 s t e i n e r 树问题在波长划分的多路传输最优网络调剂设计中有着重要的应 用。假如人们要用波长划分的多路传输最优网络来连接处在不同位置的玎 个点p ，p ：，以。由于传输力的限制，为了保证传送的正确性，信号只能 传送一定的距离，这个距离即为盂。如果在这疗个点中，有两点的距离超 过胄，就需要在某个位置加一个增幅器或传送器以使这个距离减小。此外， s t e i n e r 点个数最小的s t e i n e r 树问题在v l s i 设计，生物学中的动物种类史 的建立中也有广泛的应用。 瓶颈s t e i n e r 树问题( b o t t l e n e c ks t e i n e rt r e ep r o b l e m ) ：设集合 p = p 。，p ：，以 为有一个点的点集，给定一正整数i ，要找到一个至多有 七个s t e i n e r 点的s t e i n e r 树，使它满足最长边的长度在所有树中最小i 5 1 。 这个问题是n p 一难的，目前由堵丁柱等人研究得出( 1 ) 如果n p p ， 在欧氏平面上，这个问题的任何多项式时间的近似算法的近似比至少是 2 。( 2 ) 如果胛p ，在直线平面内( 平面内所有直线只能是垂直或平行 两种关系) ，这个问题的任何多项式时间的近似算法的近似比至少是2 。此 外，他们还给出了一个多项式时间的近似算法，这个近似算法的近似比无 论是在欧氏平面还是直线平面下都是2 。瓶颈s t e i n e r 树问题可应用于无线 电通信网络的设计中，由于资金的限制，假定最多可以设置厅4 - _ i 个转接点， 而又要求这行个转接点的位置是固定的。为了保证信号质量，当然任意两 个转接站的距离越小越好。因此要选定至多后个转接站的位置，使得连接 选定点与这一个点的最小树中，距离最大的两个转接站的距离是所有树中 最短的。这样的问题可以用瓶颈s t e i n e r 树来求解。 直角折线s t e i n e r 树状图问题( r e e t i l i n e a rs t e i n e ra r b o r e s c e n e e p r o b l e m ) ：令p = ( p o ，p 1 ，p 2 ，p 。) 是平面内的点集，每一个点p ，都对应 坐标( x t , y 。) ，p 。是原点，直角折线树是指由水平线和垂直线连接而成的树。 一个s t e i n e r 点是指它满足( 1 ) 两条线在g 点相交，( 2 ) g 不是任何一条交线 几类s t e i n e r 树问题的研究 的端点，( 3 ) 口p 。对于点集p 的直角折线s t e i n e r 树是直角折线的树，且 它的点或者是s t e i n e r 点或者是点集p 中的点，并且满足n p 均为树中 边的端点。点集p 的直角折线s t e i n e r 树状图是点集p 的直角折线s t e i n e r 树，且它满足从原点到p ，的唯一指定路径的长度等于k 。i + 1 ) ，。i ，如图1 所示。 直角折线s t e i n e r 树状图问题就是找到一个直角折线s t e i n e r 树状图使得它 的长度是所有直角折线s t e i n e r 树状图中最小的( 6 1 【”。 图1 直角折线s t e i n e r 树状图 直角折线s t e i n e r 树状图问题可用于v l s i 设计。直角折线s t e i n e r 树状 图问题已经被证明是强n p 一完备的。因此，人们不可能在多项式时间内求 得它的最优解。对于平面内的直角折线s t e i n e r 树状图s k r a o ，p s a d y a p p a n 等第一个给出了复杂性为o ( n l o g n ) ，近似比为2 的近似算法。l e u n g t 等用 分枝定界法和动态规划的方法对于平面内的直角折线s t e i n e r 树状图问题 给出了两个最优算法，但当输入规模较大时，这两个最优算法的运行时间 过长。 对称的直角折线s t e i n e r 树状图问题( s y m m e t r i cr e c t i l i n e a rs t e i n e r a r b o r e s e e n c ep r o b l e m ) ：在平面的第一象限内给定行个点，求解一个树使 它满足这行个点中任意两点的路都是由水平线和垂直线组成的，并且这个 路上的点的纵坐标是非减的，且这个树的长度最小。如果这个树中包含原 点，且从原点到达行个点中任何一点的路都满足路中所有带内的横坐标非 减，纵坐标非减，那么这个问题就转变成了直角折线s t e i n e r 树状图问题 i l l 。 几类s t e i n e r 树问题的研究 如图2 、图3 所示。 图2 直角折线s t e i n e r 树状图图3 对称的直角折线s t e i n e r 树状图 对称的直角折线s t e i n e r 树状图问题在v l s i 设计，优化算法和力学问题 上都有广泛的应用。对于对称的直角折线s t e i n e r 树状图问题，目前最好的 近似算法是由c h a r i k a r 等人给出的，并且证明了近似解最多是最优解的3 倍。程秀珍等人又给出了对每一个常值占 0 的多项式时间的近似算法，并 证明了近似解是最优解的1 + 占倍。 a s t e i n e r 树问题( a s t e i n e r t r e ep r o b l e m ) ：对于平面内的一个点，给 定一个点集p ，找到一个连接p 中所有点的最小树，且这个树中所有边与x 轴的 夹角等于却，f = 0 , 1 ，五一1 ，w = 州五。这里a 2 ，由实际问题中的要求所定【9 】， 如图4 、图5 、图6 所示。 图42 - s t e i n e r 树图54 - s t e i n “树图68 - s t e i n e r 树 一5 几类s t e i n e r 树问题的研究 避障碍的s t e i n e r 树问题( o b s t a c l e - a v o i d i n ge u c l i d e a ns t e i n e rt r e e si nt h e p l a n e ) ：在平面内给定一个含有一个点的点集z ，用q = m ， 表示障碍 集，其中w s ，f = l ，h 为障碍，为一个包含z 的多胞形，找到一个最小树， 使它连接z 中所有点且树中的边不能经过障碍集内部，不能在w 0 外部，树 中所有边和点可在w 0 和q 的边界上，树中除了z 中点外的点叫做s t e i n e r 点【i o 】。 因为平面上的s t e i n e r 树问题是p 一难的，所以避障碍的s t e i n e r 树问 题也是n p 一难的。避障碍的s t e i n e r 树问题在生活中的网络设计中应用广 泛。m a r t i nz a c h a r i a s e n 和p a w e lw i n t e r 对这个问题给出了一个精确算法， 当行1 5 0 时，最优解可在几个小时内求得。 三、图的s t e i n e r 树问题的问题描述及研究现状 s t e i n e r2 边残缺网络问题( s t e i n e r2 e d g es u r v i v a b l en e t w o r k p r o b l e m ) ：给定一个图g 和图g 中的点的集合y ，在图g 中找到一个连接y 中所有点的子图，使它满足这个子图的长度最小，且在这个子图中，矿中 任意两点至少有两条边不相交路【1 1 l 。 s t e i n e r2 - 边残缺网络问题可应用于可靠通信和运输网络等领域。一般 情况下s t e i n e r2 - 边残缺网络问题是n p - 难的。但当给定的图为特殊图时， 这个问题又是多项式可解的。当给定的图为h a l i n 图和平行图时，对这个问 题w i n t e r 给出了线性时间的算法。 k 度s t e i n e r 树问题( k - s t e i n e r t r e e p r o b l e m ) ：对于给定的图g 和点集 矿，在图g 中找到一个连接矿中所有点的树，使它满足这个树的长度最小， 且s t e i n e r 点的度不超过k 。其中，树中除矿以外的点叫做s t e i n e r 点【”1 。 关于x 度s t e i n e r 树问题，人们主要研究了足度s t e i n e r 比n ，以为 最小s t e i n e r 树与k 度最小s t e i n e r 树的比的下确界。目前由堵丁柱和 b o r c h e r sa l 给出了成。特别地，当k = 2 时，2 度s t e i n e r 树问题就是求解连 接y 中所有点的最小支撑树。 图的不相交的s t e i n e r 森林问题( n o n c r o s s i n gs t e i n e rf o r e s t si np l a n e g r a p h s ) ：给定一个无向图g = ( 矿，e ) ，其中l ，n 2 ，m 为七个点集，且 1 ，n 2 ，m v ，五，疋，瓦是树，满足z 是连接m 中所有点的树，r 是 由五，正，瓦组成的森林，r 中任意两个树不相交，找到r ，并使r 的长度 最小。 图的不相交的s t e i n e r 森林问题可应用于v l s i 设计中，y o s h i y u k i 几类s t e i n e r 树问题的研究 k u s a k a r i 等人研究了当对所有点有约束时，不相交的s t e i n e r 森林问题的算 法，这个算法的运行时间为o ( n l o g 疗) ，这里n 为g 中点的个数。 成组的s t e i n e r 树问题( c l a s ss t e i n e rt r e ep r o b l e m ) ( g r o u ps t e i n e r t r e ep r o b l e m ) ：给定一个连通无向图，把它的点分为任选的s t e i n e r 点组和 必选的点组，找到一个树使它满足至少含有每个必选组中的一个点，并且 长度最小i 1 4 1 ”1 。 在v l s i 设计中，当电路板上的每个组成部分的位置已经固定时，要用 一个电路把每个部分连接起来，使这个电路的总长度最小，而每个组成部 分又有很多部件，人们可能只需要连接每一部分中的一个部件就可以把这 一部分连入电路，这就用到了成组的s t e i n e r 问题与最小点覆盖问题是等价 的。然而最小点覆盖问题是否存在一个常量近似仍然是一个o p e n f 习题。所 以没有s t e i n e r 点的，边长是1 的成组的s t e i n e r 树问题是否存在一个常量近 似依赖于最小点覆盖问题。而最小点覆盖问题已经被证明是m a xs n p 难 的，所以成组的s t e i n e r 树问题也是比舒伊难的。关于成组的s t e i n e r 树 问题，g o r a n k o n j e v o d 和r r a v i 第一个给出了近似算法，在这个算法中他们 用了多重对数的近似比。 覆盖s t e i n e r 树问题( c o v e r i n gs t e i n e rp r o b l e m ) ：给定一个连通无向 图，把它的点分为任选的s t e i n e r 点组和必选的点组巧，圪，对每一个 必选的点组给定一个定值马，胄，r 。，找到一个树使它满足连接必选点组 k 中的胄。个点，f - 1 , 2 ，一，并且这个树的长度最小【”】。 当每个必选点组给定的常值都是1 时，覆盖s t e i n e r 树问题就转化成了 成组的s t e i n e r 树问题。当r 。中的值越接近巧中的点的个数时，就越容易得 到近似算法。但覆盖s t e i n e r 树问题的难度至少和成组的s t e i n e r 树问题的 难度等价。关于覆盖s t e i n e r 树问题a r a v i n ds r i n i v a s a n 给出了较好的近似算 法，这个算法和成组的s t e i n e r 树问题目前最好的近似算法等价。 多权s t e i n e r 树问题( m u l t i p h a s es t e i n e rn e t w o r kp r o b l e m ) ：给定一个 连通无向图，它的所有边的边权用c l ( e ) ，c 2 0 ) ，靠( 0 来表示，且满足 c l ( p ) 岛( p ) q 0 ) 。对于给定的一个点集，并将它分成k 个部分，即 n = n 1 ，2 ，m ，其中i n i l 2 ，找到一个连接中所有点的最小边权和 的树，使它满足这个树中在，中的点的任意两点的路的边权至少为 c j ( p ) 1 1 7 1 多权s t e i n e r 树问题可应用于具有不同传输速度的复杂网络。 满s t e i n e r 树问题( f u l ls t e i n e rt r e ep r o b l e m s ) ：给定一个连通无向图 g = ( 矿，e ) ，r 是矿的子集。在图g 中找到一个连接尺中所有点的最小树， 几类s t e i n e r 树问题的研究 且满足在这个树中所有的目标点都是叶子。其中r 中的点称为目标点，在 这个树中，不是目标点的点称为s t e i n e r 点，这个最小树为满s t e i n e r 树”】。 关于满s t e i n e r 树问题，m a r t i n e z ，p i n a 和s o a r e s 给出了近似比为 2 p p ( 3 9 2 1 的近似算法，其中p 是对f s t e i n e r 树问题已知的最好的近 似比，它是由g a b r i e l r o b i n s 和a l e x a n d e r z e l i k o v s k y 给出的，这里p 1 5 5 0 。 几类s t e i n e r 树问题的研究 一、引言 第二章区域网络问题 给定一个连通无向图g = ( 矿，e ) ，设r 是图g 的点集矿的子集， t 量矿( g ) ，图g 中每边的长度用函数c ：e 专r + 来表示。一个最小s t e i n e r 树是g 的连通子图，它含有丁的全部点，且是边长度和最小的树。在实际 生活中，图的s t e i n e r 树问题有着非常重要的应用价值。例如在通讯、销售 和运输系统的设计中都有着广泛的应用。此外在v l s i 设计、网络流、无 线电通信等方面也应用广泛。另一类可以用图的s t e i n e r 树问题解决生物学 中动植物种类史的树的计算问题。因此在很多年前人们已经开始研究它 了，并且知道这个问题是n p 难的。人们给出了较好的近似算法，做了大 量的研究。目前，对于s t e i n e r 树问题，最好的近似算法是由g a b r i e l r o b i n s 和a l e x a n d e rz e l i k o v s k y 给出的，他们还证明了这个近似算法的近似比为 1 5 5 0 ，以后我们称它为r z t ”算法。 在实际生活中，又出现了与s t e i n e r 树问题密切相关的另一类问题， 我们把它称之为区域网络问题瑚l 。给定一个连通无向图g = ( y ，e ) ，在图g 中，存在一个子图是森林，森林中的若干个不相交的树称为若干个区域。 区域网络问题就是把该森林子图( 若干个区域) 连结成一棵树，且使增加的 边的权和最小。区域网络问题可应用于实际生活中，例如在无线电通讯， 铁路干线网络和高速公路网络等，区域网络问题都有着非常重要的应用价 值。具体实例如：不同的省份有自己不同的内部铁路干线网络，并可知各 省的内部铁路网均为一棵树，该树连接本省的一些城市，而省份与省份之 间也有一定的铁路网。我们所要解决的问题是：在给出的一些省份，这些 省的内部铁路网已经固定，我们怎样连结这些省，使得所走的路最短，该 实际问题就可以利用区域网络问题的求解方法来解决。 本章主要讨论了区域网络问题。我把该问题转化成了图的s t e i n e r 树 问题。因为我们知道，对于一般的s t e i n e r 树问题已经被证明是n p 难的， 进而给出求解该问题的一个近似算法，并证明其复杂性，最后用实例说明 该算法的准确性。 二、s t e i n e r 树问题 s t e i n e r 树定义为：给定一个无向图g ( v ，e ) ，t v ( g ) 。在图g 中，对 于点集r 来说，丁的s t e i n e r 树指的是一棵树s ，且r v ( s ) 矿( g ) ， 几类s t e i n e r 树问题的研究 e ( s ) e ( g ) 。这里r 中的元素称为目标点，v ( s ) r 中的元素称为s 的 s t e i n e r 点。 s t e i n e r 树问题：给定一个无向图g ( v ，d ，权c ：e ( g ) - - ) r + ，t v ( o ) 。 在图g 中找到r 一个s t e i n e r 树s ，使得f ( e ( s ) ) 最小。 s t e i n e r 树问题是n p 难的。目前，对于s t e i n e r 树问题，最好的近似算 法是由g a b r i e lr o b i n s 和a l e x a n d e rz e l i k o v s k y 给出的，我们称之为r z 算 法。本文给出的求解区域网络问题的近似算法就是归结于该r z 算法。 三、近似算法 在给出近似算法前，我们先给出三个定义。 定义1 ：区域与区域之间的距离：各个区域之间可以有很多边相连，我们 规定在这些边中，选择最小边权的边来表示区域与区域之间的距 离。 定义2 ：点与区域之间的距离：每个点与区域之间也可以有很多边相连， 我们规定在这些边中，选择最小边权的边来表示点与区域之间的 距离。 定义3 ：压缩点：给定一个无向图g = ( y ，e ) ，x v ( g ) ，压缩点j 意味着 去掉点z 与其对应的边g 防】，然后增加一个新的点苫，用边扛，w 代 替每个边 v ，w ，1 ，x ，w 仨x ( 可能产生平行边) 。 近似算法3 1 ； ( 1 ) 把图g 的七个区域正，疋，疋，各压缩成一点r 1 ，r 2 ，t ，新生成的图 为g 1 。把图g 1 的各个边分别用原来的端点标出。 ( 2 ) 在图g 1 中根据定义l 和2 表示出新的k 个区域( 压缩点) r 1 ，r 2 ，t ， 与其对应的区域与区域之间的距离以及点与区域之间的距离，并在选 择的边上标出该边原来的端点。 ( 3 ) 根据s t e i n e r 树问题的求解方法r z 近似算法求解图g 1 的最小s t e i n e r 树。 恢复算法3 2 ： ( 1 ) 把图g 1 的_ j 个区域一，丁2 ，t 恢复为五，疋，互。 ( 2 ) 根据选择边的端点符号，在区域五，瓦，瓦中把上述近似算法( 3 ) 求得 的最小s t e i n e r 树中增加的边表示出来，即得到图g 的s t e i n e r 树。于是( 2 ) 中的解即为区域网络问题的最优解。 因此，通过上述近似算法我们可以看出，区域网络问题可以归结为图 几类s t e i n e r 树问题的研究 的s t e i n e r 树问题。由于图的s t e i n e r 树问题已有r z 近似算法，进而区域 网络问题就可利用该近似算法求解。 四、算法复杂性 在近似算法步骤( 1 ) 中所需的时间o ( n m ) ，步骤( 2 ) 相当于求两点之间 的最短路，因此所需的时间为o ( n 2 ) 。设求s t e i n e r 树问题的复杂性为d ( 力， 因此求解区域网络问题的时间复杂性为o ( o m n 3 ) 。( 这里的 栉= l 矿( g ) | ，所= l e ( g ) 1 ) 五、用实际问题的求解来说明算法的准确性 问题；图7 中实线为( 彳) ，( 研，( c ) - - 个区域，虚线为给出的区域与 区域，点与区域之间的路。问如何连结( 4 ) ，( 曰) ，( c ) 使得所走的路最短。 图7 1 1 ( b ) 几类s t e i n e r 树问题的研究 1 、求解步骤： ( 1 1 ) 将( 4 ) ，( b ) ，( c ) 三个区域各压缩成一点彳，b ，c ，并用原来的端点 表示出对应的边，生成的图为图8 ： 图8 ( 1 2 ) 选择最小边权的边来表示区域与区域之间的距离，去掉多余的平行 边；选择最小边权的边来表示点与区域之间的距离，去掉多余的平行边得 到的图9 ： 图9 ( 1 3 ) 最后根据r z 算法求出的图3 的最小s t c i n e r 树为图1 0 所示： 2 、恢复步骤： ( 2 1 ) 把压缩点彳，口，c 恢复为原来的区域，得到图1 1 ， 几类s t e i n e r 树问题的研究 d c 图l o p 图1 1 g ( 2 2 ) 根据增加边的端点符号，表示出增加的边，最终所求得的s t e i n e r 树 为图1 2 所示。 通过计算可知，连结三个区域所走的路长为：1 0 4 + 5 4 + 3 7 + 1 8 0 = 3 7 5 。我 们可以验证该结果是最优的，因此也说明该近似算法的准确性。 综上所述，本章主要研究了区域网络问题，它可以归结为图的s t e i n e r 树问题。对于s t e i n e r 树问题，我们己知道其r z 近似算法。因此在此基础 上，我们给出了求解区域网络问题的一个近似算法，并证明其算法复杂性， 最后用实例说明了算法的准确性。 ( a ) 、5 4 几类s t e i n e r 树问题的研究 图1 2 1 4 - ； ；1 8 0 ； ； ( b ) 、jf p 几类s t e i n e r 树问题的研究 一、引言 第三章瓶颈s t e i n e r 树问题 给定一个连通无向图g = ( 矿，司，图g 的边权用函数c ：占( g ) 寸r + 来 表示。丁是图g 的点集y 的子集，z 矿( g ) 。s t e i n e r 树是g 的连通子图， 它含有r 的全部点，其中r 中的元素称为目标点，矿( s ) r 中的元素称为s 的s t e i n e r 点。s t e i n e r 树问题就是找出权值和最小的s t e i n e r 树。因为图的 s t e i n e r 树问题在通讯、v l s i 设计、网络流、无线电通信等方面都有很重 要的应用【2 “州。因此在很多年前人们已经开始研究它了，并且这个问题已 经被证明是n p 难的。人们也做了大量的研究，给出了许多近似算法。目 前，对于s t e i n e r 树问题，最好的近似算法是由g a b r i e lr o b i n s 和a l e x a n d e r z e l i k o v s k y 给出的，以后我们称它为r z 算法，该近似算法的近似比为 1 5 5 0 。 如果一个s t e i n e r 树，在该树中最大的边，权值最小，我们称这个树为 瓶颈s t e i n e r 树1 2 5 - 2 7 。瓶颈s t e i n e r 树问题就是找出最大的边，权值最小的 s t e i n e r 树问题。瓶颈s t e i n e r 树问题在生物学领域【2 s 】，v l s i 设计领域 2 9 - 3 1 1 ， 运输和电信1 3 2 矧等方面都有着广泛的应用。我们已经知道瓶颈s t e i n e r 树问 题是有多项式时间算法的，并且知道目前最好的算法是由c h i a n - g ，s a r r a f z a d e h 和w o n gp 4 1 给出的，其算法的时间复杂性为： o ( n 恤 l v 2 i ，i 矧l o g l o g i e l ) 。 本章主要讨论了瓶颈s t e i n e r 树问题，给出其多项式时间算法，证明了 算法的正确性，并将时间复杂性改进为o ( i e i ) 。 二、瓶颈支撑树的算法及算法复杂性 给定一个无向图，g = ( ，e ，力，节点集为n = l ，2 ，珂 ，边集为 e = e 1e 2 ，e