（运筹学与控制论专业论文）块图的中位问题与中心问题.pdf

原创性声明 i l l l l l f f f l l l l l l l l l f l l i j i l l l l f l l l l l l r f l i l l l y 17 4 10 5 7 本人声明：所呈交的论文是本人在导师的指导下进行的研究工作除了文中特 别加以标 参与同一 并表示了 本人 文及送交 内容 上海大学理学硕士学位论文 块图的中位问题与中心问题 硕士生：张晓芹 导师：单而芳 专业：运筹学与控制论 上海大学理学院 二零一零年四 ad i s s e r t a t i o ns u b m i t t e dt os h a n g h a iu n i v e r s i t yf o rt h e d e g r e eo fm a s t e ri ns c i e n c e m e d i a np r o b l e ma n dc e n t e rp r o b l e m o nb l o c kg r a p h s m d c a n d i d a t e ：z h a n gx i a o q i n s u p e r v i s o r ：p r o f s h a ne r f a n g m a j o r ：o p e r a t i o n sr e s e a r c ha n dc y b e r n e t i c s t h ec o l l e g eo fs c i e n c e s h a n g h a iu n i v e r s i t y a p r i l ，2 0 1 0 2 0 1 0 上海大学硕士学位论文 摘要 网络选址问题作为运筹学的一个重要分支，在运输、通信以及计算科学等诸 多领域发挥着巨大作用1 9 0 9 年德国经济学家w e b e r 发表的工业区位选址论文标 2 0 1 0 上海大学硕士学位论文 i i a b s t r a c t a sab a s i cb r a n c hi no p e r a t i o n sr e s e a r c h ，l o c a t i o np r o b l e mo nn e t w o r k sh a sp l a y e d a ni m p o r t a n tr o l ei nm a n yf i e l & s u c ha st r a n s p o r t a t i o n ，c o m m u n i c a t i o na n dc o m p u t e r s c i e n c e s g e n e r a l l ys p e a k i n g ，m o d e r nl o c a t i o nt h e o r yo r i g i n a t e df r o mw e b e r st r e a t i s eo n t h el o c a t i o no fi n d u s t r i e si n1 9 0 9 h o w e v e r ，i tw a sn o ts y s t e m a t i cu n t i lh a k i m ip u b l i s h e d t h ef i r s tp a p e ro nt h el o c a t i o no fm u l t i p l ef a c i l i t i e si n1 9 6 4 i nt h ep a p e r ，h a k i m d i s - t i n g u i s h e dt w ok i n d so fm i n i m i z i n go b j e c t i v e s ：m i n i s u m ，t h es t a n d a r de f f i c i e n c ym e a s u r e a n dm i n i m a x ，t h es t a n d a r de q i l i 锣m e a s u r e f o rm a n yy e a r sh e n c e ，m a n yr e s e a r c h e r s h a v ed e v o t e dt h e m s e l v e st od e v e l o pn e wm o d e l sf o rl o c a t i o np r o b l e m s t h ec l a s s i c a lp - m e d i a np r o b l e ma n dp - c e n t e rp r o b l e ma r et w ot y p i c a lm o d e l si nt h i s l i n eo fi n v e s t i g a t i o n t h ep - m e d i a np r o b l e mi sc o n c e r n e dw i t ht h el o c a t i o no fpf a c i l i t i e s o nt h en e t w o r k ，s u c ht h a tt h et o t a l ( w e i g h t e d ) d i s t a n c eo fa l lt h ec u s t o m e r st ot h e i r r e s p e c t i v en e a r e s tf a c i h t i e si 8m i n i m i z e d t h ep - c e n t e rp r o b l e mi sc o n c e r n e dw i t ht h e - - l o c a t i o no fpf a c i l i t i e so nt h en e t w o r k ，s u c ht h a tt h ei n a x i i n u i n ( w e i g h t e d ) d i s t a n c eo fa l l t h ec u s t o m e r st ot h e i rr e s p e c t i v en e a r e s tf a c i l i t i e si sm i z l i m i z e d i nb o t ht h ec l a s s i c a lp - m e d i a np r o b l e ma n dp - c e n t e rp r o b l e m ，a l lt h ec u s t o m e r s c o n s i d e rt h ef a c i l i t yd e s i r a b l ea n dt r yt oh a v ei ta sc l o s ea sp o s s i b l et ot h e i ro w nl o c a t i o n w h e r e a si ft h ef a c i l i t i e ss u c ha sn u c l e a rr e a c t o r sa n dd u m ps i t e sa r eo b n o x i o u sf o ra l l c u s t o m e r s ，t h a ti st os a yt h a tt h ef a c i l i t i e ss h o u l db ep l a c e da sf a ra w a ya sp o s s i b l ef r o m t h ec u s t o m e r s ，t h e nw eo b t a i nt h eo b n o x i o u sf a c i l i t yl o c a t i o np r o b l e m am o r eg e n e r a l p r o b l e mi st h es e m i - o b n o x i o u sf a c i l i t yl o c a t i o np r o b l e m ，w h e r et h ef a c i l i t yi sf r i e n d l yf o r ap a r to ft h ec u s t o m e r sa n do b n o x i o u sf o rt h eo t h e rp a r t i nt h i sp a p e r ，w em a i n l yc o n s i d e rm e d i a np r o b l e ma n dc e n t e rp r o b l e mo nb l o c k g r a p h s t h ec o r r e s p o n d i n gr e s u l t sa r et h ef o l l o w i n gt w op a r t s ： i nt h ef i r s tp a r t ( c h a p t e r3 ) ，w ef u r t h e rp r o v et h a te v e nt h o u g ht h ec u s t o m e r sa r e n o tv e r t i c e sb u ts u b g r a p h s ，t h ev e r t e xo p t i m a l i t yp r o p e r t ys t i l lh o l d sf o rt h ec l a s s i c a l p - m e d i a np r o b l e mo ng e n e r a l 伊a p h s b e s i d e s ，w ea l s oc o n s i d e rt h es e m i - o b n o x i o u s1 一 m e d i a np r o b l e mo nb l o c k 窜a p h sw i t hs u b g r a p h - s h a p e dc u s t o m e r s u n d e rt h ec o n d i t i o n t h a tt h eb l o c kg r a p hh a su n i te d g el e n g t ha n dt h em e d i a ni sr e s t r i c t e dt ot h ev e r t e xo f t h eb l o c kg r a p h ，t h ep r o b l e mc a nb es o l v e di nl i n e a rt i m e i nt h es e c o n dp a r t ( c h a p t e r4 ) ，w es h a l la n a l y z et h eu n w e i g h t e d1 - c e n t e rp r o b l e m 2 0 1 0 上海大学硕士学位论文 i i l o nb l o c kg r a p h sw i t hu n i te d g el e n g t h b yu s i n gt h et r e es t r u c t u r eo fab l o c kg r a p h ，w e p r e s e n tal i n e a rt i m ea l g o r i t h mf o rt h ep r o b l e m k e yw o r d s ：l o c a t i o np r o b l e m o nn e t w o r k s ；s e m i - o b n o x i o u sm e d i a np r o b l e m ；c e n t e r p r o b l e m ；b l o c kg r a p h ；a l g o r i t h m 2 0 1 0 上海大学硕士学位论文 i v 目录 摘要i a b s t r a c t i i 第一章引言1 1 1 网络选址问题的研究背景及进展1 1 2 中位问题与中心问题的研究背景及模型2 1 2 1 经典中位问题和中心问题2 1 2 2 厌恶型中位问题和中心问题3 1 2 3 半厌恶型中位问题和中心问题4 1 3 本文的主要内容5 第二章基本符号和主要研究进展7 2 1 基本概念和记号7 2 2 几类图上中位问题的主要研究进展9 2 3 几类图上中心问题的主要研究进展1 4 第三章基于子图结构客户的中位问题1 7 3 。1 一般图上以子图为客户的经典p 中位问题1 7 3 2 块图上以子图为客户的半厌恶型1 中位问题1 9 3 2 1 基本概念和问题模型1 9 3 2 2g - p i e c e 中的局部最优解2 2 3 2 3c - p i e c e 中的局部最优解2 5 3 2 4 块图中的全局最优解：2 7 第四章块图上的无权1 一中心问题3 2 第五章结论与展望3 6 参考文献3 7 作者攻读硕士学位期间公开发表的论文4 3 致谢4 4 第一章引言 选址问题是研究将设施放置在什么地方最佳的问题例如银行设在什么位 置，服务效果最好；垃圾场设在何处，使其对居民生活影响最小；矿区的选矿场 设在何处，才能使各采矿点输送矿石的总运输费用最少等等选址问题在生产、 生活、物流、甚至军事领域中都有着非常广泛的应用从而，选址问题的研究具 有重大的社会、经济和军事意义 1 1 网络选址问题的研究背景及进展 选址问题是一个十分古老而又经典的问题古代的选址决策往往以经验、制 度甚至迷信思想为依据，缺乏科学性现代的选址问题是由德国土地经济学家和 区域地理学家w e b e r 于1 9 0 9 年提出的他研究了如何确定一个仓库的位置，使得 仓库到多个客户之间的总运输距离最短，并发表了工业区位论文该论文被认为 是最早的设施选址论文，它的发表标志着选址问题进入到了科学研究的时代另 一个较早的选址问题是由h o t e l l i n g 于1 9 2 9 年提出的，主要考虑一条直线上的两 个竞争供应商的选址随后许多学者如s m i t h i e s ( 1 9 4 1 ) 、l o s c h ( 1 9 5 4 ) 、v a l i n s k y ( 1 9 5 5 ) ，i s a r d ( 1 9 5 6 ) 、m a n s f i e l d ( 1 9 5 8 ) 和s t e v e n s ( 1 9 6 1 ) 等对选址问题都进行了 更深入的研究不过，1 9 世纪6 0 年代中期以前，大多数的研究工作是在几个不 相关的领域内展开的，内容比较零散，选址理论并没有真正形成直到1 9 6 4 年， h a k i m i 通过研究通讯网络中交换中心位置的确定问题和高速公路网络中警察局布 局的问题，发表了网络多设施选址论文该论文是选址问题发展为一个系统、科学 理论的重要里程碑，大大激发了选址问题的理论研究 网络选址是选址问题的一个重要分支，一般是指如下的问题：假设某市有多 个特殊部门，如交通枢纽、海港口、零售商店等，如果将它们看作网络的顶点，连 接它们的道路看作网络的边，那么整个城市就可以抽象为一个无向网络问题的 目标就是在网络中为新建设施寻找最佳的放置地点，使得在满足客户需求的基础 上，费用函数达到最优不同问题的费用函数以及最优性的定义往往不同，但在某 种程度上，这些问题至少存在一个共同点，即满足这些客户的费用依赖于客户与 2 0 1 0 上海大学硕士学位论文 2 设施间的距离，且这个距离按照网络中的最短路进行计算【3 9 】 网络选址问题在物流设施规划、通讯系统设计等诸多领域具有十分广阔的应 用背景从上世纪6 0 年代以来，网络选址问题的研究范围和模型不断拓展，在理 论和实践方面均取得了许多优秀的研究成果，如g o l d m a n ( 1 9 7 3 ) 研究了网络中心 问题；d e a r i n g ( 1 9 7 4 ) 研究了网络上的最大距离最小问题；c h u r c h ( 1 9 7 8 ) 研究了在 网络上布局一个有害设施的问题，运用的准则是使所有客户到设施的加权距离之 和最大；b r a n d e a u 和c h i u ( 1 9 8 9 ) 考虑到实际生产、运输时间、需求量等不确定性 因素，研究了动态网络选址问题模型；d r e z n e r ( 1 9 9 5 ) 研究了条件中位问题，又称 p q 中位问题，即网络中已存在q 个服务设施，如何为p 个同类服务设施选址的 中位问题；t a m i r 等( 1 9 9 8 ) 研究了服务设施选址的双目标模型，即综合考虑中位 问题和中心问题的目标函数，并将它们转化成参数为入的c e n t d i a n 单目标模型； b u r k a r d ( 2 0 0 3 ) 则考虑了树上的半厌恶型中心问题对网络设施选址问题的全面研 究进展，可参考文献【7 ，2 4 ，2 6 ，5 2 ，5 6 ，5 7 ，6 1 j 1 2中位问题与中心问题的研究背景及模型 中位问题和中心同题是网络选址问题中的两类基本模型，其它许多问题都是 在这两类问题的基础上，设置不同的条件进一步扩展得到的下面将对中位问题 与中心问题的研究背景和模型进行回顾 1 2 1 经典中位问题和中心问题 h a k i m i 于1 9 6 4 和1 9 6 5 年，分别在文献【3 5 】和【3 6 】中首次提出服务型设施选 址的中位问题和中心问题经典p 中位问题( c l a s s i c a lp - m e d i a np r o b l e m ) ，也称最小 和( m i n i s u m ) 问题，是指在给定客户集合及其需求量的条件下，分别为p 个设施找 到合适的位置，使得全部( 平均) 性能达到最优，如使总成本最小、总运输费用最小 或使总需求加权距离最小等而经典p 中心问题( c l a s s i c a lp - c e n t e rp r o b l e m ) ，也称 极小化最大( m i n i m a x ) 问题，是指在网络中放置p 个设施，使得最坏的 优，如使最大反应时间最小、最大运输费用最小或使最大需求加权距 这里的需求加权距离指客户的需求量和该客户到最近服务设施的距离 2 0 1 0 上海大学硕士学位论文 3 上述两个问题用图论的语言可表述为：设g = ( k e ) 是一个连通无向图，其 中y 为顶点集，i v i = n 为顶点数，e 为边集，i e i = m 为边数每个顶点优v 被视为一个客户，并具有非负权重t i 每条边碲e 的长度为正实数d ( u ，u ) 表 示g 中任意两点让，t ，间最短路的长度 ( 1 ) p - 中位问题：寻找子集砗= 【ql1 歹p ) 冬g ，最小化目标函数 f 1 c x p ) 2 ；t r a 9 i 9 n ( w i d ( 狮” ( 1 2 1 ) ( 2 ) p - 中心问题：寻找子集耳= 【i1 歹p ) 冬g ，最小化目标函数 ，( 而) 2 l m s t a s x n w i l r a g i n p d ( 巧，地) ( 1 2 2 ) 注：i ) j g 表示曷中的点可能是g 的顶点，也可能是g 的边上的一内点 2 ) p - 中位问题、p 中心问题的最优解依次称为问题的p 中位、p 中心 3 ) 若中心问题模型中所有顶点的权重都相等，则称其为无权中心问题 经典中位问题主要从服务设施对公众的。效益性”角度考虑，在点网络中心的 确定、计算机网络中服务器的配置、物流中心的选择等方面均有重要的实用价值 而中心问题则是从服务设施对公众的“公平性”角度考虑，通常在军队、医院、紧 急设施和有服务承诺的行业中使用 1 2 2 厌恶型中位问题和中心问题 经典中位问题和中心问题以方便客户为目的，使设施到客户间的距离越近越 好然而有些设施，如垃圾处理厂、化工厂、核电站等则令所有客户都感到厌恶，这种 设施放置的越远越好研究此类设施的问题称为“厌恶型设施选址问题”( o b n o x i o u s f a c i l i t yl o c a t i o np r o b l e m ) 关于该类问题的进一步讨论与分类，可参阅文献( 1 7 ，4 7 ， 5 3 】由c h u r c h 和g a r i l n k e l 2 1 】首次提出并研究的p - m a x i a n 问题属于厌恶型p 中 位问题( o b n o x i o u sp - m e d i a np r o b l e m ) 之一，指在含有n 个客户的网络中放置p 个 设施，使得所有客户到离其最远的设施的加权距离之和最大而厌恶型p 中心问 题( o b n o x i o u sp - c e n t e rp r o b l e m ) 是指在网络中放置p 个设旌，使得客户到离其最近 的设施的最小加权距离最大 用图论的语言来描述上述两个问题： 2 0 1 0 上海大学硕士学位论文 4 ( 1 ) p m a z d a n 问题：寻找子集曷= 巧i1 歹p ) g ，最大化目标函数 f 2 c x , , ) 2 挑臻d ( 吻，仇) ( 1 2 3 ) ( 2 ) 厌恶型p 中心问题：寻找子集墨= 巧i1 歹p ) g ，最大化目标函数 g ( x p ) 2 l r a 0 ，仇亿的权重姚 0 是任意常数函数 他) 2 麟挑配耽) ， 夕0 ) = m + 嚣凝姚d ( z ，挑) 表示紧急事件发生时，友好型客户的服务费用和厌恶型客户的损失半厌恶型1 中心问题为寻找点z g ，最小化目标函数 e ( z ) = p f ( z ) + q 9 ( z ) ( 1 2 6 ) 半厌恶型设施选址问题在现实生活中具有广泛的应用背景例如，b a n ka c c o u n t 选址问题【2 3 】是m w d 问题的个实例；而n i m b y ( n o ti nm yb a c ky a r d ) 问题则 是w m d 问题的一个实例半厌恶型1 一中心问题对学校、超市等设施的选址具有 一定的指导意义 以上考虑的所有问题中，客户或设施均由网络的( 顶) 点表示，然而有些大规 模的( e x t e n s i v e ) 客户或设施无法简单地用一个点来表示因此，在网络中放置形如 路、子树等客户或设施的选址问题【2 2 ，5 1 ，驯已成为诸多学者关注的焦点 2 0 0 9 年，程郁琨和康丽英【2 0 】首次建立了树上以子树为客户的半厌恶型p 中位问题模 型本文将在第三章研究此类问题，这里不再赘述 1 3 本文的主要内容 由于一般图上的中位问题与中心问题是n p 一困难的【叫，所以到目前为止，网 络选址问题的研究主要集中在以下几个方面： ( 1 ) 一般图上近似算法的设计与改进； 2 0 1 0 上海大学硕士学位论文 6 ( 2 ) 研究树、仙人掌图、块图等特殊图的结构性质，设计多项式时间算法； ( 3 建立新的问题模型，如考虑非线性的费用函数以及多目标、不确定性等选 址问题更有实践价值 本文主要研究块图的中位问题与中心问题，相应的结果总结为如下两部分： 第一，证明了即使客户是子图结构，而非图的顶点，一般图上的经典p 中位 问题仍满足顶点最优性此外还对块图上以子图为客户的半厌恶型1 一中位问题进 行了研究，证明了若块图的边长为1 且中位限制到块图的顶点处，则该问题在线 性时间内可得以解决 第二，探讨了边长为1 的块图上的无权1 中心问题，借助于块图树结构的性 质，给出了该问题的一个线性时间算法 第二章基本符号和主要研究进展 该文在上一章回顾了网络选址问题的研究背景及进展，介绍了中位问题与中 心问题的各种模型本章将给出一些基本概念和记号，并总结出几类图上关于中 位问题与中心问题的主要研究进展 2 1 基本概念和记号 本文中所有符号若无特别说明，均按如下定义凡是文中未加定义的术语和 符号，可参著作 6 】设g = ( ke ) 是个无向图，v ( g ) 和e ( g ) 分别表示图g 的 顶点集和边集，n = i y ( g ) i 表示图g 的顶点数，m = i e ( g ) l 表示图g 的边数如 果v ( a ) 和e ( g ) 均为有限集，则称图g 为有限图如果图g 的任意两个顶点之 间至多有一条边，则称该图为简单图本文所讨论的图均是有限、简单、无向图 设点z g 表示z 是g 的顶点或是边上任一内点，尸g ( z ，y ) 表示g 中连接点z 和y 的最短路，d g ( z ，y ) 表示z 和y 两点间的距离，即p a ( x ，y ) 的长度若f b ( z ，y ) 不存在，则定义d g ( z ，! ，) = 在图g 比较明确的情况下，可将p g ( z ，可) 和d g ( z ，y ) 简写为p ( x ，y ) 和d ( x ，! ，) 若对图g 中任意两个顶点z 和! ，均有d ( x ，秒) 0 ，一个算法能在k n 时间内处理完输入数据量为他的问题，就说这个算法的时间复杂性是d ( 他) ，或者 说该算法的运行时间为线性时间 定义2 1 7 ( 6 8 】) 设f ( n ) 与g ( n ) 为自然数，l 的两个函数，令舰f ( n ) l g c n ) = l 如果 ( i ) l = 口，n 为有限正常量，则称f ( n ) 与g ( n ) 同量级 ( i i ) 二= 0 ，则称f ( n ) 的量级比g ( 仃) 的量级低 ( 饿) l 一。，则称c ( n ) 的量级比f ( n ) 的量级低 对于某个问题而言，算法的时间复杂性函数的量级越低，说明算法的效率越 高如果一个算法的时间复杂性是以多项式为界的，则称其为有效算法 鉴于以后的章节中反复提到深度优先搜索法的概念，下面对其进行简单介绍 2 0 1 0 上海大学硕士学位论文 9 算法的思路是：首先选定图g = ( ve ) 中某一顶点v 0 作为起始点，设( v 0 ，牡) 是图中的一条边，于是沿着边( 0 0 ，u ) 搜索到顶点u ，设( t ，伽) 是与u 关联且没有搜 索过的边，于是又沿着这条边搜索到顶点t l ，再从叫出发重复上述过程一般来 说，设z 是最新搜索( 访问) 的顶点，如果与z 相邻的顶点y 尚未被访问过，则可 沿边( z ，y ) 访问到顶点可，如果与z 相邻的所有顶点都被访问过，则退回到访问z 的前个顶点( 称为z 的先驱点) ，再重复上述过程，如此继续下去，直到所有被访 问过的顶点的邻接点都已被访问为止用这种搜索方法去遍历图，就称为深度优 先搜索法( d e p t h f i r s t - s e a r c hm e t h o d ) 【6 8 1 如果图的贮存结构采用邻接表，则深度优先搜索的算法步骤如下：设 均：起始点 p ( ”) ：t ，的先驱点 t o o ： 1 3 的标号，若 已被访问，则l ( v ) = 1 t ：输出的图 l ( 口) ：无向图g 中每个顶点口的邻接表 1 ) t 卜o ，对所有的t 7 kl ( v ) 卜0 ，p ( v ) + _ 0 ，p ( v o ) 一v o ，t ，卜v 0 ，i 卜0 2 ) z ( t ，) 卜1 3 ) 对l ( v ) 的每个顶点t i ，若都有z ( t | ) = 1 ，则转5 ) ，否则 4 ) l ( v ) 中存在顶点t ，z ( t i ) = 0 ，则t 卜t u ( t ，u ) ) ，i 卜i + i ，p ( u ) 卜t ，u 卜t ， 转2 ) 5 ) 若i = n 一1 ，则输出t ，停机否则，t 7 卜p ( t ，) ，转3 ) 2 2 几类图上中位问题的主要研究进展 1 9 7 9 年，g a r e y 和j o h n s o n 3 2 】通过计算所有可行解的目标函数值，证明了当 p 是某个确定的整数时，一般图上的经典p 中位问题可以在多项式时间内解决 然而当p 为任意整数时，k a r i v e 和h a k i m i 【4 4 】则证明了即使在最大度为3 的平面 图上，经典矿中位问题也是n p 一困难的此外，一般图上的厌恶型与半厌恶型p 中位问题也是n p 一困难的因此，许多学者致力于某些特殊图上的多项式算法研 究本节仅对树、块图、仙人掌图上中位问题的主要研究进展进行总结 1 顶点最优性 2 0 1 0 上海大学硕士学位论文 1 0 顶点最优性，也称h a k i m i 特性，是指存在一个问题的最优解使其完全由图的 顶点构成这种性质可大大缩小最优解的搜索范围，提高算法的效率下面将介绍 有关顶点最优性的结论 1 9 6 5 年，h a k i m i 【3 6 1 考虑了一般图上的经典p 中位问题，首次证明该问题满 足顶点最优性 2 0 0 0 年，b u r k a r d 等【8 考虑了树上的半厌恶型p 中位问题，得出即使所研 究的图是一条路，w m d2 中位问题也不满足顶点最优性而树上m w dp - 中位 问题却满足顶点最优性 2 0 0 8 年，b u r k a r d 和h a t z l 进一步刻画了一般图上m w dp - 中位问题的解的 特征 定理2 2 1 ( f 1 4 】) 设图g = ( v , e ) 是一个连通无向图，每个顶点t ，的权重饥为任 意实数图g 上的m w dp 中位问题存在一个最优解x = z l ，唧) ，使得每个 点露x 满足下列条件之一： 1 ) 毛y ； 2 ) 甄是某条边( r s ) e 上的一个内点，且存在一个权重为负的顶点t ，v ，使得 d ( t ，r ) + d ( r ，z ) = d ( 钐，s ) + d ( 8 ，z i ) 2 0 0 9 年，程郁琨和康丽英首次提出并研究了客户为子树结构的半厌恶型中位 问题，并得到了如下结果 定理2 2 2 ( 【2 0 】) 设t 是一棵树，五( 1 t t ) 是t 的子树且其边界点均为t 的 顶点，则t 上以正( 1 i t ) 为客户的m w dp 一中位问题满足顶点最优性 2 树上中位问题的主要结果 首先介绍树上经典中位问题的研究现状 针对树上经典的1 - 中位问题，h u a 于1 9 6 1 年在文献【4 0 】中首次进行了探讨 1 9 7 1 年，g o l d m a n 证明了下述两个定理，并为该问题设计了一个线性时间算法 定理2 2 3 ( 【3 4 】) 树上j 一中位问题的解与边长无关，只依赖于顶点权重的大小 定理2 2 4 ( 【3 4 】) 对树t 的任意顶点u ，设其度d ( v ) = 七，z l ，z 2 ，x k 是与t i 相邻 的后个顶点若树以v 为根，则得到分别以。1 ，x 2 ，z k 为根的t 的子树乃，乃， 2 0 1 0 上海大学硕士学位论文1 1 t k w ( 正) 表示子树正的所有顶点的权重之和，w = t - klw ( 互) 顶点u 是t 的 一中位当且仅当所有子树的权重) 不超过w 2 ：i i l a x 彬伍) w 2 1 i l k 针对树上经典的参中位问题，g a v i s h 和s r i d h a r 于1 9 9 5 年证明了下述定理 定理2 2 5 ( 3 3 j ) 设口，b v 是树t 的咎中位，路p ( a ，b ) 的中点m a b 在边e = ( r ，s ) 上若从t 中去掉边e ，t 1 和死是包含顶点a 和b 的两棵子树，则a 是丑 的中位，b 是死的中位 因此，通过删除树的一条边得到两个子树，并在这两棵子树上分别求1 中位可解 决树上经典的二中位问题采用这种删边思想，g a v i s h 和s r i d h a r 给出了一个复 杂性为o ( nl o gn ) 的算法1 9 9 6 年，a u l e t t a 等【2 j 证明了该问题可在d ( n ) 时间内 求解 针对树上经典的p 中位问题，p 3 ，k a x i v e 和h a k i m i 于1 9 7 9 年在文献阻】 中给出了个o ( p 2 n 2 ) 时间的算法1 9 9 6 年，t a m i r 【5 8 】把算法的复杂性改进到了 o ( 即2 ) 2 0 0 5 年，b e n k o c z i 和b h a t t a c h a r y af 3 】又为该问题设计了个o ( nl o g o + 2 ) n ) 时间的算法 下面综述关于树的p - m a x i a n 问题的主要结果 1 9 6 8 年，z e l i n k a 【6 5 】首次研究了树上的1 - m a x i a n 问题，断言叶子集合包含了 问题的最优解1 9 8 4 年，t i n g 【6 2 j 则给出了求解该问题的个线性时间算法 2 0 0 7 年，b u r k a r d ，f a t h a l i 和k a k h k i 基于顶点最优性，研究了树上的p - m a x i a n 问题，得到下列结果 定理2 2 6 ( 【1 2 】) 若p ( o ，6 ) 是树t 的一条最长路，则端点d ，b 是t 上2 - m a x i a n 问 题的一个最优解 推论2 2 1 ( 【1 2 】) 树上2 - m a x i a n 问题的解不依赖于顶点的权重换句话说，所有 正的顶点权重均可得到相同的最优解 定理2 2 7 ( 1 2 1 ) 设x 是包含树t 的p 个不同顶点的集合若x 包含顶点a 和 b 使得p ( a ，b ) 是t 的一条最长路，则x 是t 上p - 似谢口礼问题的一个最优解 定理2 2 8 ( 【1 2 】) 树上的p - m a x i a n 问题可以在线性时间内解决 2 0 1 0 上海大学硕士学位论文 1 2 最后，关于树上半厌恶型中位问题，目前得到的主要结果有； 1 9 9 8 年，b u r k a r d 和k r a r u p 【1 5 】首次考虑树上半厌恶型的1 一中位问题，并证 明了该问题可在0 ( 几) 时间内解决 2 0 0 0 年，b u r k a r d 等【8 】讨论了树上半厌恶型的二中位问题由于树上的m w d 问题满足顶点最优性，采用删边思想，树上的m w d2 - 中位问题可在o ( n 2 ) 时间 内解决然而树上的w m d 问题不具备顶点最优性，边删除法也不适用，他们则 基于以下两个定理，为树上的w m d2 - 中位问题设计了一个o ( n 3 ) 时间的算法 定理2 2 9 ( 【8 】) 树上的w m d 乒中位问题存在一个最优解x = 扛l ，z 2 ) ，满足z l 或z 2 是树的一个顶点 定理2 2 1 0 ( 【8 】) 若树t = ( v , e ) 上的w m d2 - 中位问题不存在包含两个顶点的 最优解，则必存在一个最优解x = 忙l ，z 2 ) ，满足x l kz 2 垡km 1 2 v 其中 m 1 2 是路p ( x l ，x 2 ) 的中点 2 0 0 6 年，b e n k o c z i 等【4 】利用“脊椎树分解”( s p i n et r e ed e c o m p o s i t i o n ) 的数 据结构，证明了树上的m w d2 - 中位问题可在o ( n l o g n ) 时间内解决，w m d2 - 中 位问题可在o ( n h l 0 9 2n ) 时间内解决，其中h 表示树的高度 2 0 0 7 年，b u r k a r d 和f a t h a l i 讨论了树的w m d 孓中位问题，得到以下结果 定理2 2 1 1 ( 1 1 d 对树t 上的w m d3 - 中位问题，存在一个最优解x = 伽1 ，x 2 ，z 3 ) 满足下列条件之一： 1 ) x i ，吻以及m k l ( m k l 嘞) 是t 的顶点； 2 ) 翰以及 m 1 2 ，m 1 3 ，m 2 3 中的任意两点是t 的顶点 其中表示路p ( x i ，巧) 的中点 定理2 2 1 2 ( 【1 1 】) 树t 上的w m d3 - 中位问题可在d ( n 5 ) 时间内得以解决若限 制中位在树的顶点或者丁是一条路，则该问题可在d ( n 3 ) 时间内解决 综合定理2 2 1 0 和2 2 1 1 ，b u r k a r d 和f a t h a l i 【1 1 】猜测树t = ( ke ) 上的w m d p 中位问题，存在一个最优解x = z l ，2 ：2 ，却) 满足以下性质： 1 ) 至少存在一个点如v 垫! 竺土查盔堂塑主堂垡堡奎 ! 兰 2 ) 若x l ，x 2 ，z 知v ( k p ) ，x k + l ，即譬v ，则对任意的i 忌+ 1 ，计，存在 一个歹 l ，i 一1 和v 使得d ( x i ，v r ) = d ，巧) 2 0 0 9 年，程郁琨和康丽英考虑了树上以子树为客户的半厌恶型1 中位同题， 得出如下结论 定理2 2 1 3 ( 【2 0 】) 设t 是一棵树，正( 1 i t ) 是t 的子树且其边界点均为t 的 顶点，则r 上以t ( 1 i t ) 为客户的半厌恶型1 一中位问题可在m a x o ( e i t ；lq + n ) ，o ( t + 礼) ，时间内解决其中q 表示五的边数 定理2 2 1 4 ( 【2 0 】) 设t 是一棵树，t i ( 1 i t ) 是t 的子树，则t 上以五( 1 ist ) 为客户的半厌恶型1 - 中位问题可在m a x d ( 仡+ 名1n ：+ ：l 色) ，d m + ：ln ；+ t ) ) 时间内解次其中n ；表示正的边界点的个数，e - i 表示正的边数 3 块图上中位问题的主要结果 关于块图上中位问题的研究比较少，仅康丽英和程郁琨于2 0 0 8 年研究了边长 为1 的块图上的p - m a x i a n 问题，得到以下结果 定理2 2 1 5 ( 【4 3 】) 若连通块图g 的每条边的长度均为j ，则g 上的p - m a x i a n 问题 存在一个最优解x = 和1 ，x 2 ，却) ，满足每个点x i ( 1 i p ) 是g 的顶点或者 是g 的某条边的中点 定理2 2 1 6 ( 【4 3 】) 若n ，b 是连通块图g ( 完全图蚝除外) 中距离最大的两个点， 则 o ，6 ) 是g 上2 - m a z i a n 问题的一个最优解 推论2 2 2 ( 【4 3 】) 连通块图g 上2 - m a x i a n 问题的解不依赖于顶点的权重换句话 说。所有正的顶点权重均可得到相同的最优解 定理2 2 1 7 ( 【4 3 】) 设x 是包含块图g ( 完全图除外) 的p 个不同点的集合 若x 包含g 中距离最大的两个点a 和6 ，则x 是块图g 上p m a x i a n 问题的一个 最优解 定理2 2 1 8 ( 4 3 】) 边长为1 的块图上的p - m a x i a n 问题可以在线性时间内解决 4 仙人掌图上中位问题的主要结果 2 0 1 0 上海大学硕士学位论文 1 4 1 9 9 8 年，b u r k a r d 和k r a r u p 【1 5 】首次研究了仙人掌图上的半厌恶型1 中位问 题若限制中位在仙人掌图的顶点，则该问题可以在线性时间内解决 2 0 0 7 年，h a t z l 【3 8 】证明了仙人掌图上的经典参中位问题可在o ( n 2 ) 时间内 解决 2 0 0 8 年，b u r k a x d 和h a t z l 【1 4 】根据定理2 2 1 ，采用在仙人掌图的圈上增加顶 点的方法，证明了即使去掉中位在顶点的限制，仙人掌图上的半厌恶型1 中位问 题仍可在线性时间内求解 关于p 中位问题的其他研究成果，可参阅文献【1 3 ，2 5 ，2 7 ，2 9 ，5 0 ，6 3 】 2 3几类图上中心问题的主要研究进展 本节将总结几类图上中心问题的主要研究进展为叙述方便，我们引入符号 r a p 其中，r 表示设施的候选位置集合，表示客户的位置集合，p 表示需 要放置的设施个数由于设施和客户的位置可能在图g 的顶点，也可能在边上的 任一内点；客户的权重有可能相同也可能不同，因此p 中心问题可记为加权或不 加权的w v p ，w e p ，e v p ，e e p 八种形式 1 一般图上中心问题的主要结果 1 9 6 4 年，h a k i m i 【3 5 】首次研究了般图上的经典中心问题他发现加权e v 1 中心问题的目标函数在