（应用数学专业论文）图的控制集的一些相关问题的研究.pdf

图的控制集的一些相关问题的研究 摘要 控制集是图论中的重要概念，它定义为图中的一个点集，使得图中其它任何一点 都与该点集中的某点相邻这一概念的提出始于k o n i g 、b e r g e 和o r e ，他们的著作 和c o c k a y n e ，h e d e m i e m i ，以及l a r s k a r 和w a l i k a r 等人的文章为后来的研究者提供 了有益的启示 在过去的3 0 多年里，对图的各类控制集参数问题以及控制参数与图的其他参数 的关系问题的研究已经成为图论研究的一个重要领域在此期间，各种新的控制参数 被不断提出，如具有“连通性 的控制集，具有“距离控制性”的控制集，具有“无 赘性”的控制集等等，本文在连通控制集和距离控制集的基础上引入一种新的控制 檠“f r ，矧- 控制集”，并从算法的角度来讨论它的性质 如何寻找图的最小控制集是一个n p 困难问题，它不能通过回溯法或随机化算法 有效地解决，在这种情况下，对于其中的一些问题，代之以设计近似算法，我们要保 证它是一个多项式时间算法，并且能得到一个近似于最优解的“合理”的解对于 最小化问题，算法的近似解与最优解的比值称为算法的近似比近似比与l 越靠近， 算法所得的解就与最优解越接近遗憾的是，并不是所有问题都能找到近似比为常数 的近似算法，比如，已经证明：在p 尸的前提下，最小控制集问题就不可能找到 l 七o ( 1 n n ) 更好的算法 在本文第二章中，我们首先引入了h 同- 控制集的准确定义，然后对一般图中的最 小【r ，捌一控制集问题提出了一个近似比为i n a ，+ 1 2 r + 广1 1 一l 的算法，这已经与d ( 1 i l 礼) 同 阶，可以认为，在一般图中，其改进的余地已经很小然后我们分别考虑图的 7 _ ，同一控 制数与图的大小的关系、图的h 删- 控制数与其补图的h 矧控制数的关系、图 的【r ，嗣- 控制集与全控制集的关系，得到了图的h 周控制数的三个不同上界 在第三章，我们从实际应用出发，将最小h 捌控制集限定在单位圆盘图中，考 虑单位圆盘图中的特殊几何结构，得到了近似比为f 4 r ( r + 1 ) ( 1 一2 0 - 等n 2 0 ) 百r + 1 ( 常 数) 的算法，其中0 = a r c c 0 8 ：丽r 在r ，r 取特殊参数的情况下，对算法的近似比进行 了更细致的刻划 在第四章，我们将最小【r ，捌一控制集限定在随机正则图中，利用极大独立集给出了 一个随机算法，并通过微分方程的方法分析了算法的返回值，进而得到了正则图中最 小p ，刷控制集的渐近界，并且证明，在r 足够大的时候，最小 r ，r + 1 卜控制集的渐近界 卜海交通人学博士学位论文 不超过一竺下在对随机算法进行分析的过程中，我们指出了一篇主要参考 ( d 一2 ) ( d 一1 ) 尚 文献在数据处理上的错误 最后，我们给出对未来工作的展望作为结尾 关键词：近似算法，图论，控制集，连通控制集，弱连通控制集，单位圆盘图，随机正则 图，l 心咿 一一 s t u d yo nd o m i n a t i n gs e t si ng r a p h sa n dr e l a t e d p r o b l e m s a bs t r a c t d o m i n a t i n gs e ti sa l li m p o r t a n tc o n c e p ti ng r a p ht h e o r y , w h i c hi sd e f i n e da sa l la v e a e x s u b s e ts u c ht h a te v e r yo t h e rv e r c e xn o ti ni tm u s tb ea d j a c e n tt os o m ev e h e xi nt h i ss u b s e t t h ed e f i n i t i o no fd o m i n a t i n gs e tw a sf i r s ti n t r o d u c e db yk o n i g ，b e r g ea n do r e ，t h e i r b o o k sa n d s o m eo fp a p e r sb yc o c k a y n e ，h e d e t n i e m i ，l a r s k a ra n dw a l i k a rm o t i v a t e di n t e r e s t o fl a t e rr e s e a r c h e r s h l 也ep a s tt h i r t yy e a r s ，r e s e a r c ho nd i f f e r e n tk i n d so fd o m i n a t i o np a r a m e t e r sa n dt h e i r r e l a t i o nw i t ho t h e rg r a p hp a r a m e t e r sb e c o m ea l la c t i v er e s e a r c hf i e l di ng r a p ht h e o r y d u r i n g t h i sp h a s e ，n e wd o m i n a t i o nr e l a t e dp a r a m e t e r sa r ei n t r o d u c e dc o n t i n u o u s l y , s u c ha sc o n n e c t e dd o m i n a t i n gs e ta n dd i s t a n c ed o m i n a t i n gs e t ，e t c i nt h i st h e s i s ，w ei n t r o d u c ean e w p a r a m e t e r - - “ 7 ，嗣- d o m i n a t i n gs e t ”，a n da n a l y z e i t sa l g o r i t h m i cq u a l i t i e s h o wt of i n dam i n i m u md o m i n a t i n gs e ti sn p h a r d w h i c hc a nn o tb es o l v e de f f i c i e n t l y v i ab a c k t r a c k i n go rr a n d o m i z e da l g o r i t h r n s ，i nt h i sc a s e ，w et r yt of i n da p p r o x i m a t i o na l - g o r i t h m si n s t e a d a na p p r o x i m a t i o na l g o r i t h m sc a nb er u ni np o l y n o m i a lt i m ea n dg e ta r e a s o n a b l yg o o ds o l u t i o nt og i v e np r o b l e m s t oam i n i m i z i n gp r o b l e m ，t h ep e r f o r m a n c e r a t i o no fa na p p r o x i m a t i o na l g o r i t h m si sd e f i n e da st h er a t i o no fr e t u r n e ds o l u t i o no fo u r a l - g o r i t h mt ot h eo p t i m a ls o l u t i o ni nt h e o r y u n f o r t u n a t e l y , n o ta l lt h ep r o b l e m s c a nb es o l v e d v i aa p p r o x i m a t i o na l g o r i t h m sw i t hc o n s t a n tp e r f o r m a n c er a t i o ，f o re x a m p l e ，u n d e rt h ea s s u m p t i o no fp n p ，t h e r ed o e sn o te x i s ta na p p r o x i m a t i o na l g o r i t h mf o rt h ep r o b l e mo f m i n i m u md o m i n a t i n gs e tw i t hp e r f o r m a n c er a t i os m a l l e rt h a no ( 1 n 礼1 i nc h a p t e r2o ft h i st h e s i s ，w ep r e s e n ta na l g o r i t h mf o r t h em i n i m u m 【7 ，r ) 。d o m i n a t i n g s e tp r o b l e mw i t hp e r f o r m a n c er a t i ol na r + 可2 r + l 卜1 i ng e n e r a lg r a p h s ，t h i sr e s u l tc a n tb e b e t t e r c dt o om u c h a 代e rt h a t ，w ec o n s i d e rt h er e l a t i o nb e t w e e nt h ec a r d i n a l i t i e so fa n 【r ，冗卜 d o m i n a t i n gs e ta n dt h eg i v e ng r a p h ，t h er e l a t i o nb e t w e e n 【r ，删一d o m i n a t i n gs e t so fa g r a p h a n di t sc o m p l e m e n t ，a n dt h er e l a t i o nb e t w e e n r ，捌- d o m i n a t i n gs e ta n dt o t a ld o m i n a t i n gs e t ， t h e nt og i v et h r e et y p e so fu p p e rb o u n d sf o ra r ，捌- d o m i n a t i n gs e t 1 i i 卜海交通大学博士学位论文 i nc h a p t e r3 ，w er e s t r i c tt h em i n i m u m 【7 ，嗣一d o m i n a t i n gs e ti nu n i td i s kg r a p h sf o r p r a c t i c a lr e a s o n s ，b a s e do nt h es p e c i a lg e o m e t r ys t r u c t u r e ，w eg e ta na l g o r i t h mw i t hc o n s t a n tp e r f o r m a n c er a t i o 4 r ( r + 1 ) ( 1 2 0 - s 霄i n 2 0 ) 1 百r + 1 ，w h e r e0 = a l e c 0 8 而r ，f o r e x a c t p a r a m e t e r s ，t h i sc a nb ei m p r o v e d i nc h a p t e r4o ft h i st h e s i s ，w er e s t r i c tt h em i n i m u mf r ，用d o m i n a t i n gs e ti nr a n d o m r e g u l a rg r a p h s ，b yt a k i n ga d v a n t a g eo fm a x i m a li n d e p e n d e n ts e t sw el i s tar a n d o m i z e da l g o r i t h m ，a n da n a l y z ei t sp e r f o r m a n c ew i t hd i f f e r e n t i a le q u a t i o n s m o r e o v e r , w eg e t a s y m p t o t i c u p p e rb o u n do fm i n i m u m 【r ) 捌d o m i n a t i n gs e t ，a n dp r o v et h a t 【r ，r + 1 卜d o m i n a t i o nn u m b e r w o u l dn o te x c e e d i = ra s y m p t o t i c a l l yw h e nri sl a r g ee n o u g h m e a n w h i l e ， f d 一2 ) f d 一1 ) 盎 。 w ep o i n to u ta ne r r o ro fc a l c u l a t i o ni no n eo fo u r m a j o rr e f e r e n c e s f i n a l l y , w ee n dt h i st h e s i sw i t ho u t l o o k so nh 矧一d o m i n a t i n gs e ti nf u t u r e k e y w o r d s ：a p p r o x i m a t i o na l g o r i t h m s ，g r a p ht h e o r y , d o m i n a t i n gs e t ，c o n n e c t e dd o m i n a t i n gs e t ，w e a k l yc o n n e c t e dd o m i n a t i n gs e t ，u n i td i s kg r a p h s ，r a n d o mr e g u l a rg r a p h s ，r e l a y n o d ep l a c e m e n t 一一 6 1 a a s u a r d s c d s w c d s i s m i s u d g m a n e t w s n r n p s c 主要符号对照表 渐近地成立( a s y m p t o t i c a l l ya l m o s ts u r e l y ) 随机地( u n i f o r m l ya tr a n d o m ) 控制集( d o m i n a t i n gs e t ) 连通控制集( c o n n e c t e dd o m i n a t i n gs e t ) 弱连通控制集( w e a k l yc o n n e c t e dd o m i n a t i n gs e t ) 独立集( i n d e p e n d e n ts e t ) 极大独立集( m a x i m a li n d e p e n d e n ts e t ) 单位圆盘图( u n i td i s kg r a p h ) 移动自组织网络( m o b i l ea dh o cn e t w o r k ) 无线传感网络( w i r e l e s ss e n s o rn e t w o r k ) 中继节点安放问题( r e l a yn o d ep l a c e m e n t ) 集合覆盖问题( s e tc o v e r ) 上海交通大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何他个人或集体 已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本文完全意识到本声明的法律结果由本人承担。 学位论文作者签名：塑笈 日期：趁丝年z 里月z 望日 上海交通大学学位论文版权使用授权书 本学位论文作者完全了解上海交通大学有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 ( 保密的论文在解密后应遵守此规定) 学位论文作者签名：丝凌指导教师签名：i 型婆塞 日期：碰年生月卫日日期：塑年卫月卫日 第一章绪论 1 1 控制集与近似算法 图的控制集定义为图 2 7 1 中的一个点集，使得图中其它任何一点都与该点集中的 某点相邻图的控制集概念来源于网络服务站点的设计问题，例如在通信网络中，设图 中的点表示城市，边表示城市之间有通讯设备联系的关系，我们要在某些城市上建立 转接站使每个城市至少能从一个转接站上接受信息，则转接站的定位问题就是求一个 图的控制集问题 定义1 1 ：设图g = ( ve ) 是一个连通图，s 是y 的子集，如果使得y s 中的任意一点都 与s 中的某点相邻，则称s 是图g 的控制集( d o m i n a t i n gs e t ) 顶点个数最少的控制集称 为图的最小控制集( m i n i m u md o m i n a t i n gs e t ) 最小控制集中的顶点个数称为图的控制 数( d o m i n a t i o nn u m b e r ) ，记为1 控制集这一概念的提出始于k o n i g 、b e r g e 和o r e 1l ，5 3 ，6 6 ，他们的著作 和c o c k a y n e 2 3 ，c o c k a y n e 和h e d e t n i e m i 2 4 】以及l a r s k a r 和w a l i k a r 5 6 等人的文章为后 来的研究者提供了有益的启示在过去的3 0 多年里，对图的各类控制集参数问题以及 控制参数与图的其他参数的关系问题的研究已经成为图论研究的一个重要领域在 此期问，各种新的控制参数被不断提w , 1 3 ，4 8 ，4 9 ，如具有“连通性”的控制集，具有 “距离控制性”的控制集，具有“无赘性”的控制集等等，在本文中，我们将在连通控 制集和距离控制集的基础上引入一种新的控制集，并从算法的角度来讨论它的性质 所谓算法 2 5 ，6 4 ，7 6 ，就是一个由有限的指令集组成的计算过程在我们所遇到的 各种优化问题中，很多都是p 困难的【1 ，2 ，3 9 1 ，这些问题不能通过回溯法或随机化算 法有效地解决，在这种情况下，对于其中的一些问题，代之以设计近似算法 5 2 1 ，我们要 保证它是一个多项式时间算法，并且能得到一个近似于最优解的“合理”的解 定义1 2 ：给定最小化问题p ，对于p 的每一个实例，令o p t ( t ) 为其最优解，a t g ( t ) 为算 法a l g 返回的近似解如果存在p 使得 面a l g 丽( i ) p唧( ，) 一， 对任意实例，都成立，则称法a 幻为问题p 的j d 一近似算法 1 卜海交通人学博士学位论文 最大化问题的p 近似算法与此类似，唯一的差别只是t ( ，) 为与a 幻( ，) 的位置互 换，即生a l g t 盟( i ) p 对任意实例j 都成立 p 称为算法的近似i ：p , ( p e r f o r m a n c er a t i o ) 注意到近似比通常都是大于1 的，近似比 与1 越靠近，算法所得的解就与最优解越接近遗憾的是，并不是所有问题都能找到近 似比为常数的近似算法，比如，著名的s e tc o v e r 商- j 题 2 1 ，5 5 】： s e tc o v e r ( s c ) ： i n p u t ：点集t = t l ，t 2 ，t n ，t 的子集& ，岛， o u t p u t ：找到最少个数的子集使得这些子集的并等于t 如果把图中的顶点集看作t ，每个顶点并上它的邻域里的点看作丁的子集，那么 各种各样的最小控制集问题就可以看成是加了限制条件的s e tc o v e r 矗- 题1 9 9 6 年， u f e i g e 【3 7 】证明：在p p 的前提下，s e tc o v e r 商 题不可能找到比o ( 1 n n ) 更好的算 法，所以，一般图的各种最小控制集问题也不太可能找到t 卜o ( 1 n n ) 更好的算法 有了以上的准备之后，为了引出我们的新概念，我们将对连通控制集，弱连通控制 集和距离控制集作出必要的介绍 1 2 几类特殊的控制集 人们对经典控制集所做的限制多种多样，比如，考虑控制集的各点之间是否相连， 于是便出现了连通控制集；又如，考虑控制集之外的点同时被多少个控制集中的点所 控制，便有了多重控制集，等等其中，具有“连通性”的控制集由于其在无线通信技 术中的应用引起了人们广泛的关注 1 2 1 连通控制集 无线网络【4 4 】的蓬勃发展，冲击着人类的生活行为，在“有基础设施”的无线网络 结构中，两台移动设备在进行通信时，必须透过中间的固定介质作为中继站，才能将信 息传递出去一般常见的中继如基站、接收器等等，中继站的最大优点在于可以掌控 移动设备的位置，就如同路由器【4 5 】的功能一般但这些设备常因外在的因素( 如战 争、天灾等) 而遭到破坏，继而使得无线设备之间无法沟通，所以，传统的无线网络已 无法满足人类的需求近年来，有许多专家开始重视“无基础设施”的网络结构，其 中，由于移动自组网( m o b i l ea d h o cn e t w o r k ，m a n e t ) 以人类可以在任何时间，任 一2 一 第一章绪论 何地点取得最新信息为目标，因此更为各应用领域所重视目前，移动自组网已经应用 在险情控制、移动会议、战地通信等诸多领域 由于网络的逻辑拓扑结构不同，无线自组网 1 0 ，6 7 可以分为平面型( h a t ) 和层次 型( h i e r a r c h i c a l ) 在平面型网络结构中，每一个节点的等级相同，可同时作为主机或是路由器，两个 移动终端之间可以通过无线电波直接通信，或者在协议允许的条件下通过多个中继来 建立连接 但是，人们已经证明，在大型的动态自组网中，平面型的网络结构在应对系统节点 增加的情况时，表现出的效果并不理想于是，人们便提出了层次型的网络结构模型 由于聚类结构( c l u s t e r ) 【4 1 就是一个典型的层次结构，因此很多专家倾向于对无线 自组网提出有效的聚类方案( c l u s t e r i n gs c h e m e ) ，以此来建设系统的层次结构 图1 1 c l u s t e r i n g 在一个聚类方案中，移动自组织网被划分成若干个簇，每一个簇中有一个“簇 首”( c l u s t e r h e a d ) ，而同时位于多个簇的节点被称为网关每个节点维护两种数据 结构：路由表和簇成员表节点周期性地与同簇内的邻居节点交换簇成员表，更新表信 息当一个节点要通信时，数据包首先传递给自己所在簇的簇首，然后通过网关到达另 外一个簇首，以此种方法穿过中间的分簇，到达目的节点所在簇的簇首，然后再转发给 目的节点通过分簇，大大减少了维护路由表所需要的信息量，提高了系统的运行效 率 一个自然的想法就是通过图的控制集来构作聚类方案 4 7 1 如上图所示，图中的黑 点就构成了图的控制集我们可以用控制集中的点作为簇首，任何其他的点都可依控 制关系被分配到某一簇首所在的簇中通常，我们需要使簇首的数量尽可能小，但是， 一1 一 卜海交通大学博士学位论文 如果我们进一步限制簇首之间是相邻的，或者是足够靠近的话，这就会给处理实际问 题带来极大的便利出于这方面的考虑，w u ，d a s 2 6 ，8 0 ，8 2 ，8 3 1 等人将连通控制集引入 到了无线自组网的研究当中，在此之后，连通控制集在计算机科学中的作用也得到了 越来越多学者的关注也使它成为国际上的一个研究热点 图1 2 g r a p h 图1 3 c d s 定义1 3 ：设图g = ( ve ) 是一个连通图，s 是图g 的控制集，如果s 导出的图是连通的， 则称s 是图g 的连通控制集( c o n n e c t e dd o m i n a t i n gs e t ) 最小连通控制集中的顶点个数 称为图的连通控制数( c o n n e c t e dd o m i n a t i o nn u m b e r ) ，记为 关于连通控制集，目前已有的结果非常丰富 1 4 ，1 6 ，4 0 ，7 7 在算法设计方面， s g u h a 和s k h u l l e r 4 3 在1 9 9 8 年给出了一般图的近似度为日( ) + 2 的算法，其中是 图的最大度，日( ) 是调和函数，即 h ( n ) = 1 + 1 2 + + 1 n 如前所述，一般图的各种最小控制集问题也不太可能找到l t o ( 1 nn ) 更好的算法， ( 佗) i n n ，所以，可以认为，对于一般图而言，这个算法已经足够好，可以改进的余地 已经不大【6 9 】 定界方面，p d u c h e t 和h m e y n i e l 2 9 在1 9 8 2 年证明了如下定理： 定理1 。1 ：7 3 7 2 2 0 0 0 年，t c a r o 1 5 等人用概率方法证明了： 定理i 2 ：设g 是一个有r , 个顶点的图，最小度为d ，那么 坠掣n 口十j 4 - 第一章绪论 对比l o v f i s z 6 0 给出的最小控制集的界( 最小度为d 且有n 个顶点的图) ： 7 掣d1 几， ，一上 一， 可以认为在渐进的意义下，对于最小度都是d 的图，其最小控制集与最小连通控制集的 大小相差无几 以上的结果都是建立在一般图的基础上进得到的，但是在实际应用中，我们研究 的都是带有特殊性质的图，比如平面图、正则图等等，在无线网络的研究中，尤其以单 位圆盘图( u n i td i s kg r a p h ) 模型最为重要 单位圆盘图 2 2 ，6 2 是定义在欧氏平面上，其两点之间存在边的充要条件是它们的 距离不超过单位长度这种独特结构为其改进最小连通控制集算法提供了可能性事 实上。单位圆盘图上的连通控制集存在近似比为常数的算法 一个与图的控制集关系紧密的组合结构为图的独立集 3 ，5 7 ，6 1 】： 定义1 4 ：对于给定的图g = ( ve ) ，设，是y 的子集，如果，中任意两点的距离都大 于r ，则称是图g 的r 独立集( r m d e p e n d e n ts e t ) 顶点个数最多的r 独立集称为图的最 大r 独立集( m a x i m u m7 一i n d e p e n d e n ts e t ) r = 1 时，最大r 独立集就简称为最大独立 集( m a x i m u mi n d e p e n d e n ts e t ) 2 0 0 2 年，通过考虑单位圆盘图上的独立集与控制集的关系，k m a l z o u b i ，p e n g - j u n w a n 和o f r i e d e r 5 ，6 】给出了近似度为8 的分布式算法，此后，这个结果被不断改进，迄 今为止的最小近似比为4 8 + i n5 1 8 1 1 1 2 2 弱连通控制集 在无线自组网络的路由协议设计问题中，连通控制集理论的应用十分广泛，但是， 由于连通控制集对连通性的要求过高，基于这种路由协议的网络中的骨干节点的数 目将会很大，这在网络节点少的时候不成问题，但是在网络节点不断增加的情况下，骨 干节点带来的能量消耗将非常可观为了改善这种状况，c h e n 和l i e s t m a n 1 7 ，1 8 应用 “弱连通控制集”提出了新的网络构架 定义1 5 ：设s 是图g = ( ke ) 的控制集，如果与s 中的点关联的边导出一个连通图， 则称s 是图g 的一个弱连通控制集( w e a k l yc o n n e c t e dd o m i n a t i n gs e t ) 最小的弱连通控 制集中的顶点个数称为图的弱连通控制数( w e a k l yc o n n e c t e dd o m i n a t i o nn u m b e r ) ，记 为 一气一 卜海交通大学博士学位论文 图1 4 g r a p h 图1 6 c d s 图1 5 d s 图1 7w c d s 图“g r a p h ”为一个度为3 的正则图，图“d s ”，“c d s ”，“w c d s ”中的黑点的 集合分别代表它的控制集，连通控制集和弱连通控制集 图的弱连通控制集的概念最初由d u n b a r 3 4 ，4 2 等人提出容易看出，它是对连通 控制集的连通性要求的弱化具体的，对一般图，以下结果成立： 定理1 3 ：，y 2 一1 ，2 一1 d u n b a r 等人进一步证明了：求图的最小弱连通控制集是n p 难的在文献【1 7 】中， c h e n 和l i e s t m a n 对此提出了近似比为l n + 1 的算法，虽然d u b h a s h i 在【2 8 】中对此略有 改进，但是这个结果已与集合覆盖问题的近似l h o ( n 钆) - 。致，可以认为再改进的余地 很小 除了在一般图中考虑弱连通控制集之外，单位圆盘图与正则图中的弱连通控制集 也吸引了一部分学者的研究目光在单位圆盘图中，a l z o u b i 7 等人同样考虑极大控制 集与极小控制集的关系，对最小弱连通控制集问题给出了近似比为5 的算法在正则图 中，d u c k w o r t h 3 1 ，3 2 ，7 9 】等人提出了随机的贪心化算法，并用微分方程的手段对算法 进行了平均性状分析，由此得出了随机正则图中的最小弱连通控制集的一个渐进上界 定理l 。4 ：如果随机d - 正则图g 有礼个顶点，则其弱连通控制数在渐近的意义下满足 一6 一 第一幸绪论 如下不等式： ( g ) t 3 1 n 3 佗+ 。( n ) ，d = 3 ， ( g ) 掣n + 。( 扎) ，d = 4 ， 们h 南一喾赫川咄瞄 1 2 3 距离控制集 一般认为，距离控制集的研究始于m e i r 和m o o n 6 3 】( 尽管当时被称作“k c o v e t i n g ”) ： 定义1 6 ：设g = ( ve ) 是一个连通图，s 是y 的子集，r 是给定的正整数如果对 于v s q 任意一点可，都能找到s 中的一点x 使得z 与y 之间的距离不超过r ，则称s 是g 的 距离为r 的控制集( d i s t a n c er d o m i n a t i n gs e t ) ，简称r 一步控制集，最小的r 步控制集中的 顶点个数称为图的r 一步控制数( d i s t a n c er - d o m i n a t i o nn u m b e r ) ，记作* 更进一步，如 果s 导出一个连通图，则称s 为g 的连通r 步控制集同理，我们可以定义图的连通r 步 控制数货 很明显，距离控制集是对一般控制集的一个自然的推广m e i r 和m o o n 证明了： 定理1 5 ：如果图g 有佗个顶点，则竹【南j 图的距离控制集有很多应用 3 6 ，4 8 ，4 9 ，7 3 1 早在1 9 7 6 年，s l a t e r 7 2 】就给出了如下 的例子在通信网络中，将城市抽象为图上的的顶点，如果两个城市之间有通信渠道， 则对应的两个顶点之间就有边相连现在考虑在某些城市中安置发射站，使得对于任 意一个城市，要么它有发射站，要么它可以通过一些城市之间通信渠道从某个发射站 获得信息出于成本的考虑，发射站的数目要尽可能小，同时，为了保证信息传递的速 度和质量。每个消息传递所经过的中间渠道不得超过r 条，如此，这个问题就成为确定 图的最d r 步控制集问题了 许多其他的实际问题都与距离控制集问题直接或间接相关比如，运筹学中 的p c e n t e r l h - 题可看作是确定7 , 1 h - 题的对偶问题，p c e n t e r l h - 题中，预先给定的正整 一7 一 上海交通大学博士学位论文 数p 用来限制图g 的顶点子集的大小，目标是最小化7 使得竹p 关于p c e n t e r ( - 与p - m e d i a n s ) 问题，目前有很多的研究成果，详见t a n s e l ，f r a n c i s 和l o w e 7 5 c h a n g 和n e m h a u s e r 1 6 证明，即使是在很特殊的图中( 如二部图) ，最小距离控 制集依然是p 难的在分布式环境中 3 5 1 ，图所代表的网络拓扑通常是度有界的甚至 是正则的，图的距离控制集在这样的情况下可应用来衡量路由表的紧致性 3 8 ，5 4 ，因 此，很多学者对正则图中的距离控制集问题产生了兴趣，其中，我们感兴趣的一个结果 是：d u c k w o r t h 和m a n s 3 3 在2 0 0 3 年通过微分方程的方法，给出了竹的渐进上界，比如， 在3 正则图中，我们渐近地有0 0 4 5 4 5 n 竹0 0 9 6 9 6 n 1 3 本文内容 本文从无线网络中的中继节点安放问题( r e l a yn o d ep l a c e m e n t ，r n p ) 问题出 发，将图论中的弱连通控制集在“距离控制性”上做了推广，提出t r ，捌- 控制集的组 合结构然后将f r ，捌- 控制集分别限制在一般图中，单位圆盘图中与随机正则图中，依 次给出了搜索图的最小【r ，捌一控制集的相关算法，并得到了随机正则图巾最小 r ，删一控 制集大小的一个渐进上界 具体地： 1 3 1 一般图中的p ，嗣一控制集 在第二章中，我们将从无线传感网络中的“中继节点安放问题”( r r e l a y n o d ep l a c e m e n t ) 模型出发，经由类比的方法，一步一步地抽象，提出一种新的控制集 结构- - - - i t ，捌一控制集： 定义1 7 ：设g = ( ke ) 是连通图，scy ，对于给定的正整数r ，兄，我们称s 是 图g 的 7 ，矧一控制集( r ，嗣- d o m i n a t i n gs e t ) ，如果以下条件成立： 1 s 是图g 的7 步控制集； 2 所有端点在s 中且长度不超过r 的路径的并是一个连通图 确定图的距离控制集是p - 难的，所以，如何计算图的 r ，周- 控制数竹，r ( g ) 也 是p 一难的在本章中，我们给出一个如何计求出图的最小r ，捌控制集的两阶段的近 似算法 一8 一 第一章绪论 我们的算法是基于g u h a 并l l k h u l l e r 4 3 的算法2 首先，我们将找到图的一个r 步控 制集，然后通过添加一系列的点链( c h a i n so f v e r t i c e s ) 使它满足h 矧控制集的连通 性的要求 经过证明，我们的算法的近似比为i na ，+ f 呈盟r 一1 由于一般图的各种最小控制 集问题在p 尸的前提下不可能找到l l o ( 1 n n ) 更好的算法，所以，可以认为，对于一 般图而言，我们的算法可以改进的余地很小 在给出了求图的最小【r ，嗣- 控制集的近似算法之后，我们尝试给 r ，捌控制数定界， 并得到了如下结果： 定理1 6 ：如果r 1 ， 2 则* 2 ，r 竹1 ，r 定理1 7 ：如果r 1 兄2 ，则 忡。轨心鲁1 ( y r , r 2 - 1 ) “ 通过考虑等号成立的情况，我们得到了一个更强的结果： 定理1 8 ：设r ，r l ，r 2 ，c 2 皆为正整数，而且r 1 r 2 ，z 为满足 z | _ 鲁 c q l ，+ 1 一眈 的非负整数则存在一棵树t 使得，r 。( t ) = c 2 和，r 。( t ) = c 2 + z 同时成立 接着，我们考虑图的p ，捌控制数与图的阶数的关系，从而得到如下上界： 定理1 9 对于r ，r l ，如果图g 的阶数n r + l ，r ，则竹，r ( g ) 再葫更进一步， 如果r = 2 ，则* ，r ( a ) n ： 1 9 5 6 年，n o r d h a u s 和g a d d u m 建立了图g 及其补图0 的着色( c h r o m a t i c ) 数的和及乘 积的上下界，从此，人们将图及其补图的同一参数之间的关系称为n o r d h a u s g a d d u m 型 关系j a e g e r 和p a y a n 在1 9 7 2 年得到了第一个有关图的控制数的n o r d h a u s g a d d u m 型关 系式的上下界 对于【r ，例一控制集，我们得到了如f n o r d h a u s g a d d u m 型结果： 一9 一 卜海交通大学博士学位论文 定理1 1 0 ：若图g 与0 都是顶点数为n 的连通图， 1 ，则 1 侧g ) “。) 丽n ， 2 仲( g ) + 兄( 。) 南+ 1 第二章的最后，我们考虑距离全控制数嘭与 r ，捌一控制数，r 的关系，证明了如下 定理： 定理1 1 l ： 伸州| - 可2 r + 1 1 - 1 肼- - 1 1 ) 1 3 2u d g 中的p ，捌- 控制集 单位圆盘图( u d g ，u n i td i s kg r a p h s ) 是定义在欧氏平面上，其两点之间存在边 的充要条件是它们的距离不超过单位长度实际应用中，人们通常将无线白组网抽象 为单位圆盘图，在这种情况下，每个移动终端的信号覆盖半径都被认是l ，所以，单位圆 盘图代表了网络中通信连接的集合也因为如此，研究控制集在单位圆盘图中的性质 是十分必要和有实际意义的 单位圆盘图的一个重要性质就是其中的独立集与控制集之间的关系这种关系可 以通过考虑一个顶点最多可以与独立集中多少个点相邻得到： 引理1 8 ：【5 】令，为单位圆盘图g 的一个极大独立集，u 为图g 中任意一点那么，中 与v 相邻的点的个数不超过5 在第三章，我们尝试将这个结果在距离控制的情况下进行推广，并得到了如下结 论： 引理1 9 ：令，为单位圆盘图c 的一个极大r 独立集，u 为图g 中任意一点那么，中 与u 的拓扑距离不超过r 的点的个数不超过4 r ( r + 1 ) 利用这个结论，我们找到了一个近似比为 4 r ( 川m 一鼍竽，百r + 1 的算法来搜索图的最小p ，嗣一控制集，其中口= 盯c c o s 矗 第一章绪论 1 3 3 正则图中的阿，嗣一控制集 在分布式系统中，图所代表的网络拓扑通常是度有界的甚至是正则的在度有界 的情形之下，我们前面已经对如何搜索图的最小【r ，捌控制集做了介绍，在第四章中， 我们将h 捌一控制集限制在正则图中进行讨论 首先，任何一个【r i 嗣控制集都是r 步控制集，所以7 步控制集的下界也可以作 为h 捌控制集的下界 在19 9 4 年，r o b i n s o n 和w o r m a l d 7 0 证明了： 定理1 1 2 ：在渐近的意义下，几乎所有的随机正则图都是哈密尔顿图 所以，如果我们在任一个哈密尔顿圈中每隔r 1 个点就取一个点，则选取的所有 的点构成的集合就是一个【r ，捌- 控制集，那么，我们就可以得n r ，嗣一控制集大小的一 个改进了的渐近上界： m ( g ) 吴 综合以上分析，我们有以下定理： 定理1 1 3 ：对于有礼个顶点的d - 正则图g ，在渐近的意义下： 揣2 鲰r ( g ) 兰r d ( d 一1 ) 7 一 一”一u 。7 一 受到单位圆盘图中找最小 r 用- 控制集的算法的启发，我们仍然考虑先找到图的 极小【r ，r4 - 1 卜控制集，然后添加点链使其满足【r ，问- 控制集的连通性要求所以，在本 章剩余的部分里，我们将着重讨论关于 r ，r + 1 卜控制集的算法，并证明了： 定理1 1 4 ：对于一个有礼个顶点的随机d - 正则图g ，如果7 3 ，则在渐进的意义下，它的 最小【r ，r + 1 卜控制集的大小满足： 协+ - 言( 1 一互1 1 n 3 一南+ c ( r - 2 , 3 ) ) 礼+ o ( 毗当d = 3 ； 协+ l 吾( 1 - l n 2 + c ( r - 1 ，4 ) ) n + 。( 毗当d =