（系统分析与集成专业论文）图的几类全控制参数.pdf

摘要 在过去近四十年里，随着计算机科学和网络通讯技术的飞速发展，图论研究 也呈现出异常活跃的趋势，而控制数理论的研究是其中发展最快的领域之一图的 控制数理论作为图论的一个重要研究方向，在相关学科领域，例如计算机科学、 通信网络、组合优化、编码理论、监视系统以及运筹学等领域具有广泛的应用随 着研究的深入，各种新的控制参数不断提出和研究，而且与图论的经典理论相互 交融，精彩纷呈 图的( 全) 控制函数就是图的经典( 全) 控制数的一类自然推广由于图的( 全) 控制函数的引入，致使利用函数性质来研究各类( 全) 控制数成为可能目前，各 类全控制函数已成为图的控制理论中一个崭新的研究方向关于全控制函数的研 究主要集中在四个方面。( 1 ) 确定各种控制参数的上下界，在一些特殊图上计算 它们的值；( 2 ) 寻找各种控制参数之间的关系；( 3 ) 给出极端图类的结构性质的刻 画；( 4 ) 各种控制参数计算复杂性的研究及其算法的设计 本文所做的工作主要包括以下两大部分： 第一部分，首先给出了负全l 【- 控制函数是极小的充要条件；接着研究了一些 特殊图如路、完全图、完全二部图中负全l c - 控制数的情况；最后建立了一般图和 树中负全l 啦制数的下界及k = 佗时，百的几个下界( 有关结果被j o u r n a lo f s h a n g h a iu n i v e r s i t y 录用) 。 第二部分，得到了全符号局部控制数在一般图和正则图中的下界以及在完全 二部图，。中的上界；并求出了圈g k 和星甄，。中诏的精确值( 有关结果已投 上海大学学报) 关键词： 图；全控制函数；负全危j 空制数；负全控制数；全符号局部控制数；界 a b s t r a c t w i t h i nt h ep a s td e a l f o r t yy e a r s ，c o n c u r r e n tw i t ht h eg r o w t ho fc o m p u t e r s c i e n c ea n dc o m m u n i c a t i o nn e t w o r k s ，g r a p ht h e o r yh a ss e e ne x p l o s i v eg r o w t h t h e s 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 tg r o w i n ga 1 ：e a sw i t h i ni t a s 叭 i m p o r t a n tr e s e a r c hf i e l di ng r a p ht h e o r y , d o m i n a t i o nt h e o r yh a sm a n ya n dv a r i e d a p p l i c a t i o n si nr e l a t e df i e l d s ，s u c ha sc 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 ， c 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 , m o n i t o rs y s t e ma n do p e r a t i o n sr e s e a r c h 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 eb e e n p u tf o r w a r da n dr e s e 缸c h e d ，e s p e c i a l l ym i n g l ew i t ht h ec l a s s i c a lt h e o r yo fg r a p h t h e o r ym u t u a l l y , w h i c hi sa c c o m p a n i e db yb r i l l i a n tp h e n o m e n o n ( t o t a l ) d o m i n a t i n gf u n c t i o ni ng r a p h si st h en a t u r a lv a r i a t i o no fc l a s s i c a l ( t o - t a l ) d o m i n a t i o nn u m b e r b e c a u s eo fi n t r o d u c i n gt h ec o n c e p to f ( t o t a l ) d o m i n a t i n g f u n c t i o ni n t og r a p h s ，i ti sp o s s i b l et os t u d y ( t o t a l ) d o m i n a t i o ni nt e r m so ff u n c t i o n a l p r o p e r t i e s a tp r e s e n t ，t h es t u d yo ns e v e r a lk i n d so fd o m i n a t i n gf u n c t i o n si sa n e w a n dc h a l l e n g a b l er e s e a r c hf i e l di nd o m i n a t i o nt h e o r y a n dm o s tr e s e a r c h e r si nt o t a l d o m i n a t i n gf u n c t i o nc o n c e n t r a t et h e i ra t t e n t i o no nt h ef o l l o w i n gf o u ra s p e c t s ：( 1 ) d e t e r m i n i n gt h eb o u n d so ns e v e r a ld o m i n a t i o np a r a m e t e r sa n dc o m p u t i n gt h e i r v a l u ei ns o m es p e c i a lg r a p h s ；( 2 ) f i n d i n gt h er e l a t i o n s h i p sb e t w e e nd o m i n a t i o n - e l a t e dp a r a m e t e r s ；( 3 ) g i v i n gc h a r a c t e r i z a t i o no fe x t r e m eg r a p h s s t r u c t u r a lp r o p - e r t i e s ；( 4 ) s t u d y i n gt h ea l g o r i t h m i cc o m p l e x i t yo fd o m i n a t i o n - r e l a t e dp a r a m e t e r s a n dd e s i g n i n ga l g o r i t h mo fd o m i n a t i o n - r e l a t e dp a r a m e t e r s i nt h i sp a p e r ，w ep a yo u ra t t e n t i o nm a i n l yo nt 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 i r s t l yg i v et h en e c e s s a r ya n ds u f f i c i e n tc o n - d i t i o n sw h e nam i n u st o t a lk - s u b d o m i n a t i n gf u n c t i o ni sm i n i m a l ；t h e ni n v e s t i g a t e t h ev a l u e so nt h em i n u st o t a lk - s u b d o m i n a t i o nn u m b e ro fs o m es p e c i a lg r a p h ss u c h a sp a t h 、c o m p l e t eg r a p h 、c o m p l e t eb i p a r t i t eg r a p h ；a tl a s tw ee s t a b l i s haf e w l o w e rb o u n d so n7 磊o fg e n e r a lg r a p sa n dt r e e s ，e s p e c i a l l ys e v e r a ll o w e rb o u n d so n 付w h e n 元= n i nt h es e c o n dp a r t ( c h a p t e r4 ) ，w eo b t a i naf e wl o w e rb o u n d si ng e n e r a lg r a p h s a n dr e g u l a rg r a p h s ，a l s oa nu p p e rb o u n di nc o m p l e t eb i p a r t i t eg r a p h ，nf o r 镌； i na d d i t i o n ，w eo b t a i nt h ee x a c tv a l u eo n 镌o fc y c l ega n ds t a rk 1 ，n 2 q q 墨生土鲞太堂亟堂僮迨塞! ! ! k e yw o r d s ：g r a p h ；r o t a ld o m i n a t i n gf u n c t i o n ；m i n u st o t a lk - s u b d o m i n a t i o n n u m b e r ；m i n u st o t a ld o m i n a t i o nn u m b e r ；t o t a ls i g n e dl o c a ld o m i n a t i o nn u m b e r ； b o u n d 原创性声明 本人声明：所呈交的论文是本人在导师的指导下进行的研究工作除了文中特 别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果， 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示了谢意 签名： 弘锄聚 啉川年6 月1 f 日 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即t 学校有权保留论 文及送交论文复印件；允许论文被查阅和借阅；学校可以公布论文的全部或部分 内容 保密的论文在解密后应遵守此规定 签名：靼铴粘导师签名：忿丽定 啸刎年舌月f 妒 2 0 0 8 年上海大学硕士学位论文 1 第一章绪论 本章主要介绍图的控制数理论的产生背景、应用领域及其主要研究方 向，最后指出了本文所做的主要工作 1 1图的控制数理论的产生、应用及研究 在过去近四十年里，随着计算机科学和网络通讯技术的飞速发展，图论研究也 呈现出异常活跃的趋势，而控制数理论的研究是其中发展最快的几个领域之一 所有理论研究的最终目的都是为了更好地应用于实践，图的控制数理论作为图论 的一个重要研究方向，在相关学科领域，例如计算机科学、通信网络、组合优化、 编码理论、监视系统以及运筹学等领域具有广泛的应用 对图的控制数的研究可追溯到十九世纪中期，当时人们注意到这样的问题：一 个国际象棋棋盘上，最少放置几个皇后就可控制( 攻击) 或占据所有的方格? 这可 以看作图的控制数问题的最初形式在1 9 6 0 年前后，人们开始对图的控制数进行数 学理论方面的研究，起初还是集中于研究nxn 棋盘的各类控制所公认的图的控 制数理论是在1 9 5 8 年由b e r g e 和1 9 6 2 年由o r e 共同建立的1 9 5 8 年b e r g e 的图 论专著中首次定义“控制数”这一概念，虽然当时他用的是另外的名称1 9 6 2 年， o r e 在图论著作中正式定义并使用目前一直沿用的控制数方面的术语。d o m i n a t i n g s e t ”和“d o m i n a t i o nn u m b e r ”1 9 7 7 年，c o c l = ( 甚y n e 和h e d e t n i e m i 在一篇报 告中综述了当时已知的有关图的控制数的结果，并且首次开始使用符号，y ( g ) 表示 图g 的控制数，此符号沿用至今此后的1 0 多年里，这一理论开始引起人们的广 泛关注并得到迅速发展，控制数研究的文献频频出现在各类数学期刊上据1 9 9 0 年d i s c r e t em a t h e m a t i c s 出版的一期控制集专辑( v o l8 6 ) 统计，截至当时 累计的文献就达到了4 0 0 篇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 i l ，z 】在对此领域进行系统总结后，首次出版了两本关于图的控制数理论的专著 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 n i ng r a p h 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 中引用了12 0 0 多个文献这两本专著的出版，为人们深入研究这一理论奠定了坚实的基础，同 至q q 璺生土塑太堂亟堂僮迨塞 2 时也巩固了控制数理论在图论中的地位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 ，d i q u e s 在分类条目中专列了一项0 5 c 6 9 关于控制参数理论研 究的全面进展可参阅f 1 ，2 】 随着控制数理论研究的深入和应用领域的拓宽，各种控制参数也不断涌现 到目前为止，控制参数种类已经多达几十种，其中，函数( 全) 控制数就是( 全) 控 制数的一类自然推广1 9 9 6 年，b m a g e 3 】等引入了一类推广的图的控制数一弘 控制函数设p 是一实数集，函数i ：v ( a ) _ p 称为图g 的口控制函数，如 果对每个点钞y ( g ) ，有厂( m ) 1 ，这里，n v 】= 扣i “ e ( g ) ) u 伽) ， ，( m ) = 。m ，( t ) 图的刊空制数定义为。 仰= 厕n ，( y ) i ，是g 的p 一控制函数) 当p = o ，1 ) 时则是图的标准控制数；当p = ( - 1 ，1 ) 和p = - 1 ，0 ，1 ) 时，则分 别是图的符号控制数和负控制数其相关研究结果可参见文献f 4 - 2 4 更进一步， 若将对每个点口y ( g ) ，有f ( n t v ) 1 改成对k 个点口y ( g ) ，有厂( 【u 】) 1 ， 则分别是图的符号k 控制数和负k 控制数再将上述定义中的，( m ) 1 改 为厂( ( ) ) 1 就得到相应的标准全控制数、符号全控制数、负全控制数、符号 全k 控制数和负全k 控制数的定义，具体见本文第二章及文献【2 5 - 4 6 下面给出有关负全k 一控制数的个有趣的研究背景，可参考文献【4 6 】例如t 我们考虑某个社会群体网络中的投票问题将其转化为一个图论模型，图中的点 表示个体，两点之间的边表示对应的两个个体具有某种关系给持赞成意见的顶 点赋值+ 1 ，给持中立意见的顶点赋值0 ，给持反对意见的顶点赋值一1 这样图 中度大的顶点具有较大的“影响力”此时负全k 控制数表示即使整体持反对意 见的个体远远多于持赞成意见的个体，但能够保证有至少k 个局部群体所持赞成 意见的个体多于持反对意见的个体，且使得整体和值最小 图的控制数理论之所以如此迅速地发展起来主要是基于以下三个方面的因素： ( 一) 它在现实世界和诸如”覆盖”监控”等数学模型研究中有着广泛而深刻的 应用现实中的许多问题模型都可以归结为图的控制问题例如，一个通讯网络可 以看作一个图，而网络节点与通讯线路就是图的顶点和边在某些网络节点上放 置监控设备来监控整个网络的运行状况，而为了降低成本，总希望在监控整个网 络的情况下，可以选择尽可能少的节点来放置监控设备如何选择这些节点就是 ! q 塑生上整太堂亟主堂僮迨塞 墨 寻找图的最小控制集的问题 ( 二) 控制参数的定义类型具有多样性根据实际背 景的不同，现已定义的控制参数有几十种之多，而且随着研究的深入和应用背景 的不断扩大，新的参数仍在不断涌现( 三) 图的控制参数判定问题的p 完全 性与其它组合优化中户- 完全问题有着紧密而自然的关系在特殊图类( 如树、 弦图、区间图、置换图、路、圈等) 上，研究各类控制参数的计算复杂性已成为组 合优化领域中一个引人入胜而富有挑战性的研究方向 目前，关于函数全控制数的研究主要集中在四个方面： ( 1 ) 确定各种控制参数的上下界，在一些特殊图上计算它们的值； ( 2 ) 寻找各种控制参数之间的关系； ( 3 ) 给出极端图类的结构性质的刻画； ( 4 ) 各种控制参数计算复杂性的研究及其算法的设计 1 2 本文的主要工作 由于图中( 全) 控制函数的引入，致使利用函数性质来研究( 全) 控制数成为 可能。目前，函数( 全) 控制数已成为图的控制理论中一个崭新而富有挑战的研究 方向本文所做的工作主要包括以下两大部分； 第一部分，首先给出了负全k 控制函数是极小的充要条件；接着研究了一些特 殊图如路、完全图、完全二部图中负全l c 控制数的情况；最后建立了一般图和树中 负全l c 控制数的下界及k = n 时，竹的几个下界，并通过给出实例说明了其中一 些下界是可达的 第二部分，首先定义了图的全符号局部控制数，进而得到了全符号局部控制 数在一般图和正则图中的下界以及在完全二部图。中的上界；并求出了圈g 和星妫，n 中诏的精确值 2 0 0 8 年上海大学硕士学位论文 4 第二章基本符号和结论 2 1 基本概念和记号 本文所讨论的图均是无向、无孤立点、无环无多重边的有限简单图凡是文中 未加定义的术语和符号，可参看文献【1 ，4 7 】为了叙述方便，我们首先引入一些定 义和记号设g = ( ve ) 是简单图，y ( g ) ，e ( g ) 分别表示图g 的顶点集和边集， g 的点的数目n = l y ( g ) i 称为图g 的阶数如果图日满足条件v ( h ) v ( a ) 和e ( h ) e ( g ) ，则称日为图g 的个子图对s y ( g ) ，用a s 】表示由s 导 出的子图 图g 中点z v 的开邻域定义为n ( x ，g ) = 妇lx y e ( g ) ) ，x 的闭 邻域为n x ，g 】= n ( x ，g ) up ) 更一般地，对任意的xc y ( g ) ，我们定义 n ( x ，g ) = u 霉x n ( x ，g ) ，n i x ，g 】= n ( x ，g ) ux 6 ( g ) 和a ( a ) 分别表示图g 的最小度和最大度在不引起混淆的情况下，上述符号可分别简记为n ( x ) 、 n x 】、n ( x ) 、n x 1 、6 和对z v u e ，定义蜥( z ) = y l y 与x 相邻或 相关联，y vue ) ，n r m = ( z ) ux 我们称d ( x ) = i ( z ) l 为g 中点x 的 度数，度数为1 和0 的点分别被称为图的悬挂点和孤立点特别地，树中的悬 挂点也叫叶子图g 中度为奇数和偶数的点分别称为奇度点和偶度点若图g 的所有点均为奇( 偶) 度点，则称g 是奇( 偶) 度图所有顶点的度都等于k 的 图g 称为后正则图 由佗个顶点构成的路和圈一般记作r 和吼如果对g 中任意两个顶点牡 和勘，在g 都可以找到连接这两个点的路，则称图g 是连通的，连通的无圈图称 为树若图g 中的任意两个相异点之间都有边相连，则称g 为完全图，n 个 顶点的完全图记作用g = ( m ，v k ；e ) 表示顶点集是u 垒1 ，边集是 z 秒e ( g ) ix k ，y 巧，l i 0 ，至少存在一个点让( 口) ，使得 ，( ( “) ) 1 ，2 ) 类似地，图的符号全控制数即为； 臂( g ) = m i n w ( 1 ) l ，是g 的符号全控制函数) x i n g 4 8 】等人引入图的多数全控制数( m a j o r i t yt o t a ld o m i n a t i o n ) 的概念函数 f ：v ( a ) _ 一1 ，1 ) 称为g 的多数全控制函数，如果y 中至少一半的点，满足 ，( ( w ) ) 1 多数全控制数定义为t 7 ( g ) = m m w ( f ) i ，是g 的多数全控制函数) 最近，x i n g 3 8 】等人还引入了符号全k - 拦2 制数( s i g n e dt o t a lk - s u b d o m i n a t i o n ) 设 七为正整数，1 k i y l 函数厂：v ( a ) 一 一l ，1 ) 称为g 的七一符号全控制函 至q q 垒生土整太堂亟堂僮迨塞曼 数( s t k s f ) ，如果y 中至少存在k 个点，满足，( ( t ，) ) 1 个s t k s ff 是极小 的，如果对每个点t ，v ，不存在g 的个s t k s f9 ，使得g f ，且夕( 口) ，( 口) 则图的符号全七一控制数为； 。( g ) = m i 竹扣( ，) l ，是g 的s tk s f 显然当k = f 等1 ，f y i 时，y 2 。( g ) 分别为多数全控制数和符号全控制数 若将以上定义中的，( ( 秽) ) 改成f ( n v 1 ) ，则可分别得到图g 中负控制数、负 k 一控制数、符号控制数、多数控制数以及符号k - 控制数的定义具体可参见前面 所引用文献【1 2 2 4 】及文献【4 95 7 下面我们给出全符号局部控制数的定义， 设图g = ( ve ) ，令函数f ：vue 一 - 1 ，1 ，f 的权u ( 厂) = e 霉y u e ，( z ) ，对 任一z vue ，定义f x = 蜥扛) ，( 3 ，) 图g 的个全符号局部控制函数为 f ( 简记为f t s l d fo fg ) ：v t je _ 一1 ，1 ) ，满足对所有的z vue 有 f i x 】l ，删图g 的全符号局部控制数为， 程( g ) = m m z o ( f ) i 馒g 的t s l d f ， 并称此，为图g 的幅一函数若将定义中的坼( z ) 改为坼，则按照同样方式 我们可以定义全符号控制数的概念，具体可参见文献【5 8 ，5 9 ，6 0 】 2 2 函数全控制数的主要结果 近些年来对上述各种函数控制参数的研究主要集中在界、各种参数之间的关 系、极图的刻画以及判定问题的复杂性和算法的设计等方面下面我们给出相关 的主要研究结果 关于负全控制数和符号全控制数的研究，给出下面主要结果： 定理2 2 1 ( 1 4 1 ) 若g = ( k ，v k ；e ) 为n 阶后部图，k 2 ，则 7 1 ( a ) 2 占”仡 且此界是可达的 定理2 2 2 ( 【4 4 】) 若g = ( ke ) 为n 阶七一部图，k 2 且6 1 ，令c = f 十1 ) 2 1 则 w ( g ) 占( 一c - 1 ) + v ( c - 1 ) 2 + 4 与i c n ) 川 且此界是可达的 定理2 2 3 ( 【3 9 】) 若g 为i r l 阶k - 9 - 更 l 图，则 w c g ， ；，：兰主萎： 且此界是可达的 定理2 2 4 ( 【3 6 】) 若g 为n 阶图，则w ( g ) 而+ 1 一n ，等式成立当且仅 当g 了 歹是一类图的集合，它的具体构造可参阅文献【3 6 】 定理2 2 5 ( 【3 6 】) 若g 为n 阶图，最小度6 2 ，最大度，则 们川黔黼蒜渊h 且此界是可达的 定理2 2 6 ( 【3 6 】) 若g 为佗阶图，边数为m 则w ( g ) 2 ( n 一竹1 ) 定理2 2 7 ( 【3 6 】) 若t 为n22 阶的树，l ( t ) 为所有叶子的集合，则能( t ) 2 ， 等式成立当且仅当每个点口( v ( t ) 一l ( t ) ) 是奇度点且至少与( d ( v ) 一1 ) 2 个 叶子邻接 下面介绍一些有关符号全控制数和负全控制数的复杂性和算法方面的研究结 果，我们首先给出图的符号全控制数和负全控制数的判定问题形式， 符号全控制数问题 实例。给出图g 和正整数七i v ( g ) i 问题tw ( t ) 七是否成立? 负全控制数问题 实例。给出图g 和正整数k i v ( g ) 1 ! q q 璺生上漫盔堂亟堂僮迨塞墨 问题t 霄( t ) 后是否成立? 2 0 0 4 年，h e l m i n g 证明了符号全控制数的判定问题是尸- 完全的，而h a r r i s 和ha ：t t i n g h 证明了负全控制数的判定问题是p - 完全的 定理2 2 8 ( 【3 6 】) 图的符号全控制数的判定问题是n p - 完全的，即使对于二部图 或弦图也是成立的 定理2 2 9 ( 【3 1 】) 图的负全控制数的判定问题是p 完全的，即使对于二部图或 弦图也是成立的 此外，在文献【3 1 】中h a r r i s 和h a t t i n g h 还给出了树上计算臂( 丁) 和何( t ) 的线 性时间算法 最后我们介绍一些有关多数全控制数和符号全七一控制数方面的研究结果 2 0 0 5 年，x i n g 等人研究了图的多数全控制数，并得到了下列结果。 定理2 2 1 0 ( 【4 8 】) 对f i , 2 ，则 c 址 三：麓 、 定理2 2 1 1 ( 【4 8 】) 对n m21 ，则 c ，= 定理2 2 1 2 ( 【4 8 】) 对n 2 ，则 c r ，= 定理2 2 1 3 ( 4 8 1 ) 对1 1 , 3 ，则 1 一n ，m 为奇数； 2 一n ，m 为偶数 一l ，n 为奇数； 0 ，n 为偶数 c 啦鬻 定理2 2 1 4 ( 【4 8 】) 若g 为佗阶图，最小度和最大度分别为6 1 和a ，则 ( g ) 掣n 定理2 2 1 5 ( 【4 8 】) 若g 为n 阶图，最小度和最大度分别为6 和a ，且图中的点 都为偶度点，则 ( g ) 等n 定理2 2 1 6 ( 【4 8 】) 若g 为1 9 , 阶k - f f ：贝1 l 图( 惫1 ) ，则 c 啦像：麓 i 蚕f n 列i 两氰 且此界是可达的 2 0 0 5 年，x i n g 等人还对七稍号全控制数进行了研究，并得到下列结果； 定理2 2 1 7 ( 【3 8 】) 对仃2 ，则 ，y 2 。( ) = 1 ，n 为奇数且七 i f t ，, 0 ，r , 为偶数且忌詈； 3 ，n 为奇数且詈 k 几； 2 ，n 为偶数且詈 k n 定理2 2 1 8 ( 3 8 1 ) 对7 , m 1 ，则 喉，( j ，n ) = 1 一n ， 2 一n ， 2 ， 3 ， 4 ， m 为奇数且七sn ； m 为偶数且詹n ； m ，几为奇数且n k m + n ； 仇+ 礼为奇数且n k m + n ； m 。n 为偶数且n 坠掣掣n 2 0 0 8 年上海大学硕士学位论文 第三章图中负全后一控制 负全控制问题是近期研究的一个新热点，本章则着重考虑了更一般的 负全k 一控制问题首先给出了负全k 一控制函数是极小的充要条件；接着研 究了一些特殊图如路、完全图、完全二部图中负全k 一控制数的情况；最后 建立了一般图和树中负全k 一控制数的下界及k = n 时，何的几个下界， 并通过给出实例说明了其中一些下界是可达的 3 1 负全k 控制函数 在介绍本章的主要定理之前，我们作以下准备工作， 设，是图g = ( ve ) 的个7 磊一函数如果对点口v 满足厂( ( 秽) ) 1 ， 则称点铷被，覆盖，我们用q 表示被厂覆盖的点集令p ，= p v l i ( v ) = 1 ) ， m s = 刀v i s ( 铆) = - 1 ，q ，= 口v i f ( v ) = o ) b s = v i i ( n ( v ) ) = 1 ) 对于集合a ，j e i y ，如果对任意b b ，有n ( b ) na ，我们称a 完全控制b ， 用a 卜tb 表示若ahy ，则称a 是图g 的一个完全控制集 定理3 1 1 设，是图g 上的一个m t k s f ，如果不存在m t k s fg 满足g tp | u q | 证明；假设，是满足上述条件的一个m t k s f ，但，不是极小的那么存在一个 m t k s fg f ，且有一个k 一子集k 7 g 冬c ，此时存在一点勘v 满足 夕( ) ，( 御) ，即g ( v ) = - 1 ，而s ( v ) = 0 或l ；或者夕( u ) = 0 ，而s ( - ) = 1 + 根据假设 知j e i ，nk 7n tp ) ，即存在一点u b in k 7n ( ) 由，( ) ) = 1 和 n ( w ) 知夕( ) ) 1 ，矛盾所以此时，是极小的 相反，假设，是一个极小m t k s f ，且存在个k 子集q ，使得b s n k 乒t 扣) ，其中口p su q ，下面我们定义一个新函数h ：v 一 - x ，0 ，1 ) ，对于满足 ，( ) = 1 的一个点 ，我们定义 ( 口) = o ；对于u v p ) ，定义 p ) = ，) 若u k nb i ，则ug ( 口) ，也即t ，gn p ) ，那么，l ( ( u ) ) = ，( 0 ) ) 1 若 u k b ，即，( ) ) 2 ，这种情况下有可能刀) 尽管如此，我们仍 可得到 ( 0 ) ) ，( 0 ) ) 一l 1 所以h 是一个m t k s f ，与，的极小性相矛 盾定理证毕 3 2 特殊图中负全k 一控制数的情况 定理3 2 1 对任意路r ( 1 5 2 ) ，l k i r l 一1 有 幅( r ) = - t j ， 若n 是奇数且k = n + ：l ； 警1 一n 幅( r ) 警+ 1 一n ，若n 是奇数，壳是偶数，且2 k n 兰3 ( r o o d4 ) ； 幅( r ) = 警1 一n ， 其它 证明。令r ：v l 忱叻是含n 个点的一条路，是将路r = ( ve ) 中点赋 值一1 的个数为最多的一个最小m t k s f 因此，y 磊( r ) = i 尸，l i 屿1 用，表示 p n 【c ，】中所有孤立点的集合我们首先证明对任一口i 有，( ) = - - 1 否则至少 存在一点口i ，s t f ( n ( v ，) ) 1 ，但是厂( 秽7 ) 一1 此时我们定义另外一个函数 ，7 ，s t ，( 口7 ) = - 1 ，且对所有口叫| 【秽7 ) 满足厂7 ( 口) = ，( 钞) 显然，7 仍然是一 个m t k s f ，但是，( y ) ，( y ) ，矛盾 情况1 i = g ， 也就是说， r 【q 】中所有点都是孤立点，与，中不相邻的点都被赋值一1 若n 是奇数，k i q i 学；若t i , 是偶数，k i q i 鸶显然，对任意 口q ，n ( v ) 尸，uq ，且f ( 口) i = l 或2 情况1 1 n 是偶数显然l p ，i + l q ，i l q l k ，且l p i j q ，j ，则i m s i n - k 因此幅( r ) 冬一一南) = 警一7 1 , ，则幅( r ) f 警1 7 1 , 情况1 2 n 是奇数若k = 学，则i p ，l + i q ，i = i q i l = k l ，且i 毋i i q ，l + 1 该情况下，r 【q 】中孤立点数为孚，且i = c i ，所以l 如i = 孚= 后 因此幅( r ) 考一k = 一言，根据幅( r ) 的整数性，我们有 r s ( p r , ) 一【考j ；若 k 尊翥? 叫； 另一方面，我们将按如下方式定义不同情况下的函数g ：v _ - 1 ，0 ，1 ，： ( & ) k 詈定义 l 1 ，若2 i 2 k ，且i = 4 歹一2 ，j z + 和1 歹半； 9 ( 仇) = 0 ，若2 i 2 k ，且i = 4 j ，j z + 和1 j 喜； 【一1 ，否则 则g 是r 上一个权重为g ( v ) = 璺 一一f 一【刳) = 挚1 一n 的m t k s f ( b ) 7 1 , 是奇数且k = 烈2 定义 i 1 ，若i = 4 歹一2 ，及点v n 一1 ，j z + 且1 歹孚； 9 ( 仇) = 0 ，若i = 4 j ，j z + 且1 js 字； 【一1 ，否贝l j 则g 是r 上一个权重为g ( v ) = f 一k = 一【喜j 的m t k s f ( c ) 1 7 , 是偶数且詈 k 竹一1 在如下几种情况下，我们定义一个m t k s f g ，其赋值一1 的点的个数为佗一k ，且q 中点的个数为n k + n 一2 一k ) = k ( c 1 ) k 是奇数，则礼一k 是奇数若2 k n 兰0 ( m o d4 ) ，定义g 为 ( 夕( 如，夕( ) ) = ( 互至：工! ：! ：二! ：9 ，匹立：叠! ：旦：9 1 一1 ) ， 经检验知g 是一个权重为g ( v ) = 竺乒+ 挚一一k ) = 业2 一n 的m t k s f 若2 k n 三2 ( r o o d4 ) ，定义g 为 ( 夕( 口1 ) ，夕) ) = 1 ，1 ，一1 ，d ，- 1 ，1 ，- 1 ，o ，0 ，1 ，1 ，d ，0 ，1 ，1 ，q ，0 ，1 ，1 ，一1 ) ， 、_ - - _ _ _ _ _ _ _ _ _ _ i _ _ _ _ _ _ _ _ _ - o _ _ _ _ o r 、- _ _ _ _ _ _ _ _ _ 、j _ _ _ _ _ _ _ - _ - ， 至q q 璺生上连太堂亟堂僮迨塞 ! 垒 经检验知g 是一个权重为g ( v ) = 出2+ t 2 k - n - 2 + l 二- 一后) = 学一n 的 m t k s f ( c 2 ) k 是偶数，则n k 是偶数若2 七一亿兰0 ( r o o d4 ) ，定义g 为 ( 夕( 口1 ) ，9 “) ) = ( j 1 ，1 ，- 1 ，d ，- 1 ，1 ，- - 1 ，旦，垒，l ，1 ，o ，0 ，1 ，1 ，9 ) ， 、- _ _ _ _ - _ _ - _ _ _ _ _ _ _ - 一j _ _ _ - _ _ - l _ _ l _ l _ ，、_ _ _ _ - _ - _ _ 、，- _ _ _ - _ - _ _ _ - r 经检验知g 是一个权重为g ( v ) = 墨+ t 2 k - n 一一k ) = 警一n 的m t k s f 若 2 k 一佗三2 ( m o d4 ) ，定义g 为 ( 口1 ) ，夕( ) ) = ( ；1 ，1 ，一1 ，d ，- 1 ，1 ，- 1 ，o - 1 ，1 ，窆，0 ，1 ，i ，o ，0 ，1 ，! ，0 ，0 ，1 ，一 、_ _ _ - _ _ _ _ _ _ _ _ - i _ _ _ - - j _ - _ _ _ _ l _ _ _ _ _ _ _ ，、_ _ _ _ o 、j _ _ _ l _ _ _ _ _ 一 经检验知g 是一个权重为g ( v ) = 下n - k - 2 + 2 + 半- ( n - k ) = 警一佗的m t k s f ( d ) n 是奇数且蛆2 丢( i y i - i y 0 1 ) ，因此i y + i + i y o i ( i y i + i y 0 i ) i y i ；1 x 1 此时按如下方式定义，2 ：v _ ( - 1 ，0 ，1 ，为：对y + 或y o 中的( i x f + 1 ) 2