（管理科学与工程专业论文）瓶颈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 i 设计中也起到了非常重要的作用在管理科学 中，图的s t e i n e r 树问题在销售和运输系统的设计、v l s i 设计、网络流等方 面也起到指导作用s t e i n e r 树问题开始应用于生命科学，解决物种演化问 题，s t e 妇r 树问题应用范围很广，成为多个学科专业领域的专家学者的研 究热点 本文将继续对图上的s t e i n e r 树问题进行研究，文中提出满瓶颈s t e i l l e r 树问题的模型给出满瓶颈s t e i n e r 树问题的性质，给出了多项式时间算法， 并用数值例子说明此算法的正确性和有效性 近二十年，反问题在管理科学中应用较多，成为被关注的焦点，很多问 题可以归结到数学问题的反问题解决，如反最小支撑树问题、反最短路问 题、反最大流问题等，各种问题的总体思想是相似的，但它们的方法各不相 同反组合最优化兴起于对道路的设计，另外。它在生物结构科学及一些花 费问题上应用尤为突出 在本文中，通过对反问题的学习，在研究反瓶颈支撑树问题的性质与算 法的基础上，我们提出反瓶颈s t e i n e r 树问题模型，研究问题的性质，给出 z z 范数下有边界限制的反瓶颈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 树问 题，多项式算法，时间复杂性 b o t t i e n e c ks t e i n e r r r e ep r o b i e m a b 啦恰c t ：g i v e n8s e to f 俺p o i n t s ，丑n d i n ga 七r 0 fm i n i m 啪l i e n 戥h 七oc o n n e ! c tt h e p o i n t 8o fn i sc a dam i n i m ：眦s t e i e rt r e e s t e i n e r 切p r 砒i l e mi s8 ni m p o r t 毗 8 e c t i o no ft h ec o 衄b i n a t i o r i a lo p t i m i z a t i 0 i np r o b l e m 8 s t e i n e rt r e ep r o b l e mc 8 nb e 8 p p l i e dw i d e l yi nm a n 戳r e m e n ts d e n c e ，e n 酉n i e e 血gt e ( 岫l o 帮a n d8 0o n 。m o r ea n d 皿1 0 r ep e o p l e8 r ec ( m c e r 列e da b o u tt l l i sa e r a s t e i n e rt r e ep 吣b l e mi nt h ec o m p u t e r c i r 咖tb o 舭d ，t h e1 0 n 分d i 8 t a n c et e l e p h o n el i i l 鹤舭l dt h ed 鹤i g no fp o s t a l lr o u t eh a v e aw i d e rr a n _ g e 印p l i c a t i o n 8 i nt h e 咖i m l n j c a t i o n s ，t r 龇1 8 p o r t ，v l s id 鹤i g ni t 山o p l a y 8av 明了i m p o 毗锄七r o l e i nm 锄娜；e m e n ts c i e n c e ，s t e i n e rt r e ei ng r 印h 88 l l s 0h 够 伽i 衄tf b rm u c ho f 印p l i e dv m u e f b re x 锄p l e ，t h e 妇i g no fm 8 r k e t i n g 缸l dt r 8 n s - p o r t a t i o ng y 8 t e m 8h a ew i d ea p p l i c a t i o i n s t e i n e rt r e ep r 0 1 ) l 眦b e 西璐t ob eu 8 e d i nl i f e8 c i e n c et os o l v er e 、，e l o t i o no f8 p e c i e 8 s t e i n e rt r 印p l i 鹤e 哦e 鹏i v e l y 锄d m 强yr e 苣旧扯c h e r 88 t a r tt oc o n c e r na b 0 1 l tt h i sa e r aa n ds t u d yi t t l l i st h 髑i s 而uc o n t i n u et os t u d ys t e i n e rt r p r o b l e m i nt h ea r t i c l e ，t h et h 争 s i sp r 鹤e n t st h e f u ub o t t l e i l e d cs t e i n e rt r e ep r o b l e m w e 西v et h ep r o p e r t i 髑o ff i m b o t t l e 】1 e d 【s t e i n e rt r p r o b l e m g i v eap o l ”l o l l l i a i - t i m e 姆i t a tl a s t ，w e 西v e 眦e x 锄p l et ov e r i 匆i t 8c o r r e c t 蚰de 珏b c t i 矾m 船s 两溉n t 伽e 刀姆y e a r 8 ，i n v e r p r o b l e mi 8u s e di nm 蛆a g 即n t i e n c eal i d tm l d 0 0 i 煅n e dd e e p l y m a n yp r o b l e r n 8c a nb er e d u c 嗣t oi n ：v e r 舱p r o b l e mi nm a t h 争 m a t i c s f b r 咖p l e ，i n 、，e r s es p a n i l i n gt r e ep r o b l e m ，i m r e r 跎t h es h o r t 鹤tp a t h gp r d b - l 眦，i 删e r s et h el 盯g 朗t 丑o wp r o b l e l n ，a n d o n t l 蛹ep r o b l e m s8 r es i m i l 盯，b u tn o t t h e8 舢m e a t 丘r s t ，i n v e r o p t i m i z 8 t i o no m i i n l l mp r o b l e m 锄e 8f 锄址l ed 髑i g no f r o a d b e 8 i d e s ，i ti sa l s ow i d e l yu s e di nt h e8 t r u c t u r eo fb i o l o 舀c a ls c i e n o e 缸d8 0 i 屺 p r o b l e m sa b o u to t i nt h e 踟飞i c l e ，1 e 啪a n d8 t u d ya b o l l tt h ei i l _ v 乇鹈ep r o b l e m b a 跚do nt h e8 l - 酬t ha n d 瞅n ep r o p e r t i 铭o nt h ei n 、惯8 eb o t t l e | 腕ks p a n i l i n gt r e ep r o b l e m ，w e 西v ea 加【0 d e la b o u ti i e r s eb o t t l e n e c ks t e i n e rt r e ep r o b k ma n d8 t u d yi t 8p r o p e r t y g i v eap 0 1 y n o 如曲l t i m em 舀) r i t h mu n d e rw 西g t h e dz 1n o r mw i t hb 0 1 皿【dc o 璐t r 出t 8 a n di t 8m 衄j n gt i n 地0 ft h ea l g i 试t h m a tl 嬲t p r o 、，et h ea 1 9 0 r i t h mr i g h t k e y 哪d s ：b o t t l e n e c ks t e i n e rt n e ep r o b l e m f u b o t t l e n e c ks t e i n e rt r i e ep r o l 卜 i e m ，i n v e r 驰b o t t l e n ks t e i n 甜t r p r o b i e m p o i y n o m i a ia i 驴r i t h m ，c o m p i 歌时 o f t i m e 学位论文独创性声明 本人所呈交的学位论文是在导师的指导下取得的研究成果。据我所知， 除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过 的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了 明琅说明并表示了谢意。 作者签名：基些丝 日期：丝星：兰：三f 学位论文使用授权声明 本人授权沈阳师范大学研究生处，将本人硕士学位论文的全部或部分 内容编入有关数据库进行检索；有权保留学位论文并向国家主管部门或其 指定机构送交论文的电子版和纸质版，允许论文被查阅和借阅；有权可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。保密的学位论文 在解密后适用本规定。 作者签名：枣丝垫 日期：筮堕：查1 瓶颈s t e m e r 树问题 第一章引言 8 t e i n e r 树问题是组合最优化问题十分重要的研究内容之一，它在运输、通讯网络、 汽油管线设计、电力电缆架设等有举足轻重的作用【卜3 】另外，s t e i n e r 树问题在生命 科学及相关领域有着广泛的应用s t 血埘树问题研究及发展的历史悠久曲折，有各种 度量空间的s t e i n e r 树问题，其中，平面上的与图上的s t e i n e r 树问题应用最为广泛 下面介绍一个图上的s t e i n e r 树问题在管理科学上的应用 在一个居民区里，为了满足市民打电话的需要，需在社区内架设电话网，而在社区 内架设电话网是需要一定的费用的，那么怎样才能使架设电话网的费用降到最低呢? 每部电话机所在的位置用点集来表示，那么，这个费用什么时候有最小值呢? 最初 人们先计算出点集的最小支撑树的长度，然后用这个长度乘以每米的费用就得到了 总的费用这个标准一直延续到1 9 6 6 年1 9 6 7 年有人发现最小支撑树要比连接点集 与点集以外的某些点的最小距离要大，为了减少相似问题的费用支出，就出现了这 样一个问题，怎样选取这个距离才是最小的，才能最大可能的减少开支而怎样连接 点集中的点使它们的距离最小就是最小s t e i n e r 树问题 由于平面上的与图上的s t e i n e r 树问题的广泛应用，近三十多年来它们受到有关学 者的重视，本章将对这两种问题进行简单介绍 一、s t e i m r 树问题 平面上的s t e i n e r 树问题：在平面上给定一个点集t ，要求用最小的长度将t 中的 点连接起来的树，树中可以包含除t 以外其它的点，这个问题就称作平面上的s t e i n e r 树问题这个问题的一个解称作最小s t e i n e r 树我们把点集t 中的点称目标点，在解 中，除集合t 以外的点称作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 树有很多有趣的性质【4 】： ( 1 ) 最小s t e i n e r 树是一棵树，不含有圈 ( 2 ) 最小s t e i 聃r 树中，相交线的角度大于或等于1 2 0 度 ( 3 ) 对每个s t e i n e r 点，三边相交的角度一定为1 2 0 度 ( 4 ) 对于一个有礼个目标点的最小s t e i n e r 树最多有礼一2 个s t e i n e r 点 1 瓶颈s 如n e r 树同题 2 ( 5 ) 平面上的最小s t e i r l e r 树解是不唯一的 平面上的最小s t e i n e r 树问题是m a x s p 一难的，1 9 6 8 年，e n g i l b e r t 与 h o p 0 u a k 猜测性能比的下界是狮f 2 ，这也是著名的s t e i n e r 比猜想这个猜想直到 1 9 9 2 年才得以证明【5 】当s t e i n e r 点的个数为n 一2 时，把这种树叫满s t e 嘶树，树 中目标点都为叶子在满s t e i n e r 树中，若目标点的个数大于2 ，则树中一定有s 懈n 凹 点，这个问题仍然是m a x s 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 妇r 树是要连接t 中的点，并极小化e = z e 吲九+ a ( 删m b e ro fs t e i n e rp o i n t 8 ) ，a 是 一个确定的非负权因子，解这个闻题叫点权s t e i n e r 树问题【4 1 满s t e i n e r 树问题是目 标点都是叶子的s t e i n e r 树满s t e i n e r 树问题在生物学、。s i 设计、网络流和电信等 方面有着重要的应用 人们在研究s t e i n e r 树问题的过程中提出了这样的问题t 有礼个用户，要建一个将 这n 个用户连接起来的连通网络，用户与用户之间的连接要通过中转站，与中转站连 接的最多用户数为凳，怎样连接使总连接网络最短，我们把这个问题叫做老度s t e i n e r 树问题，这个问题没有多项式算法4 度s t e i n e r 树问题是此问题的一个特殊情况，它 是多项式可解的，在【6 】中给出了算法，证明了算法的时间复杂性是0 ( n 2 ) 二、图上的s t e i 聃r 树问题 图上的s t e i n e r 树问题可以描述为：给定一个加权无向图g ，给定点集t 冬y ( g ) ，s 为g 中的棵树，满足z y ( s ) 冬y ( g ) ，并且以s ) e ( g ) ，s 称作t 在g 中的s t e i n e r 树，其中集合t 中的点称作目标点，y ( s ) t 中的点称s 的s t e i n e r 点y ( g ) t 中 的点称作s 的可选点 s t e i n e r 树问题：g 是一个边赋权无向图，给定一个点集t y ( 回，在g 中找出对 于t 的一个s t e i n e r 树s ，使其权值和最小，s 称为对于t 的一个最小s t e i n e r 树 容易看出，当t = y ( g ) 时最小s t e i n e r 树是最小支撑树，当例= 2 时就是最短 路问题，这两个问题都有多项式时间算法这两种情况是s t e i n e r 树问题的特殊情形， 而s t e i n e r 树问题的一般情形，d r e y f u 8s e 和w 堍n e rr a 给出了s t e i n e r 树问题的精 确解，算法的时间复杂性是指数的【7 】1 9 7 2 年由k 跗p 首先证明s t e i n e r 树问题是p 一 难的【8 】，由b e r m 和p l 躐m a n n 在1 9 8 9 年证出s t e i n e r 树问题是m a x s p 一难的1 9 】， 所以它没有多项式时间算法，即便它所有的边权都是1 但s t e i n e r 树问题有许多近似 算法： k 0 u ，m a r k 0 w 8 k y 衄db e r m a n 给出用最小支撑树近似s t e i n e r 树，得到时间复杂 瓶颈s t e i l l e r 树问题 3 性为d ( 佗3 ) 的二因子近似算法【1 0 1 ，m e b d l l o mk 和k o ul 把互因子近似算法的时间 复杂性改进到d ( n 2 ) 【1 1 1 2 】，实际上还有近似比更好的近似算法，在1 9 9 3 年，a k 眦d e r z e u k 叫s k y 做出了突破，对于s t e i n e r 树问题他给出了一个近似比为1 1 6 的多项式时间 近似算法1 1 3 】，这个近似算法将原来的近似比由2 改进到1 1 6 随后，1 9 9 4 年由b e r i n 缸 和旺a i y e r 将其改进到1 7 5 【1 4 1 ，1 9 9 7 年由k a r p i n s k i 和z e h k o v 8 k y 改进到1 6 5 【1 5 1 ，1 9 9 9 年又由h o u g 甜d y 和p r o l n e l 改进到1 6 0 【1 6 1 ，目前，最好的近似算法是由g a b r i e lr 0 b i n 8 和a k a n d e rz e h l 跚8 k y 给出的，它的性能比为p = 1 + l n 3 2 ，约等于1 5 5 0 【1 7 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 i 埘树 问题和满s t e i n e r 树问题进行简单介绍 ( 一) 、瓶颈s t e i 矾r 树问题 瓶颈s t e i n e r 树。加权无向图g ，目标点集t y ( g ) ，在g 中的一棵树s ，满足 t y ( s ) y ( g ) ，e ( s ) e ( g ) ，且最大的边权值最小 在网络设计中，要考虑到费用的限制假设有t 个城市，现在要建设铁路网使这 几个城市连接起来，如果需要加入除t 个城市以外其它的城市，那么加入的城市间的 费用忽略不记，而t 个城市间的与t 和加入城市间的费用由这t 个城市负责，所以每 个城市都希望花费最小的费用如果不考虑其它因素的影响，只有当连接每个城市的 最大距离是最小的，才能满足这t 个城市要求这个问题就是瓶颈s t e i n e r 树问题 c h a r l e 8c 1 1 i 趿g ，m a j i ds a r r 也a d e h 和c k w r o n g 通过将瓶颈s t e i n e r 树转化为瓶颈支 撑树的方法f 圳，给出它的一个最优多项式解法，并指出它的时间复杂性，它的时间复 杂性为o ( 1 n i n i e i l o g l o g 旧，i y l 2 ) ( = ) 、满s t e i m r 树问题 满s t e i n e r 树t 加权无向图g ，目标点集t y ( g ) ，在g 中的一棵树s ，满足t y ( s ) y ( g ) ，e ( s ) e ( g ) ，且目标点集t 中的点在s 中都为叶子 满s t e i n e r 树问题：就是求权值和最小的满s t e i n e r 树 例如在通讯网络设计中，信息发送点和信息接受点已经确定，并且不允许它们作 为信息中转点，中转点只能是除去发送点和接受点以外给出的点，即信息的发送点和 接受点必须是叶子此外，满s t e i l l e r 树问题在生物学、v l s i 设计、网络流和电信等 方面也都有着重要的应用 瓶颈s t e i i i e r 树问题 4 满s t e i n e r 树问题已经被证明为m a x s p 一难的【1 9 1 ，即使所有边的权都是1 或 2 因此，满s t e i n e r 树问题只有一些近似算法，关于满s t e i n e r 树问题g u o h u jl i n 和 g u 0 h a n gx u e 给出了第一个近似算法，并证明了它的性能比为p + 2 俐此后，f i i l d l 8 给出了性能比为2 p 的近似算法【2 1 1 后来，m a r t i n e z ，p i n a 和s o a 瑚又给出了性能比为 2 p p ( 3 p 一2 ) 的近似算法【2 2 l ，把性能比从3 1 0 改进到2 5 2 四、本文的组织 本文系统介绍了平面上与图上的s t e i n e r 树问题及它们的研究现状，而后提出了满 瓶颈s t e i n e r 树问题的模型，给出了它的一个多项式时间算法，证明算法的正确性和有 效性总结在h a t m i n g 距离下，在f 1 范数下的反瓶颈支撑树问题，给出满瓶颈s t e i n e r 树问题形式模型，在反瓶颈支撑树问题的基础上给出了反瓶颈s t e i l 埘树问题算法，证 明算法本文的具体安排如下t 第一章引言：介绍s t e i n e r 树及对其研究的意义，简述了s t e i n e r 树的发展现状 第二章满瓶颈s t e i n e r 树问题：提出了满瓶颈s t 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 盯树问题 5 第二章满瓶颈s t e i n e r 树问题 本章将要研究的问题是结合图上的瓶颈s t e i n e r 树问题与满s t e i n e r 树问题，创新 地提出了个新的模型：满瓶颈s t e m r 树问题满瓶颈s t e i n e r 树问题具有瓶颈s t e i i 埘 树与满s t e i n e r 树二者皆有的特点下面将从如下几个方面进行描述：首先给出满瓶颈 s t e i n e r 树问题的概念极其性质，然后给出它的多项式时间算法，证明算法，最后，给 出数值例子加以说明 一、满瓶颈s t e i m r 树问题简述 满瓶颈s t e i n e r 树。给定一个加权无向图g = ( ve ) ，在g 中，对于一个给定点集 t y ( g ) ，求t 的一棵树s ，满足t y ( s ) y ( g ) ，e ( s ) e ( g ) ，要求在树s 中，点 集t 中的点在s 中均为叶子，且最大边权值最小树s 叫t 在g 中的满瓶颈s t e i n 盱 树，t 称作目标点，y ( s ) t 称作瓶颈s t e i n e r 点，y ( g ) t 称作需求点 问题描述：满瓶颈s t e i n e r 树问题是指在给定的一个加权无向图g 中，一个目标点 集t y ( g ) ，求t 在g 中的一棵树s ，要求t 在s 中的点都为叶子，树s 的最大边权 值最小的s t e i n e r 树 这个问题在管理科学中有实际的应用价值它兼有满s t 血l e r 树与瓶颈s t e i n e r 树 的特点( 也就是目标点不仅要是叶子，而且最大边权值要最小) 在人们的实际生活中 它有很大的利用价值，尤其适用于在所有的点中对指定的点有如此要求的情形 定理2 1 满瓶颈s t e i n e r 树中目标点都是叶子，最大边的权值最小 证明：在输出的图g 中，目标点集为t ，s 为t 在g 中的满瓶颈s t e i n e r 树，假设 t 在s 中有不是叶子的点，这与定义矛盾假设s 中最大的边为e t ，去掉e t ，则把s 分 成岛，两部分，这意味着既是连接研，最小的边，否则，存在边e f 连接魏，且 有e ， 龟，这也与定义矛盾，证毕 二、满瓶颈s t e i n e r 树问题算法 通过上面给出的满瓶颈s t e 毗r 树问题的概念，描述及性质，下面给出它的多项式 时间算法 算法2 1 给定一个加权无向图g ，目标点集t = 亡1 ，亡2 ，“) ，其中知i y ( g ) i ( 1 ) 在图g 中，去掉目标点及与目标点相连的边得到图g 1 ( 2 ) 在g 1 中去掉目标点及其与需求点相连的边得到g 2 瓶颈s 蛐树问题 6 ( 3 ) 求出g 2 的最小支撑树岛 ( 4 ) 取出g 1 中任意一个目标点如 七) ，如与需求点相连的边，若只有一条，则直 接将此边连同目标点，按g 中位置加到g 3 中；若多于一条，则任意取出两边按g 中 位置加到g 3 中，那么必形成圈比较圈中各边权值大小，去掉最大权值边若目标点 度数为1 ，那么去掉此最大边，若目标点度数不为1 ，则在任意取出的两边中，其中一边 e 必经过最大权值边才能使其加入原g 3 中连通，即g 3 + e 连通，则删去此边若任取 的两边都不经过权值最大边就能使图g 3 + e 连通，则去掉较大边用此种方法进行， 直到取完g 1 中与此目标点相连的所有需求点 ( 5 ) 同算法( 4 ) ，取完t 中所有的目标点，使其都加到g 3 中，得到g 4 ( 6 ) 如果g 4 中需求点度数都不为1 ，输出g 4 否则，删去任意一个度数为1 的需求 点及其与之关联的边，得到g 5 定理2 2 此算法是正确有效的 证明：首先，算法的第( 1 ) 步先去掉目标点及与目标点相连的边，使目标点只与需 求点相连，算法的第( 2 ) 步中去掉目标点与需求点相连的边后，求需求点的最小支撑 树，由【2 1 】知，最小支撑树必为瓶颈支撑树，保证需求点所构成的树最大边权值最小。 再由算法第( 4 ) 步，使目标点加入瓶颈支撑树后只与一个需求点相连，使目标点一定 为叶子，这是显然的其次证明所求得的s t e i n e r 树最大边权值最小设e i 为算法最 后得到的树中最大边，假设还有另外一棵树，最大边权值为e ，有e j 龟，将勺加入 g 4 中，一定形成圈，并且只有两种可能如果e f 在只有需求点形成的圈中，则与算 法第( 3 ) 步矛盾，如果e ，在需求点与目标点形成的圈中，则e ， o ) 要求毗一如s 嵋姚+ 地，且 【c 一( e ) m a x _ 【叫( e ) 一矿( e ) ，o ) _ 卜c + ( e ) m a x 叫( e ) 一伽( e ) ，o ) 】最小当嘶口) = p 时，就 把这个问题称作z 1 范数下定值p 的反瓶颈支撑树问题 在给出定值p 的反瓶颈支撑树问题的算法前，先引入符号：t 搴) = e pi 伽( e ) p ) ；c ( p ( p ) ) = c 弋e ) 扣( e ) 一p ) ) ，c ( t p ) ) 是令p ) 的最大权值为p 的 e 2 ( 纠 花费； e ( 功= e 刀t + l 钮( e ) p ) ；勺( e ) = c + ( e ) 一彬( e ) ) i e e p ) ，p 一钏( e ) ( e ) ) ； g p ) = ( ve ) ) ；丁表示g 的所有支撑树的集合；t 表示一个支撑树；k 表示支撑 树的一个可行切；j | c 表示可行切的集合 下面引入几个定义。 定义3 1 对于定值p ，如果对每一个e k ，有伽( e ) + t ( e ) p ，那么k 称可行切 定义3 2 对t 丁的支撑树中的边叼，满足加( 叼) + u ( e t ) 2p ，那么p 称作可行 的 算法3 1 令g 为加权无向图，给定g 的一个支撑树t ，修改p 的权值使p 在叫下为瓶 颈支撑树，且使【c 弋e ) m a x ( e ) 一硼( e ) ，o ) + c + ( e ) m a x 伽+ ( e ) 一叫( e ) ，o ) i 最小 ( 1 ) 若e t 白) ，则叫( e ) = p ，c ( t + 0 ) ) 是t 事) 最大权值为p 的花费 瓶颈树问题 ( 2 ) e e ，钮( e ) = p 如果g ) 是不连通的，p 已经是嘶下的瓶颈支撑树，最小 花费为c ( p ( p ) ) ，否则 ( 3 ) 在g 的可行切k 中求它的最小切圈，若e k ，则凹( e ) = p g ( k ) = 印( e ) ) e 耳( p ) p 在给定值p 下的最优解咖= c ( p ( p ) ) + q 僻) ( 二) 有边界限制的2 ，范数下的反瓶颈支撑树问题 从前文可知，最优解矿对应一个值p 。，在可行值p 的所有花费咖( p ) 中，咖铲) 是 最小的现在的目标是如何找到这个矿下面给出命题 命题3 1 型p s 伽( t + ) ，其中型= m 8 x 钮( t + ) ，m 8 x ( e ) 一z ( e ) ie t ) ) ，t + 为g 在权伽下的瓶颈支撑树 命题3 2g + 0 ) 是一个非减函数 命题3 3 如果存在歹，瓠+ 1 ) ，满足c + ) 0 定理3 1 个s t e i n e r 树s 在权向量伽下是一个瓶颈s t e i n e r 树当且仅当删去不小 于伽( s ) 的边，存在目标点与其它目标点不连通，不能生成s t e i i l e r 树 证明。假设当删去不小于伽( s ) 的边存在s t e i n e r 树扩，叫( s 悻) 伽( s ) ，显然s t e i n e r 树s 的最大边权值不是最小的，与瓶颈s t e i n e r 树定义相矛盾当叫( ) 叫( s ) 时， 与假设条件矛盾，所以假设不成立，得证 设矿为硼下的瓶颈s t e i n e r 树，一定有t l ，( 伊) 伽( 矿) ，否则，埘( 伊) 叫( 矿) ，则 扩已经为伽下的一个最优解下面给出矿( 扩) 的一个范围 定理3 2 叫。( s ) 伽( s + ) 证明t 事实上。如果钮( 舻) ( 酽) ，我们能够构造一个新的权向量萄，当e s 、 t u + ( e ) 伽( 矿) 时，丽( e ) = 伽( 伊) ，否则，面( e ) = 伽+ ( e ) ，很明显有峦( s 4 ) = 伽( 舻) 此外，对 于任给的一个s t e i n e r 树s 有钮幸( s ) 钮( ) ，设对任一e s s 满足矿( e s ) = 矿( s ) ，那 么有：如果铅g 伊，则面( e s ) = 矿( e s ) = 伽( s ) 伽( s ) ；如果e s ，则面( e s ) = 们( s 。) 因此，西( s ) 西( 舻) 所以西也是一个最优解，显然，虿的花费少于镏，与钮。是最 优解矛盾，得证 另一方面，我们有 定理3 3 硼( s + ) 硼。( s ) 证明t 设伽( s + ) = p ，叫( s ) = r p 7 然后证明出矿不是最优解，进而得出矛盾设 q p = e s l 叫( e ) p ) q 1 = e s i 硼( e ) 下) 1 1 瓶颈s 蛐树问题 在p 1 - 的情况下，显然有q r ，现在调整埘到蜘，花费为伊，对于那些e 嘶的 r 来说，它至少包括锄( e ) 到矿( e ) 的减少花费，而 伊 c - ( e ) ( e ) 一下) ) c - ( e ) ( e ) 一p ) 下面我们定义西为 酢，= 嚣 对于每个s t e i n e r 树s ，若伽( s ) p ，我们记为仍( s ) p ，另一方面，由仍的定义，有 面( 舻) = p ，也就是说在西下，扩成为最小权s t e i n e r 树，从锄到西调整花费，记为d ， 有 c = c 一( e ) ( 西( e ) 一力) c 与叫搴是最优解矛盾 此外，因为随着权值的减小，有更小的界叫( 舻) 最小的可能值为m a x 伽( e ) 一z ( e ) f e ) ，箜= m x 伽( 矿) ，m a x 扣( e ) 一z ( e ) le s ) ) 从以上分析得到亚s 矿( 扩) 脚( 扩) ( 二) 定值p 的z ，范数下的反瓶颈s t 血e r 树问题 在考虑如何直接解反瓶颈s t e i n e r 树问题之前，先研究一个“限制版本，的反瓶颈 s t e i n e r 树问题 我们仅需在世，叫( 舻) 】范围内研究在给出“限制版本值p 的反瓶颈s t e i n e r 树问 题之前，给出几个定义 定义3 4 对于一个给定的值p ，在权向量加一下使得伊成为一个瓶颈s t e i n e r 树， 不仅要满足唧( ) = p ，而且唧要满足边界限制，还要满足修改的花费值最小我们 把这个反瓶颈s t e i n e r 树问题称作值p 的2 1 范数下的“限制版本的反瓶颈s t e i 舶r 树 问题 定义3 5 在图g ( p ) 中如果删去边集k ( k y ( g ) ) 中的边，那么有一个目标点不 能与其它的目标点连通，则边集k 称作此目标点的切 定义3 6 在可行切k 中，对于值p ，有伽( e ) + u ( e ) p ，则切k 叫可行切权值和 最小的切称作最小切 定义3 7 如果每个s t e 蛔树s 5 包括一条边e s ，有加( e s ) + u ( e s ) p ，那么p 称作可行的 瓶颈s 蛐树问题 定义3 8g 是无向图，u ：e ( g ) 一j 4 是容量函数，r 是个树，如果y ( 刁= y ( g ) ， 且 k = e 醴。) u ( 倪) ) 8 ，亡y ( g ) 则t 被称作( g ，) 的舶m o 妒h u 树，其中只t 是t 中的( 唯) 8 一t 一路，而倪和 y ( g ) 倪( e e ( t ) ) 是t e 的连通分图 通过g o m o 驴h u 树的定义我们可以知道，g 伽时h u 树就是求g 的一个树t ，满 足t 中的点与g 中的点相同，树中的边权为每个点不能与其它点连通的最小容量和 若g 中的边表示权值，那么t 中的边权表示每个点最小切的权值和 下面给出反瓶颈s t e i n e r 树问题的算法 算法3 2 给定加权无向图g ，给出一个树s 悻，树伊包含奄个目标点，z 个s t e i n e r 点修改 s 的权值使其在叫+ 下为瓶颈s t e i n e r 树 ( 1 ) 令国) = e 扩l 彬( e ) p ；若e 伊，则钮( e ) = p ，g ( 酽) = c 一( e ) ( e ) 一p ) ie 舻白) ) ，c ( 扩) ) 是舻( p ) 的最大权值为p 的花费 ( 2 ) q 表示对于p 不可行的边的集合，e e = e ei 铆( e ) p 设 g 0 ) = ( ve ) q ) ，如果g ( p ) 中不能生成s t e i n e r 树，那么伊已经是嘶下的瓶 颈s t e i n e r 树，最小花费为c ( ) ，否则计算e 中每条边的花费，记为勺( e ) ，并将 唧( e ) 作为e ) 中每条边的权值 ( 3 ) 求g ) 的g o m 咿h u 树，得到目标点赴的最小切致，若e 段，则凹( e ) = p q ( 硒) = c + ( e ) ( p 一伽( e ) ) ie 甄) ( 4 ) 计算m i n q ( 甄) 则s + 在p 下的最优解为) = c ( ) ) + m i n q ( k ) 定理3 4 此算法是正确的，算法时间复杂性为d ( 佗4 ) 证明。首先证明算法是正确的在定值p 下，算法的第( 1 ) 步求出s t e i n e r 树矿 中边权大于p 的修改费用，由定理3 1 可知，如果g ) 中不能生成s t e i n e r 树，那么 已经是嘶下的瓶颈s t e i n e r 树，算法结束否则，修改e ) 中每条边的花费，记为 勺( e ) ，并将勺( e ) 作为e ( p ) 中每条边的权值，求g 0 ) 的g 0 m o 妒h u 树【如，4 1 l ，求出每个 目标点不与其它目标点连通的最小权值和，即目标点的最小切删去任一个目标点最 小切中的边，此目标点就不能与其它目标点连通，就不能生成s t e i n e r 树，所以通过第 ( 4 ) 步，求出所有目标点的最小切对应的修改费用的最小值，就是在定值p 下伊为瓶 颈s t 咖e r 树的最小花费然后证明算法的复杂性第一步时间复杂性为d ( k + 2 1 ) ， 第( 2 ) 步与第( 3 ) 步最多需要的时间为o ( n 4 ) ，第( 4 ) 步的时间为o l c 愕t ) ，所以此算法 1 3 瓶颈s 妇树问题 的时间复杂性至多为d ( 一) ( 三) z - 范数下反瓶颈s t 咖e r 树问题算法 现在开始求p 在给定范围内的反瓶颈s t e i n e r 树问题的方法 从前文可知，最优解矿是一个值p + ，满足型伽。( 扩) 彬( 9 ) ，在可行值p 所有 的花费白) 中) 是最小的现在的目标是如何找到这个p 用c + ( p ) 表示给定p 值时s t e i n e r 树舻的最小花费由前文可知，如果g 中不 能生成s t e i n e r 树，伊已经是唧下的瓶颈s t e i n e r 树，那么c + = o ；如果g ) 能 生成s t e i i l e r 树，那么c + p ) = q 僻) ，其中它包括一种特殊情况，也就是没有可行 切，则c + 白) = q ( k p ) ) = + o 。 显然地，如果。僻) = + o o 那么对于任意的q p ，有c + ( 口) = + o o 但是如果 有一个值p 满足g + ( g ) = + ，则不必在眵，叫( 舻) 】间找值 考虑到p 掌需要在原来权值间与陋，伽( s ) 】范围内搜索，也就是集合( 伽( e ) ie 研u 伽( e ) + u ( e ) ie e u 地 ) n 陋，伽( 伊) 】，用非降序将这些值排序，记做业= 9 1 q 2 铂， q d = 伽( 扩) ，这里每个弛( 凫2 ) 对应一条边有钮( e ) = 讯或硼( e ) + “( e ) = 瓠，可 得 定理3 5c + ) 是一个非减函数 证明：考虑两个值 o ，c + + o o 考虑可行切k ，令b = e k 仞) i 硼( e ) p ，所以b 是g 0 ) 的一个可行切因此可以得到，q ( k ) q ( b ) ( b ) q ，倦) ) ，即c + c + ) ，证明c + 是一个非减函数，得证 定理3 6 如果存在，弧+ 1 ) ，满足c + ) + o 。，那么对任意的p ，弧+ 1 ) ， 有c + ( p ) + o 。此外，在，弧+ 1 】上c + 是一个凹函数，有l i m c + ) c + ) p q z 证明；假设存在歹，鳜+ 1 ) ，满足o 伊) + o o ，因为c + 0 ) 是一个非减 函数，则有c + ( 口七) + 。o 对任意的p ( 饥，讥+ 1 】，通过 瓠)