（运筹学与控制论专业论文）图的定位控制集与识别码.pdf

摘要 众所周知，由于图的控制集理论在组合优化、编码理论、计算机科学、通信网 络、监视系统和社会网络等领域重要的应用，使它成为近几十年来图论中发展最 快的领域之一随着研究的深入和应用的激发，各种新的控制参数不断涌现其 中图的定位控制集( 也称为定位控制码) 和识别码就是在控制集的基础上被提出来 的图的定位控制集和识别码已成为编码理论中较活跃的研究方向，它在通讯网 络和监视系统中有广泛的应用 由于任意图的最小定位控制码和识别码的判定问题均是n p - 完全的，所以对 这两类码的上、下界的估计、极值图的刻画、特殊图上算法的设计和寻找其近似算 法成为人们很感兴趣的问题本文主要研究了定为控制集和识别码的界，其主要 研究的结果如下： 第一部分，首先给出了图的定位控制集和容错定位控制集的概念，接着给出 了它们的一些基本性质，得到了容错定位控制集在几类有限图和无限三角形格子 图中的一些界接着我们在海明空间中对定位控制集进行了相关研究( 有关结果 被上海大学学报录用) 第二部分，研究了图的识别码从算法的角度证明了任意图上识别码的一个 上界，根据我们给出的算法自然的构造了一类能够达到这个上界的图另外，给出 了识别码在几类特殊图上的界 关键词： 图；控制集；定位控制集；容错定位控制集；识别码 a b s t r a c t a sw ea l lk n o w ，w i t h i nt h el a s tm o r et h a nt h i r t yy e a r s ，g r a p ht h e o r yh a s b e e ne x p l o s i v eg r o w t h t h es t u d yo fd o m i n a t i o ni ng r a p h si so n eo ft h ef a s t e s t g r o w i n ga r e a sw i t h i ng r a p ht h e o r y t h er a p i dg r o w t ho fd o m i n a t i o nr e s e a r c hi s a t t r i b u t a b l em a i n l yt oi t ss om a n ya p p l i c a t i o n st oo t h e rs c i e n c e sa n dr e a lw o r l d p r o b l e m s ，s u c ha sc o m b i n a t o r i a lo p t i m i z a t i o n ，c o d i n gt h e o r y , c o m p u t e rs c i e n c e ， c o m m u n i c a t i o nn e t w o r k s ，m o n i t o rs y 8 t e ma n ds o c i a ln e t w o r kt h e o r y w i t hr e - s e a r c h i n gd e e p l y , m a n yd i f f e r e n tt y p e so fd o m i n a t i o np a r a m e t e r sh a v es p r u n gu p r a p i d l y l o c a t i n g - d o m i n a t i n gs e t ( c o d e ) a n di d e n t i f y i n gc o d ei ng r a p h sa r eb a s e d o nt h ec o n c e p to fd o m i n a t i n gs e t a sa ni m p o r t a n tr e s e a r c hf i e l di nc o d i n gt h e - o r y , l o c a t i n g - d o m i n a t i n gs e ta n di d e n t i f y i n gc o d ea r ew i d eu s e di nc o m m u n i c a t i o n n e t w o r k s ，m o n i t o rs y s t e m a sd e c i s i o np r o b l e m so ft h em i n i m u ml o c a t i n g - d o m i n a t i n gs e ta n di d e n t i f y i n g c o d ea r en p o c o m p l e t ef o rg e n e r a lg r a p h s ，i ti si n t e r e s t i n gt oi n v e s t i g a t eb o u n d so f t h o s ea n dc h a r a c t e r i z et h es t r u c t u r eo fe x t r e m a lg r a p h s ，w h i c hi su s e f u lt od e s i g n t h e i ra p p r o m i x a t i o na l g o r i t h m sa n dt of i n da l g o r i t h m si ns o m es p e c i a l 铲a p h s i n t h i sp a p e r ，w em a i n l yi n v e s t i g a t eb o u n d so fl o c a t i n g - d o m i a n t i n gs e ta n di d e n t i f y i n g c o d ei ng r a p h s ，a n dt 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 g ： i nt h ef i r s tp a r t ( c h a p t e r3 ) ，w es t u d yt h el o c a t i n g - d o m i n a t i n gs e ta n df a u l t - t o l e r a n tl o c a t i n g - d o m i n a t i n gs e t w ep r e s e n tb o u n d so nt h em i n i m u mc a r d i n a l i t y o ft h ef a u l t - t o l e r a n tl o c a t i n g - d o m i n a t i n g a n di ni n f i n i t et r i a n g u l a rg r i d s t h e nw e h a m m i n gs p a c e s s e t ，b o t hi ns o m ek i n d so ff i n i t e 黟a p h s s t u d yt h el o c a t i n g - d o m i n a t i n gs e ti nt h e i nt h es e c o n dp a r t ( c h a p t e r4 ) ，w es t u d yt h ei d e n t i f y i n gc o d e w ep r o o fa n u p p e rb o u n do ft h em i n i m u mc a r d i n a l i t yo fi d e n t i f y i n gc o d ei ng e n e r a lg r a p hf r o m t h ea l g o r i t h m i cp o i n to fv i e w b yo u ra l g o r i t h mac l a s so fg r a p h sw h i c hc a na c h i e v e t h i sb o u n db en a t u r a l l yc o n s t r u c t e d t h e nw eg i v es o m er e s u l t si ns o m es p e c i a l g r a b s k e yw o r d s ：g r a p h ；d o m i n a t i n gs e t ；l o c a t i n g - d o m i n a t i n gs e t ；f a u l t - t o l e r a n t l o c a t i n g - d o m i n a t i n gs e t ；i d e n t i f y i n gc o d e 原创性声明 本人声明：所呈交的论文是本人在导师的指导下进行的研究工作除了文中特 别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果。 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示了谢意 签名。 套朔似 日期t 矽矿年p 占月l f 日 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即s 学校有权保留论 文及送交论文复印件；允许论文被查阅和借阅；学校可以公布论文的全部或部分 内容 保密的论文在解密后应遵守此规定 签名。 翻钦导师签名：7 隶砺亥 日期t 纠9 年彩月i 岁日 2 0 0 8 年上海大学硕士学位论文 1 第一章引言 在图上定义的定位控制码( l o c a t i n g - d o m i n a t i n gc o d e s ) 和识别码( i d e n t i f y i n g c o d e s ) 是近几年提出的两类重要的码，它们与图的控制集概念密切相关，其中图的 定位控制码在文献中也称为图的定位控制集，而识别码也可归结为一类图的控制 集众所周知，图的控制集理论是图论研究的一个非常活跃的方向，1 9 9 8 年，美国 学者h a y n e s ，h e d e t n i e m i 和s l a t e r l 均，l b l 在对此领域进行系统总结后，首次出版 了两本关于图的控制数理论的专著d o m i n a t i o ni ng r a p h s - - a d v a n c e dt o p i c s 和f u n d a m e n t a l so fd o m i n a t i o ni ng r a p h s ，其中在f u n d a m e n t a l so f d o m i - n a t i o ni ng r a p h s 中引用了1 2 0 0 多个文献2 0 0 0 年，a m s 为d o m i n a t i n gs e t s ， i n d e p e n d e n ts e t s ，c l i q u e s 在分类条目中专列了一项0 5 c 6 9 关于控制参数理论研 究的全面进展可参阅【1 5 ，1 6 】 1 9 8 7 年s l a t e r 在文献【4 5 】中引入了定位控制集的概念设s 是图g = ( v e ) 的控制集，如果对于y s 中任意两点u ，钞满足g ( u ) ns g ( v ) ns ，那么称s 是图g 的定位控制集接着在1 9 9 8 年，k a r p o v s k y 在文献 3 6 】中给出了识别码 的概念，它与定位控制集密切相关设s 是图g = ( k e ) 的控制集，如果对于y 中任意两点u ，秽满足心1ns mns ，那么称s 是图g 的识别码 对上述两个参数进行研究的动机是基于它们在现实生活中和编码理论中有着 重要的理论和实践意义我们知道，在一个网络中安装传感器或监测器已广泛的 应用于国家安全、土木工程、制造业和分布式或多处理器的故障检测等领域中 安装监测器的目的是：为了迅速准确地检测到一个网络中的攻击、故障和污染等 等，同时要降低安装监测器的费用把一个网络系统表示成一个简单的图，从而就 把问题转化成寻找图中最小定位控制集和识别码任意图中最小定位控制集和识 别码的判定问题已经证明是n p - 完全的，即便是在一些简单的拓扑结构，如路和 圈上，这个问题也比较复杂我们在路和圈上研究这两个参数是因为，路和圈在生 活中最为常见，比如，地铁隧道就可以看作图中的一条路，有轨电车的环形轨道， 可以看作图中的圈许多文献也对其它有意义的拓扑结构进行了研究，特别是在 至q q 墨生土整太堂亟堂僮迨塞 ! 二进制立方体、非二进制立方体、各种网格图，树和二进制超立方体中人们对这两 个参数进行了大量的研究目前关于定位控制集和识别码的研究文献越来越多， 【4 3 】中最近关于这两个参数的索引文献已有1 0 0 余条关于这两个参数的研究， 可参考【1 8 - 2 0 ，2 2 ，2 5 ，2 6 ，2 9 - 3 2 ，3 4 ，3 7 ，3 8 ，4 1 ，4 7 】对它们的研究都已经形成了 一个独立的研究分支定位控制集和识别码的一般定义见本文第二章 下面我们用一个模型来具体说明一下研究的问题例如，一个系统可以对应 的建立一个图的模型，其中图中的每个点对应系统中的一个处理器，图中的两个 点之间的连边表示对应的两个处理器是连接的假设所有的处理器中至多有一个 发生故障，我们希望能够检测这个系统并且能够及时的找出发生故障的处理器 为了达到这个目的，我们需要选出一些处理器s 使它们具有检测功能，能够检测 到与它相邻的处理器包括它自己这些被选定的处理器一旦检测到有处理器发生 故障就给中心控制器( 系统之外的部分) 发送报警信号。我们要求能够通过中心控 制器接收到的信号能够准确的确定出发生故障的处理器的位置 如果对于选出来的集合s ，当s 中的处理器u 检测到g v 1 中有处理器发生 故障，则给中心处理器发送报警信号l ，反之，发送0 为了根据中心处理器接收 到的信息来确定出发生故障的处理器，需要s 是一个识别码我们把模型如下修 改，如果 发生故障，处理器口给中心控制器发送信号2 当 检测到g ( v ) 中 有处理器发生故障时给中心控制器发送信号l ，当n v 】中没有故障发生时发送信 号0 也就是任意 s 有三种信号状态，这时，为了确定出所有处理器中故障 发生的位置，需要s 是一个定位控制集一个定位控制集s 称作容错定位控制集 ( f a u l t - t o l e r a n tl o c a t i n g - d o m i n a t i n gs e t ) ，如果它能够在当s 中所有的处理器正确 检测并发送正确数值，或当s 中有一个处理器发生故障失去监测功能时，利用中 心控制器得到的信息都能正确地确定出发生故障的处理器的位置 目前，对于定位控制集和识别码的研究主要集中在以下几个方面t ( 1 ) 确定它们的上下界，计算一些特殊图的值； ( 2 ) 给出极端图类的结构性质的刻画； ( 3 ) 讨论其复杂性问题，算法及应用问题； ( 4 ) 研究它们在无限格子图中的最小密度 ! q q 墨生上整太堂亟堂焦迨塞墨 本文的主要工作是研究了定位控制集、容错定位控制集和识别码，其相应的 结果为以下两部分： 第一，首先得到了几类简单图上的最小容错定位控制集；给出了最小容错定 位控制集在树上的一个紧的上界；讨论了最小容错定位控制集在无限三角形格子 图上的密度；此外，研究了定位控制集在海明空间中的一些性质 第二，研究了图的识别码从算法的角度给出了任意图上识别码的一个上界， 根据我们给出的算法自然地构造了一类能够达到这个上界的图另外，给出了最 小识别码在几类特殊图上的界 2 0 0 8 年上海大学硕士学位论文 4 第二章基本符号和结论 2 1 基本概念和记号 本文所讨论的图( 除特别说明外) 均是无孤立点、无环无多重边的无向有限简 单图凡是文中未加定义的术语和符号，可参看文献f 1 1 5 】为了叙述方便，我们 首先引入一些定义和记号设g = ( ke ) 是简单图，y ( g ) ，e ( c ) 分别表示图g 的顶点集和边集，g 的点的数目n = i y ( g ) l 称为图g 的阶数如果图日满足条 件v ( h ) v ( g ) 和e ( h ) e ( g ) ，则称日为图g 的一个子图对s y ( g ) ， 用g s 1 表示s 的导出子图 图g 中点z 的开邻域定义为n ( x ，g ) = 妇ix y e ( g ) ，z 的闭邻域为 n i x ，g 】= n ( x ，g ) o z ) 更一般地，对任意的x y ( g ) ，我们定义n ( x ，g ) = u 。x n ( x ，g ) ，n x ，g 】= n ( x ，g ) ux 在不引起混淆的情况下，上述符号可分别 简记为( z ) ，m ，n ( x ) 和】我们称d e g ( x ) = l ) l 为点z 的度数，度数 为1 和0 的点分别被称为图的悬挂点和孤立点特别地，树中的悬挂点也叫叶 子分别用j ( g ) 和a ( a ) 表示图g 的最小度和最大度图g 中度为奇数和偶 数的点分别称为奇度点和偶度点所有顶点的度都等于k 的图g 称为后正则 图 由n 个顶点构成的路和圈一般记作r 和g 图g 的一条路是指一个有限 非空序列w = v o e l v l e 2 v 2 e k v k ，它的项交替地为顶点和边而且顶点v o ，t ，1 是互不相同的，使得对1 i k ，e i 的端点是忱一1 和称是从如到讥的 路，或一条( v o ，v k ) 路顶点仳和口之间的距离d ( u ，勘) 是g 中最短( u ， ) 路的 长如果对于g 中任意两个顶点u 和v ，在g 中都可以找到一条( “，秒) 路，则称 g 是连通的若图g 中的任意两个相异点之间都有边相连，则称g 为完全图， 礼个顶点的完全图记作珞连通的无圈图称为树用g = ( k ，k ，y k ；e ) 表 示顶点集是u 墼1 k ，边集是 z 可e ( g ) ix m ，y y j ，l i o ； ( 6 ) 州( q 知+ 1 ) = k + 1 ，当q = 1 ，p o ； ( c ) l ( c k 知+ 1 ) = k + 3 ，当q = 2 ，p o ； ( d ) 聊( 岛七十1 ) = k + 1 ，当g = 3 ，p o ； ( e ) 趔( q 七+ 1 ) = 后+ 2 ，当q = 4 ，p 0 ，聊( 岛) = 5 定理2 2 4 ( 【4 2 】) 关于路r ，设n = 5 p + q ，口 垒2 笾e 至q q 墨生土整太堂亟堂僮迨塞! q 定理2 2 1 6 ( 【2 4 】) 设7 1 ，n 3 是两个整数，g = ( ve ) 是一个阶n 的连通 无向r - - 可识别的图 c y 是g 的一个最小的r 一识别码，那么 i c l 1 0 , 一1 i r e n ec h a r o n 等在文献【l o 】中构造了几类能够达到这个上界的图 定理2 2 1 7 ( 【2 1 】) 如果t 是阶扎的树，且有t 个叶子，那么 m 7 ( t ) 【詈j + t 一1 定理2 2 1 8 ( 2 1 】) 如果t 是阶n 3 的树，那么 m 7 ( 丁) 学 u r ib l a s s 等在文献【3 】中给出了识别码在海明空间中的一些结果 廷丝! ( 翌)娶 丝! ( 丝】 3473 2 47 85 6 6 4 51 091 0 1 1 2 8 6 1 8 - 1 9 关于最小识别码在无限格子图上的密度，我们有： 定理2 2 1 9 ( 【3 6 】) k a r p o v s k y 等最小识别码在四边形格子图中的密度 d ( z 2 ) ； 定理2 2 2 0 ( 【6 】) c o h e n 等最小识别码在四边形格子图中的密度； 嚣d ( z 2 ) 音 定理2 2 2 1 ( 【6 】) c o h e n 等最小识别码在四边形格子图中的密度： 嚣sd ( z 2 ) 云 定理2 2 2 2 ( 【3 5 】) l i t s y n 和m e r k a s m e r 最小识别码在四边形格子图中的密度； d ( z 2 ) = 嘉 呈q q 墨生土整太堂亟堂焦迨塞! ! 定理2 2 2 3 ( 【3 6 】) k a r p o v s k y 等最小识别码在三角形格子图中的密度。 d ( t ) = 定理2 2 2 4 ( 【3 1 】) c o h e n 等最小识别码在六边形格子图中的密度： 3 1 6 9 d 呷) 等 定理2 2 2 5 ( 8 1 ) c h a r o n 等最小r 一识别码在k i n g 一格子图中的密度； d ( k ) = ；， 研( k ) = 5 ，其中r 1 关于定位控制集和容错定位控制集的研究主要有以下结果： 定理2 2 2 6 ( 4 4 1 ) 对于所有n 1 ， m 厶( r ) = f 警1 = m 工( g ) 定理2 2 2 7 ( 【1 】) 对于所有竹1 ，7 2 m l ( p ) n + 3 1 定理2 2 2 8 ( 【1 】) 设k 是一个非负整数，r 2 ； ( 1 ) 如果r 是偶数且佗= 3 k r + 2 r + 1 ，那么 畔( r ) 学+ t j 3 f f l ，, ( 2 ) 如果7 是奇数且礼= k ( 3 r + 3 ) + 2 r + 1 ，那么 聊( r ) 学+ r d 3 f f l o ， ( 3 ) 对于所有礼2 r + 1 ， 聊( r ) 出3 + 丛3 i 定理2 2 2 9 ( 【1 】) 对于所有n l ，7 2 聊( 瓯) 闭 定理2 2 3 0 ( 1 1 ) 设r = 2 且k 2 ，或7 2 且k 1 ；如果7 是奇数且 佗= k ( 3 r + 3 ) ，或7 是偶数且n = 3 k r ，那么 聊( g ) 詈 定理2 2 3 1 ( 4 4 1 ) 对于任意阶7 1 , 的树t 有 m l ( t ) 詈 定理2 2 3 2 ( 【4 6 】) 对于阶礼的树t 有 f t l d ( t ) 警 关于最小定位控制集和最小容错定位控制集在无限格子图上的密度，我们有t 定理2 2 3 3 ( 4 6 1 ) 在四边形格子图中定位控制集最小密度 d ( z 2 ) = 啬 定理2 2 3 4 ( 2 8 1 ) 在三角形格子图中定位控制集最小密度 d ( t ) = 嚣 定理2 2 3 5 ( 2 7 1 ) 在忌i 聊一格子图中定位控制集最小密度 d ( 1 k ) = 定理2 2 3 6 ( 【2 7 1 ) 在六边形格子图中定位控制集最小密度 d ( h ) = 关于定位控制集和识别码的算法和算法复杂性的研究参考文献【1 1 ，1 2 ，3 9 ，4 5 1 2 0 0 8 年上海大学硕士学位论文 1 3 第三章图的定位控制集和容错定位控制集 本章我们首先给出了容错定位控制集在路r ，圈g 和乘积图倪x p 2 上的最小值，以及在树t 上的一个紧的下界；接着讨论了容错定位控制集 在2 l f 艮三- 角形格子图上的最小密度；最后研究了定位控制集在海明空间中 的情况 3 1 应用背景和相关研究 为了对一个设备或系统进行安全分析，例如进行火警检测，可以把这个系统 抽象成一个图g = ( ve ) ，其中图中的每个点代表个房间、走廊、楼梯等等两 个点之间的连边表示他们代表的两个位置在物理意义上是邻接或相互之间是可见 或可听到的为了能够及时准确地确定出系统中入侵者的位置，我们需要在y 中 选出一个集合s ，在这些位置安装监视设备每一个在 处安装的设备能够完成以 下检测任务：( 1 ) 在口处发现入侵者时监视设备给中心控制器发送信号2 ，( 2 ) 在 刀的开邻域研( 口) 一p ) 中( 不能确定出是开邻域中的哪一个点) 发现入侵者时， 给中心控制器发送信号1 ，( 3 ) 在 的闭邻域研( 口) 中没有入侵者时，给中心控 制器发送信号0 我们需要根据中心处理器接受的信息来确定入侵者的位置因此 定位控制集是一个具有定位性质和控制性质的集合 定义s 是图g = ( ve ) 的7 一定位控制集，如果s 满足s ( i ) 任意 口v ，b ，( 刀) ns 9 ， ( i i ) 任意u v s ，如，( 仳) 矗，( 口) 当r = 1 时简称为定位控制集 、 定位控制集在任意图上都有定义，但最小定位控制集在任意图上的判定问题 确实j v 尸一完全的目前，关于定位控制集的研究主要集中在，( 1 ) 寻找最小定 位控制集在一些特殊图上的界最小定位控制集在路和圈上的情况在文献【4 4 】中 给出了证明，文献【1 】给出了最小r 一定位控制集在路和圈上的部分结果( 2 ) 计 算定位控制集在无限格子图上的最小密度，三角形格子图、四边形格子图、六边形 格子图和舰叼一格子图上的情况分别在文献【2 8 】、f 4 6 】、【2 7 】中得到了证明文 至q q 墨生土漫太堂亟堂僮迨塞! 垒 献【4 6 】中讨论了最小容错定位控制集在四边形格子图上的情况( 3 ) 寻找最小定 位控制集在一些特殊图上的算法，文献【4 5 】给出了在无圈图上最小定位控制集的 线性算法一些其它算法复杂性方面的结果可以参考【1 l ，1 2 】在这一章中我们 的工作主要研究了容错定位控制集我们给出了容错定位控制集在r ，圈g 和 乘积图“马上的最小值，以及在树t 上的一个紧的下界；接着讨论了容错定 位控制集在无限三角形格子图上的最小密度；最后研究了定位控制集在海明空间 中的情况 3 2有限图中的容错定位控制集 在这一部分中我们给出f t l d 一集在路r ，圈c k 和乘积图c kxp 2 上的最 小值，以及在树t 上的一个紧的下界证明中需要用到下面两个引理 引理3 2 1 1 4 6 1g 是阶n 2 的连通图，g 有f t l d 一集当且仅当图g 中任意两 点没有相同的开邻域 引理3 2 2 4 6 1 若s 是图g 的f t l d - 集，则 ( i ) 对任意的w y ( g ) ，i n w 】ns i 2 ； ( i i ) 若n u 】ns = 饥，秽 且u z ( 口) ，贝0i n i x 】ns i 3 我们注意到，如果s 是图g 的个f t l d - 集，那么( s ) 中的每个连通分支 中任意两点没有相同的开邻域否则，若存在两点u 和v 并且s ( 让) = ( 口) ，那 么当 k ( u ) 里面的处理器都传送数值1 ，而s 中其它的处理器都传送。时，故障 的位置可能在u ，也可能在口，与s 是g 的f t l d 一集矛盾 定理3 2 1f t l d ( p , 。) = n 一【翌j ，其中n 4 证明；假设s 是路r 的一个f t l d 一集，研，岛，乳是( s ) 的连通分支， 那么对所有i = 1 ，2 ，k ，我们有i & i 4 否则，我们假设有一个i 最i = 2 ，那 么存在一个点锄y ( r ) 一s 且钞与& 中的一个点相关联，根据引理3 2 2 有 l n ( v ) ns i 3 ，这与r 是一条路矛盾如果有i & l = 3 ，那么( 最) 一定是p 3 路 假设它是一条u u w 一路，d e g ( v ) = 2 ，那么当口传送数值1 ，其它所有的都传送。 时，那么故障的位置可能是在乱或在w ，矛盾 至q 塑生土篷太堂亟堂僮迨塞 ! 墨 设r = v s ，7 = l r i 注意到r 中的两个端点一定属于s ，那么有 7 k 一1 和礼= i s + r l 4 k + k 1 ， 从而k 孚所以我们得到 丢= 等( 孚一1 、忙鲁， 一= 一一一- - ，r z = 一 扎n a b n 因此 所以 r 4 n 5 在下面的定理中我们给出了树t 上f t l d 一集的一个 紧的下界，并给出了一类能够达到这个下界的树 定理3 2 3 如果t 是阶仃5 的树，那么 f t l 。c t ，f 鲁( 礼+ 丢) 且下界是可达的 证明；假设s 是t 中的一个f t l d 一集，设5 = i s l ，研，岛，瞰是( s ) 的连 通分支容易知道对于i = 1 ，2 ，k 没有i & i = 3 的连通分支，否则s 不是个 f t l d - 集我们假设有后1 个点数为2 的连通分支，那么剩余的( s ) 中的k k 1 个连通分支每部分至少有4 个点设k 2 = k k l ，那么2 七l + 4 k 2 s 设r = v s ，r = l r l 设k 1 是一个与( s ) 中所有点数为2 的连通分支 相对应的k t 个点的集合，尬是一个与( s ) 中所有点数至少是4 的连通分支相 对应的七2 个点的集合下面我们构造一棵树f ，它的点数为k l + k 2 + r ，点集 v ( f ) = k lu 鲍ur ，边集e ( f ) 包括原来树t 中( r ) 里面所有的边，另外我们 在点u k 0 = l ，2 ) 与点v r 也连上边当且仅当在原来的树t 中u 与u 对应 的一个连通分支中的某个点邻接为说明图f 是一棵树我们注意到对于任意树 t ，假设t 7 是t 的一个非空的连通分支，把r 收缩看成一个点口7 后得到图t 记v ( t + ) = _ 秒7 ) uv ( t r ) ，v ( t r ) 中任意两点乱和秽是邻接的当且仅当它 们在t 中是邻接的，点钞7 与点v v ( t r ) 邻接当且仅当勘与v ( t ) 中的某个 点邻接易知图丁+ 仍是一棵树因此易得上面构造的图f 是树 设尺- 是r 中的这样一个集合，它之中的每个点至少与k l 中的一个点相邻 接，设r 2 = r r 1 那么我们根据引理3 2 2 可以知道每个尺l 中的点至少与 蜀u 鲍中的3 个点邻接，而冗2 中的点至少与j 已中的两个点邻接设r l = l r l i ， r 2 = i r 2 i 我们分以下几种情况来考虑 至q q 墨生土鲞太堂亟堂鱼途塞! z 因此 所以 因此 所以 因此 情况1 ：如果k 2 = d ，那么有7 _ = 7 _ 1 和2 k l = s 注意到f 是一棵树， 3 r l r l + 后1 一l ， r 1 ( k l 一1 ) 2 n 一5 = i v s i = i r i = r = r l 8 1 4 1 2 ， 5 4 ( 死+ 1 1 2 ) 1 5 情况2 ：如果坼= d ，那么有r = r 2 和4 k 2 3 因为f 是一棵树， 2 r 2 r 2 + k 2 1 ， r 2 k 2 1 8 1 4 1 7 , 一s = r 2 8 1 4 1 ， s 4 ( n + i ) 1 5 情况3 ：如果k 1 o 并且k 2 d 因为f 是一棵树，所以 3 r x + 2 r 2 7 1 + r 2 + 七l + k 2 一l ， 2 r 2 + 7 2 | 1 + 砣一1 同时我们注意到r 2 k 2 1 ，因此 所以 2 r l + 2 r 2 七1 + 2 k 2 2 8 1 2 2 ， r 8 1 4 1 至q q 墨生土瀣太堂亟堂僮迨塞! 墨 由此得出 n 一5 = i v s i = i r i = 7 8 4 一l ， 所以 s 4 ( n + 1 ) 5 根据上面的讨论我们得出s ( 佗+ i 1 ) 成立 下面我们来说明这个界是紧的如果要达到下界，当且仅当在情况1 中的所有 的不等式都能够取到等号因为t 是棵树，k 2 = 0 ，特别有r 1 = ( k 1 1 ) 2 由 此得出树俾us ) 中冗里面的每个点的度是3 ，并且冗中的点是两两不邻接的， ( s ) 中的每一个连通分支都是岛根据上面的结构特点，我们可以如下构造树t ， 取r ( r + ) 条两两没有公共点的尼路和一个恳，然后把每条r 路中间的点与 p 2 中任意的一点连一条边取t 的一个点子集s ，它包含除尼路中间点外的所 有点可以验证s 是t 的一个f t l d 一集且i s l = 加+ ) 定理证毕 对于任意的两个图g 和日，它们的乘积是这样定义的t 点集v ( c h ) = v ( c ) v ( h ) = ( 秕，甜) l u y ( g ) ，v y ( h ) ) ，边集e ( g h ) = ( u 1 ，秒1 ) ( 札2 ，v 2 ) l u t u 2 e ( g ) 且刨l = 砚或者刨l 口2 e ( h ) 并且u 1 = u 2 ) 定理3 2 4f t l d ( c nxp 2 ) = n + 陪州，其中亿5 证明一假设y ( p 2 ) = 秒l ，耽) ，y ( 瓯) = 乱l ，“2 ，) ，设磷= x 讥 ， 我们把磷中的点( u i ，仇) 简记为u ? ，其中l = 1 ，2 ，n ，k = 1 ，2 假设s 是 gxp 2 的一个最优的f t l d - 集，并且l sny ( c 三) i 尽量的小我们称gxp 2 中任何一对点( u i ，仳? ) 为个栏( c o l u m n ) ，记无= ( 吣1 ，啦) 一栏称为竹卜型的如 果i sn “毛u ：) i = m ，其中m = 0 ，1 ，2 我们定义任意的两栏厶和易之间的 距离为d 亿，易) = d ( u i ，) ，d ( u i ，蚴) 是点u i 与哟在g 中的距离，其中i 歹， i ，歹= 1 ，2 ，礼接下来我们可以证明总存在一个最优的f t l d 一集使得下面的 结论成立 断言l ：对于所有1 一型栏 = ( 叫1 ，钍? ) ，有u ：岳s 设厶= ( u z l ，仳；) ，乃= ( 丐1 ，嘭) o j ) 且让i ，嵋簪s 则d ( 厶，i j ) 4 否则，如 果d f f , ，乃) = 1 ，那么点田与u ；是不能被区分的如果d ( h ，乃) = 2 ，那么点仳 与 u 磐1 是不能被区分的如果d ( h ，乃) = 3 ，那么当sn u 件21 ，饯1 + 2 ) 中的处理器都传 ( 1 ) 礼= ( 2 ) n = ( 3 ) 礼= ( 4 ) n = ( 5 ) n = + 1 + 2 + 3 + 4 图3 2 1 ：所有的黑点是y ( 碟) ns 中的点 送数值1 时，故障的位置可能在u 州1也可能在牡拜2 ，因此点t l i + 1 1与u 知2 是不能 被区分的 如果对于所有1 一型栏l i = ( t l i l ，u i 2 ) 有乱ins = 以那么我们已经证明了断言 是成立的相反的，我们假设五= ( “i 1 ，“i 2 ) 并且u i s ，u ；隹s 我们通过下面的 步骤来得到一个新的f t l d - 集s 7 并且有l s 7 l = l s i 和l n 哦i i sn 嚷l 成 立首先我们找出最左边的一个1 一型的栏五= ( u ，u ) ，其中也 岳s ，即左边距 离厶最远的，同时要满足在厶和五之间没有这样的l 一型栏易= 0 ，1 ，乱；) 它的点 仳；譬s 类似地找出最右边的一个l 一型栏厶= ( u j ，坼2 ) 它的点札；譬s 现在对于 五和之间的所有的1 一型栏包括它们自身，把它们中原来属于s 的点从s 中删 除，把原来不属于s 的点选进s 我们把得到的新集记作s 7 可以验证这个过程 得到的s 7 仍然是一个最小的f t l d - 集，但i s f 7 砩i 豇1 2 ， 0 1 再根据口的任意性有f t l d ( t ) 1 2 3 1 定理证毕 3 4海明空间中的定位控制集 在这一节中我们对海明空间中的定位控制集进行了研究用f 。表示二进制字 母表 o ，1 ) ，略表示一个住维的二进制空间设z ，y 是赡空间中的两个n 维向 量，它们之间的海明距离d ( x ，y ) 是两个向量之间相异坐标的个数通常对于z 叼 我们记 b t ( z ) = s ，x t = 。ge 当z t ) 乏，z 。) 巴且 t s 证明我们对i 进行归纳证明如果i = 2 ，3 ，那么v x 】是一条b 或p 4 路， 显然，以上的所有性质都成立因此我们不妨假设对于所有的i k 其中k 4 引 理都成立，下面我们将证明当i = k + 1 时引理成立 设s = v 一 z ) 如果s 是一个识别码，那么算已经停止否则，根据算法 的设计，存在两个点“，移v 且有b ( 乱) = i s ( 影) ，那么有x k = n m m ，否 则，【喇= n v 】与g 是可识别的矛盾 下面我们证明使得等式，( u ) = i ( v ) 成立的唯一可能的情况是u = z k 一1 且 锄v x 七 情况1 ：u ，口x 詹容易证得u z 知，否则m = m 所以不失一般性，假设 t t = z 5 ，= z t 其中， s t 知 情况1 1 ：s 和t 奇偶性相同根据归纳假设的性质( 4 ) ，有茁1 区分u 和v ，所以 如( u ) i s ( u ) ，矛盾 情况1 2 ：5 和t 奇偶性不相同因为b ( u ) = i s ( t ，) ，所以札和t i 一定是邻接的 至q 鱼墨生土整太堂亟堂僮迨塞 垫 根据归纳假设的性质( 4 ) ，我们有u 霹和口x 2 ，那么x $ - - i 可以区分t l 和t ， 矛盾 情况2 ：u ，刨v x 知因为i ( u ) = l ( v ) ，所以x k 一2 一定与仳和口都邻接或者都 不邻接根据归纳假设( 3 ) ，z 七一定与u 和钞都邻接或者都不邻接那么我们有 【乱1 = p 】，矛盾 情况3 ：u x 知，刀v x 蠹容易验证u x k ，否则，m = n v 】与g 是可识 别的矛盾 情况3 1 ：钍= 而且5 和k 奇偶性相同，其中0 5 k 根据归纳假设的性质 ( 1 ) 有秒z 一2 e ，根据归纳假设的性质( 3 ) 有口z e ，因此我们有m = 川， 矛盾 情况3 2 ：u = 而且s 和k 奇偶性不相同，其中0 5 k 1 根据z 七= n x 。】x n v 】和口一定与z 七和x k 一2 都邻接或都不邻接，得出x k 一2 可以区分u 和 口，矛盾 在以上所有的假设情况之中我们都证明了其不成立，所以u = o 知一1 和口 y x 七根据我们的算法，记z 七+ l = 秽，x 七+ 1 = 【z o ，x l ，t 2 ，z 知，x k + 1 ) 根据 x 七中的点是两两不同的，我们容易知道x 七+ 1 的点也是两两不同的因此，根据 归纳假设( 1 ) ，当i = k + 1 时g 【蜓】和g 【定】一定是完全图如果z 七霹，那么 有x k x k 一1 e 和z 女z + lge ，因此我们易得性质( 4 ) 成立如果x k x 2 ，那么有 ：r , k x k 一1ge 和z 七z 七+ 1 e ，性质( 4 ) 也成立所以我们证得当i = k + 1 时，引理 中的性质( 1 ) ，( 2 ) ，( 3 ) 和( 4 ) 都成立证毕 定理4 2 1 如果g 一个阶数为1 3 ( n 3 ) 的可识别图，m ( g ) n 一1 证明对于一个给定的阶数为n ( n 3 ) 的可识别图g ，我们在图g 上运用算法 4 2 1 根据引理4 2 1 的性质( 2 ) ，我们知道x 中的点数是单调增加的所以算法 在运行有限步之后肯定会停止，与此同时，我们可以得到一个点数为扎一l 的识别 码，所以m ( g ) = 1 7 , 一1 ，证毕 下面根据算法4 2 1 和引理4 2 1 ，我们构造一类可以达到这个上界的图歹= g 七im ( a k ) = iv ( g k ) i - 1 每个图g k 厂( 参考图4 2 1 ) 构造如下t ( 1 ) 选取点集v ( e k ) = 戤ii = 0 ，1 ，2 ，忌) 其中七是偶数记砖= 缸 li ! q q 墨生土渔太堂亟堂僮迨塞 墨q 是偶数，0 i 七 ，记x o = 毛ii 是奇数，0 i 后) ( 2 ) 首先增加边使得a , , i x 2 】和g 七【霹】都是完全图，然后在所有的点矾霹 和点群其中s 不是图g 七的识别码根据引理4 2 2 和 引理4 2 3 得m ( g k ) n 一1 ，所以对于每个图g k 厂，有m ( a k ) = iv ( g k ) i 1 根据上一部分的讨论，注意到我们局