（运筹学与控制论专业论文）图的边控制函数和全控制函数.pdf

摘要 随着计算机科学的迅速发展，图论随之也得到了飞速发展，而近几十年来图 的控制数理论成为图论中发展最快的领域之一控制数理论能够快速发展的主要 原因是它在组合优化、编码理论、计算机科学、通信网络、监视系统和社会网络等 理论与实践中有着重要的应用背景图的函数( 全) 控制数是经典( 全) 控制数概念 的一类自然推广由于函数的引入，致使利用函数性质来研究( 全) 控制数成为可 能目前，函数控制数已成为图的控制集理论中一个崭新而富有挑战性的研究方 向 人们已发现，对任意图已定义的几类函数控制数的判定问题均是n p _ 完全的， 所以对它们的上、下界进行估计以及对其极值图结构的刻画成为十分有意义的问 题本文研究了几类函数全控制数，其主要结果分为以下两部分： 第一部分( 第三章) ，首先建立了任意图的符号边全控制数( 吒( g ) ) 的几个下 界，接着得到了完全图和完全偶图的符号边全控制数( 心( g ) ) ，这些结果是全新 的；( 有关结果被i n t e r n a t i o n mj o u r n a lo fp u r ea n da p p l i e dm a t h e m a t i c s 录 用) 第二部分( 第四章) ，建立了一些笛卡尔积图的符号全控制数( ( g ) ) 的几个 下界，接着得到了一类特殊有向图的符号全控制数的精确值，这些结果也是最新 的 关键词： 图；边控制函数；符号边全控制数；全控制函数；符号全控制数 至q q 墨生土瀣太堂亟堂焦鲨塞! ! a b s t r a c t 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 ，c o n c u r r e n tw i t ht h eg r o w t ho fc o i n - p u r e rs c i e n c e ，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 es t u d yo fd o m i n a t i o ni n g r a p h si so n eo ft h ef a s t e s tg r o w i n g8 f 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 f d o m i n a t i o nr e s e a r c hi sa t t r i b u t a b l em a l i n l yt oi t s8 0m a n ya p p l i c a t i o n st oo t h e r8 c i - e n c e sa n dr e a lw o r l dp 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 s t e ma n ds o c i a ln e t w o r k t h e o r y ( t o t a l ) d o m i n a t i n gf u n c t i o ni n 擎印1 1 8i st h en a t u r a lv a r i a t i o no fc l a s s i c ( t o t a l ) d o m i n a t i o n t h u s ，i ti sp o s s i b l et os t u d yd 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 n o w a d a y s ，t h es t u d yo nd o m i n a t i n gf u n c t i o n si san e wa n dc h a l l e n g a b l e r e s e a r c hf i e l di nd o m i n a t i o ns e tt h e o r e y p e o p l eh a v ef o u n dt h a td e c i s i o np r o b l e m so fs e v e r a lk i n d so fd o m i n a t i n gf u n - t i o n st h a th a v eb e e nd e f i n e da f en p - c o m p l e t ef o rg e n e r a l 口8 p h s ，8 0i ti sm e a n i n g - f u lt oi n v e s t i g a t eb o u n d so ft 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 ft h e i re x t r e m a l g r a p h s i nt h i sp a p e r ，w em a i n l yi n v e s t i g a t es e v e r a lk i n d so ft o t a ld o m i n a t i n g f u n c t i o n si 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 l 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 i r s t l ye s t a b l i s hs e v e r a ll o w e rb o u n d so n 亿( g ) f o rg e n e r a lg r a p h s a l s o ，w eo b t a i nt h et o t a le d g ed o m i n a t i o nn u m b e r so fc o m p l e t e g r a p ha n dc o m p l e t eb i p a r t i t eg r a p h t h e s ea r et h el a t e s tr e s u l t s i nt h es e c o n dp a r t ( c h a p t e r4 ) ，w ee s t a b l i s hs e v e r a ll o w e rb o u n d so nt h et o t a l s i g n e dd o m i n a t i o nn u m b e ro fc a r t e s i a np r o d u c t so f 留a p h 8 a l s ow eo b t a i nt h e t o t a ld o m i n a t i o nn u m b e r so fas p e c i a lc l a 8 8o fd i r e c t 昏a p h 8 t h e s ea r ea l s ot h e l a t e s tr e s u l t s 呈q q 璺生土整太堂亟堂垡迨塞 ! ! ! k e yw o r d s ：g r a p h ；e d g ed o m i n a t i n gf u n c t i o n ；s 远n e dt o t a le d g ed o m i n a t i o n n u m b e r ；t o t a l ld o m i n a t i n gf u n c t i o n ；s i g n e dt o t a ld o m i n a t i o nn u m b e r 原创性声明 本人声明所呈交的论文是本人在导师的指导下进行的研究工作除了文中特 别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果， 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示了谢意 签名i 羡丑l 虱 日期：7 p 嚼年舌月1 5 日 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即t 学校有权保留论 文及送交论文复印件；允许论文被查阅和借阅；学校可以公布论文的全部或部分 内容 保密的论文在解密后应遵守此规定 繇殳丑l 虱导师张律曳 日期：7 琊年石月，j 日 2 0 0 8 年上海大学硕士学位论文 第一章引言 在近四十年里，随着计算机科学的迅速发展，图论的发展也非常迅猛，其中图 的控制数理论是图论中发展最快的几个领域之一 对图的控制数的研究最早可追溯到十九世纪中期当时有一种棋盘比赛，棋 赛的目的就是用某些棋子覆盖或者控制棋盘上的所有方格人们注意到了在棋盘 上如何放置最少几个皇后就可控制( 覆盖) 或占据所有的方格这样的问题，这就是 图的控制数问题的最初形式 在1 9 6 0 年前后，人们开始对图的控制数进行数学理论方面的研究所公认 的图的控制数理论是在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 gs e t ”和。d o m i n a t i o nn m n b e r 。1 9 7 7 年，c o c k a y n e 和h e d e t - n i e m i 在篇报告中综述了当时已知的有关图的控制数的结果，并且首次使用符号 ，y ( g ) 表示图g 的控制数，此符号一直沿用至今同年，m i c h e l l 和h e d e t n i e m i 引 入了图的边控制概念，并定义了边控制数方面的术语。e d g ed o m i n a t i n gs e t ”和 。e d g ed o m i n a t i o nn u m b e r ”符号，y ( g ) 表示图g 的边控制数此后的2 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 【，驯】在对此领域进行系统总结后，首次出版了 两本关于图的控制数理论的专著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 fd 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 和d i q u e s 在分类条目中专列了一项0 5 c 6 9 关于控制参数理论 研究的全面进展可参阅【3 6 ，3 7 】 呈q 塑生上鎏太堂亟堂焦迨塞至 随着控制数理论研究的深入和应用领域的拓宽，各种控制参数也不断涌现 到目前为止，控制参数种类已经多达几十种，其中，函数( 全) 控制数就是( 全) 控 制数的一类自然推广1 9 9 6 年，b m a g e 【3 】等引入了一类推广的图的控制数一弘 控制函数设尹是一实数集，函数，：y ( g ) 一尹称为图g 的弘控制函数，如 果对每个点可y ( g ) ，有，( m ) 1 ，这里，、r m = t lu 移e ( g ) up ) ， f c n v ) = - ，u e n v ， ) 图的p 啦制数定义为t 修= , m n ( y ) i ，是g 的p 一控制函数) 当尹= 【o ，1 ) 时，则是图的标准控制数；当p = - - 1 ，1 ) 和尹= - 1 ，0 ，1 ) 时，则分别是图的符号控制数和负控制数，其相关研究结果可参见文献【1 4 ，1 7 ， 1 9 ，2 0 ，3 2 ，3 7 ，4 8 ，4 9 ，5 1 ，5 3 ，5 5 ，5 6 ，6 8 】把上述定义中的，( m ) 1 改为 ，( ( 臼) ) 1 就得到相应的全控制数、符号全控制数和负全控制数2 0 0 0 年， z e l i n k a 在图的符号控制数的基础上引入了图的符号边控制数，其相关研究结果可 参见文献 3 0 ，7 8 ，7 9 ，8 0 ，8 2 ，8 5 ，8 6 】- 所有这些控制数的定义具体见本文第二章 所有理论研究的最终目的都是为了更好地应用于实践，图的控制数理论作为 图论的个重要研究领域，在相关科学，例如计算机科学、通信网络、编码理论、 监视系统和社会网络等领域中有着重要的应用同时，随着实际问题的发展，控 制数的种类在不断增加，我们可以根据实际背景的差别来定义不同的控制参数， 从而便于问题的讨论例如公共交换电话网络中的线路交换问题一个典型的边控 制集问题公共交换电话网络的有线电话是从引入线然后进入去话中继线( 假设一 条去话中继线一次只能允许一个电话呼叫) 我们的问题是找出这个网络的最坏情 况，比如当网络饱和并且没有电话呼叫时，最小电话呼叫次数i 是多少我们对这个 问题建立一个二部图所有引入线和中继线构成图的点集，一条引入线与中继线 有边相连当且仅当这条线能切换到中继线所有引入线之间和所有中继线之间没 有边相连这个问题即等价于找出这个二部图的最小独立边控制集 目前，对于控制数的研究主要集中在以下几个方面。 ( 1 ) 确定各类控制参数的上下界，计算一些特殊图的值； ( 2 ) 寻找各种控制参数之间的关系，以及控制参数与图的其他参数，如匹配数 关系的研究； 至q q 璺堡土瀣太堂亟堂僮迨塞墨 ( 3 ) 给出极端图类的结构性质的刻画； ( 4 ) 讨论各类控制参数复杂性问题，算法及在相关科学领域的应用问题 本文的主要工作是研究了几类函数全控制数，其相应的结果为以下两部分 第一部分，首先建立了任意图的符号边全控制数( 心( g ) ) 的几个下界，接着 得到了完全图和完全偶图的符号边全控制数( 亿( g ) ) ； 第二部分，建立了一些笛卡尔积图的符号全控制数( ( g ) ) 的几个下界，接 着得到了一类特殊有向图的符号全控制数的精确值 2 0 0 8 年上海大学硕士学位论文 4 第二章基本符号和结论 2 1 基本概念和记号 本文所讨论的图均是无孤立点、无环无多重边的有限简单图凡是文中未加 定义的术语和符号，可参看文献【5 ，s 6 为了叙述方便，我们首先引入一些定义和 记号设g = ( ve ) 是简单图，y ( g ) ，e ( g ) 分别表示图g 的顶点集和边集，g 的点的数目佗= i y ( g ) i 称为图g 的阶数如果图日满足条件v ( h ) v ( g ) 和 e ( h ) e ( g ) ，则称日为图g 的个子图对s y ( g ) ，用g 吲表示由s 导 出的子图图g 的补图百是指和g 有相同顶点集y 的个简单图，召中两个 顶点相邻当且仅当他们在g 中不相邻若g 不包含k 1 3 作为它的导出子图，则 称图g 是无爪图 图g 中点z 的开邻域定义为n ( x ，g ) = 妇ix y e ( g ) ) ，z 的闭邻域为 k ，g 】= n ( x ，g ) u 扛 更一般地，对任意的x y ( g ) ，我们定义n ( x ，g ) = 魄x n ( x ，g ) ，n x ，g 】= n ( x ，g ) ux 在不引起混淆的情况下，上述符号可分别 简记为( z ) ，n ( x ) 和】我们称d ( z ) = i ( 。) i 为点z 的度数，度数 为1 和0 的点分别被称为图的悬挂点和孤立点。特别地，树中的悬挂点也叫叶 子分别用6 ( g ) 和( g ) 表示图g 的最小度和最大度图g 中度为奇数和偶数 的点分别称为奇度点和偶度点所有顶点的度都等于k 的图g 称为詹正则图 若图g 所有顶点的度都等于k 或七一1 ，我们称图g 称为几乎七正则图若图g 中两个不同的顶点在g 中是不邻接的，则称它们是独立的如果点集s v ( a ) 中所有点都是相互独立的，则称s 是g 的独立集 图g 中的边e e ( g ) 的开邻域定义为n a ( e ) = e 7 e ( g ) ie ，与e 邻接) ， e 的闭邻域定义为g 【e 】= ( e ) ue 对任意的t ，冬y ( g ) ，我们定义上k ( z ，) = _ 【伽e ( g ) it l y ( g ) ) 为了方便，上述符号可分别简记为( e ) ，n e 】和e ( 口) 我们称d ：g ( e ) = i ( e ) i 为边e 的边度分别用7 和艿7 表示图g 的最大边度和最 小边度对于个图g ，设易和最分别表示由有奇数边度和偶数边度的边构成 的集合对m e ( g ) ，用g ( m ) 表示由m 诱导的边导出的子图若m 中任 ! q q 璺生土整太堂亟三匕堂僮迨塞墨 意两条边在g 中是不相邻的，则m 称为g 的匹配或边独立集如果m 的某 条边与v 关联，则称匹配m 饱和顶点t ，或者称t ，是m 饱和的，否则，称秒是 m 非饱和的m 中一条边的两个端点称为在m 下是配对的设v ( m ) 表示匹 配m 所饱和的点集，若满足v ( m ) = y ( g ) ，则称m 为g 的完美匹配 由佗个顶点构成的路和圈一般记作r 和q 若图g 中的任意两个相异点之 间都有边相连，则称g 为完全图，n 个顶点的完全图记作k 。若图g 中任意两 个点让和t ，之间都有条路相连，则图g 称为连通的g 中任意两个点u 和秽之 间最短路的长度称为u 和秽之间的距离，用d ( 让，t ，) 表示图g 中任意两个点之 间的最长路的长度称为图g 的直径，用d i a m ( g ) 表示通过划分图g 中的每条 边仅一次后所得到的图称为图g 的划分( s u b d i v i s i o n ) 用g = ( ，k ，k ；e ) 表示顶点集是u 整l k ，边集是 z 秒e ( g ) lz k ，y 巧，1 i 设，是定义在边集e 上的实值函数，伽( ，) = 。e f ( e ) 称为，的权对任 意子集m 刀，我们定义s ( m ) = 。m ，( e ) ，因此伽( ，) = ，( e ) 有时为了方便 起见，对边e e ，我们将，( 【e 】) ) 简记作，f e 】 z e l i n k a 【8 6 】引入了图的符号边控制数概念设，：e ( g ) _ - t ，1 ) 是定义在 e 上的函数，我们称函数，为图g 的符号边控制函数( s i g n e de d g ed o m i n a t i n g f u n c t i o n ) ，如果对于任意一条边e e ( g ) ，有。，司，( e ) 1 图g 的符号边 控制数( s i g n e de d g ed o m i n a t i o nn u m b e r ) 定义为 7 o ( a ) = r a i n ( e ) l ，是g 的符号边控制函数) e e ( g ) x u 8 0 】引入了图的符号星控制数( 也称局部符号边控制数) 概念设厂： e ( a ) _ 一1 ，1 ) 是定义在e 上的函数，我们称函数，为图g 的符号星控制函 数( s i g n e ds t a rd o m i n a t i n gf u n c t i o n ) ，如果对于每个点钞y ( g ) ，有。e ( 。) l ( e ) 1 图g 的符号星控制数( s i g n e ( is t a rd o m i n a t i o nn u m b e r ) 定义为 心( g ) = r a i n ，( e ) i ，是g 的符号星控制函数) e e ( g ) 图的局部符号边控制数( l o c a ls i g n e de d g ed o m i n a t i o nn u m b e r ) 用啊( g ) 表示 最近，s a e i 【6 5 】等人还引入了图的七一符号星控制设，：e ( g ) _ - 1 ，1 ) 是 定义在e 上的函数，我们称函数，为图g 的壳一符号星控制函数( 南一s i g n e ds t a r d o m i n a t i n gf u n c t i o n ) ，如果y 中至少存在k 个点秽，满足。e ( 锄) ( e ) 1 图g 的座一符号星控制数( 南s 追n e ds t a xd o m i n a t i o nn u m b e r ) 定义为 镌( g ) = r a i n ，( e ) i ，是g 的忍符号星控制函数) 本文基于图的符号边控制的概念，引入了图的符号边全控制的概念函数f ： e ( g ) _ - 1 ，1 ) 称为图g 的符号边全控制函数( s 蜘dt o t a le d g ed o m i n a t i n g f u n c t i o n ) ，如果对任意一条边e e ( g ) ，有。， ，( 。) f ( e ) 1 图g 的符号边全 控制数( s i g n e dt o t me d g ed o m i n a t i o nn u m b e r ) 定义为 心( g ) = m i n f ( e ) i ，是g 的符号边全控制函数) e e ( g ) 显然，对任意非连通图g ，我们可以定义( g ) = 0 ，因为- i e ( g ) i 亿( g ) l e ( g ) i 对任意两个不相交的图g 1 和岛，都满足忆( g au g 2 ) = ( g 1 ) + 心( g 2 ) 下面我们给出与本文相关的一些函数全控制数的概念 1 9 8 0 年c o c k a y n e 【1 0 等人首先引入了全控制的概念设s y ( g ) ，s 称 为g 的全控制集，如果对每一个点 v ，口至少邻接于s 中的一个点，也即 n ( s ) = y ( g ) 如果对任意点钞s ，都有s m 不再是g 的全控制集，则称s 为g 的个极小全控制集图的全控制数t t ( a ) 定义为g 的最小全控制集的点 数，也即仳( g ) = m i n i s i ls 是g 的极小全控制集) 图的上全控制数定义为 r ( g ) = m 1 蚓is 是g 的极小全控制集) 。 设，是定义在点集y 上的实值函数z o ( f ) = 蚝矿f ( v ) 称为，的权对任 意子集s y ，我们定义f ( s ) = 掣s ，( 口) ，因此叫( ，) = 厂( y ) 为了方便起见， 对点t ，v 我们将，( ( 口) ) 简记作f l y 设f ：y ( g ) _ o ，l 是定义在y 上的 函数，我们称，是g 的全控制函数，如果对每个点铆v 有，m 1 如果对 每个点移v ，不存在全控制函数g ：v ( g ) 一 o ，1 ) ，g f ，满足夕( 秽) ，( 秽) ， 则称，是一个极小全控制函数图的全控制数和上全控制数即为， 饥( g ) = m 讯扣( ，) i ，是g 的全控制函数) 和 r t ( g ) = m 彻 钮( ，) i ，是g 的极小全控制函数) z e l i n l mf 8 4 】引入图的符号全控制数( s i g n e dt o t a ld o m i n a t i o n ) 的概念函数 ，：v ( g ) _ 一1 ，1 ) 称为g 的符号全控制函数，如果对任意点 1 3 v ，有fr y 】1 2 q q 墨生土篷太堂亟堂僮迨塞璺 个符号全控制函数，是极小的当且仅当对每一个点口vf ( - ) 0 ，至少存在 个点t ( 秽) ，使得，m 1 ，2 ) 图的符号全控制数和上符号全控制数分 别定义为t w ( g ) = 删铭扣( ，) i 馕g 的g f q - 全控制函数 和 r ( g ) = m 扣( ，) i ，是g 的极小符号全控制函数 x i n g ( 7 6 j 等人引入图的多数全控制数( m a j o r i t yt o t a jd o m i n a t i o n ) 的概念 函数f ：v ( c ) _ - 1 ，1 ) 称为g 的多数全控制函数，如果y 中至少一半的点， 满足，m 1 多数全控制数定义为， ，y ( g ) = m i n w ( f ) i ，是g 的多数全控制函数) x i n g 【7 7 等人还引入了图的“符号全控制数( k - s i g n e dt o t a ld o m i n a t i o n ) 设 k 为正整数，1 k l v l 函数f ：v ( g ) 一 一l ，1 ) 称为g 的庇一符号全控制函 数( k s t f ) ，如果y 中至少存在k 个点，满足f n 1 个k s t ff 是极小的， 如果对每个点秒v ，不存在g 的一个k s t fg ，使得g f ，且g 扣) 厂( 口) 图 的一符号全控制数和上符号全控制数分别定义为； 磺。( g ) = m 轨 叫( ，) l ，是g 的k s t f 和 r 2 5 ( g ) = 竹矗n 包u ( ，) l ，是g 的极硝、k s t f 显然当k = 掣1 ，i v i 时， 。( g ) 分别为多数全控制数和符号全控制数，而当 k = l v l 时，r 。( g ) 就是上符号全控制数 h a r r i s 【3 5 】等人弓l 入图的负全控制数( m i n u st o t a ld o m i n a t i o n ) 的概念函数 f ：v ( g ) _ - 1 ，0 ，1 称为g 的负全控制函数，如果对任意点钉v ，有f - 】1 个负全控制函数，是极小的当且仅当对每一个点口vf ( - ) 0 ，且至少存在 个点t ( 移) ，使得外q = 1 图的负全控制数和上负全控制数即为。 竹( g ) = m i n 伽( f ) l ，是g 的负全控制函数) 和 h ( g ) = m a x w ( f ) i ，是g 的极小负全控制函数) 目前，对图的符号全控制数的研究仅限于无向图本文将这一定义引入到有向 图上本文所讨论的有向图不含有环，也没有_ 对点被两条弧相连设d = ( ka ) 是 个有向图，v ( d ) 和a ( d ) 分别表示图d 的点集和弧集对任意点口y ( d ) ， 如果只有从秽出发的弧而没有到达御的弧，称御为源点，本文所讨论的有向图不 含有这样的点对任意点移y ( d ) ，秒的外邻域和内邻域分别定义为+ 扣) = “i u u a ( d ) 和一扣) = 托l 删a ( d ) ) 进一步，用d + ( 秽) = f n + ( 秽) i 和 d 一( 口) w - - 1 n 一 ) 1 分别表示御的出度和入度函数f ：v ( d ) 一 - 1 ，1 称为图d 的个符号全控制函数，如果对每个点移y ( d ) ，满足f ( n 一( 钐) ) 1 图d 的符 号全控制数定义为 ( d ) = 撕竹如( ，) i ，是g 的符号全控制函数 2 2 函数边控制数的主要结果 近些年来对上述各种控制函数参数的研究主要集中在界、判定问题的复杂性、 算法、各种参数之间的关系以及极图的刻画等方面下面我们给出相关的主要研 究结果本节主要给出边控制数方面的研究成果 关于边控制数方面的研究主要有以下结果， 定理2 2 1 ( f 4 7 】) r ( q ) = p 3 ，p 3 定理2 2 2 ( 8 1 ) 若g = ，g ) ，则，y 7 ( g ) t p 2 j 定理2 2 3 ( 4 7 1 ) 若g = 白，g ) ，则，y ( g ) q 一7 定理2 2 4 ( 4 7 1 ) 若g = ，g ) ，则7 ( g ) q 一尻+ q o 其中q o 是图g 中独立边 的数目 呈q 塑生上盘太堂亟堂垡迨塞! q 尻的定义见文献【4 7 】 定理2 2 5 ( f 4 7 】) 若g = ( 鼽d ，则7 ，( q + ( g ) 冬q + 1 ( g ) 的定义见文献【4 7 】 下面七个定理是对上面几个定理的优化和改进 定理2 2 6 ( f 2 d 若g 是p 阶连通图并且p 是一个偶数，则r ( g ) = p 2 ，当且仅 当g 与或2 , p 2 同构 定理2 2 7 ( 【2 】) 若t 为p 2 阶的树，则y ( t ) ( p 一1 ) 2 ，等式成立当且仅当 丁与星图的划分同构 定理2 2 8 ( 2 1 ) 若g 为p 阶连通单圈图，则- ( g ) = b , 2 j ，当且仅当对某些 竹0 ，g 与吼，瓯，研，q ，。或瓯，作任意一个同构 岛，n 和c k n 的定义见文献 2 1 定理2 2 9 ( 2 1 ) 若t 为边数q 的树，e = 伽为一条有最大边度a 7 的边，则 一( 力= q 一7 ，当且仅当d i a m ( t ) 4 并且对每个点卸满足d ( w ) 2 定理2 2 。1 0 ( 【2 】) 若g 为含有圈c 的连通单圈图，边敷为g ，则r ( g ) = g a ， 当且仅当以下六个条件的任意一个成立- ( i ) g = 锈 ( 西) c = 岛= ( u 1 2 , 3 1 , 1 ) ，d ( u t ) 3 ，d ( u 2 ) = d ( u a ) = 2 ，对所有不在g 中的 点t t ，d ( u t ，t l j ) 2 并且最多有一个不在c 中的叫满足d ( w ) 3 ( i i i ) ，c = 岛= ( 1 钍2 “1 ) ，d ( u x ) 3 ，d ( u 2 ) 3 ，d ( u a ) = 2 ，所有与u 1 相邻 且不在c 中的点的度数最多是2 并且所有与u l 的距离为2 的点都是悬挂点 a t ，) ，c = 岛= ( u l u 2 u 3 m ) ，以铭i ) = 3 ，硪u 2 ) 3 ，d ( u a ) 2 ，所有不在e 中 的点都是悬挂点 ) g = q ( 讲) c = c 4 ，仅仅只有c 中的一个点或d 中的两个相邻点的度数至少是? 并且所有不在c 中的点都是悬挂点 至q q 墨生土鲞太堂亟堂垡迨塞! ! 定理2 2 1 1 ( 【2 】) 若g 为边数口的连通图，则r ( g ) = q 一尻，当且仅当g 与瓯 同构或者g 是一个星图的划分 定理2 2 1 2 ( 【2 】) 若g = ，g ) ，则y ( g ) + ( g ) = q + 1 ，当且仅当g = c 3 ， 甄扩l 或者竹妫 在最小度相同的情况下，给定一个正整数k ，若图中阶数足够大并且k 个不相 交的圈尽可能含有足够多的点，f u j i t a 等人证明了这些圈组成图的个边控制集 定理2 2 1 3 ( 【6 0 】) 若k 为一个正整数，g 为阶数佗4 4 的2 连通图，6 ( n + 2 ) 3 ， 则对每个由k 个不相交的圈组成的最大集，u 是图g 的一个边控帝j 集 当k = 1 时就得到文献【2 8 】的结果，最大集专和蜒的定义见文献【6 0 】- 下面给出立方体图的边控制数的一个研究成果； 定理2 2 1 4 ( f 8 5 j ) 若n 为一个正整数，则，y ( q 露) 2 舾1 q 。表示磁隹立方体，具体定义见文献 8 5 】 其他有关边控制问题的研究成果可参阅文献【7 ，3 4 ，4 6 ，5 7 】， 下面介绍些有关边控制集复杂性和算法方面的研究结果，我们首先介绍p 完全理论中判定问题( d e c i s i o np r o b l e m ) 的概念类问题，如果它的每个实例都 可以表述为用“是”或“否”来回答的形式的话，那么称之为判定问题图的边控 制集判定问题形式为： 输入t 图g = ( ve ) 和正整数七； 属性g 中是否有个最多含有詹条边的集合控制其他所有边? 1 9 8 0 年，y a a n a k a k i s 和g 目v r i l 证明了图的边控制集问题是p ? 完全的 定理2 2 1 5 ( 【8 1 】) 图的边控制集问题是p 一完全的，即使对于最大度为雪的平 面图或二部图也是成立的 至q q 璺生土整太堂亟堂垡途塞 ! 至 2 0 0 5 年，b e r g e r 和p a r e k h 【4 】给出了般边控制集问题的线性时间算法同 年，r a a d e r a t h 和s c h i e r m e y e r 6 3 】给出了边控制集的第个精确算法，时间复杂 度为o ( 1 4 4 2 3 ”) 后来，s a 工n s i l 6 4 】等人也给出了个时间复杂度为o ( 1 4 4 2 3 n ) 的算法，丽f o m i n 【2 7 】等人的算法将时间复杂度改进为o ( i 4 0 8 2 n ) 2 0 0 7 年1 2 月，r d o i j 和b o d l a e n d e r 【7 2 】在他们的一篇报告中给出了时间复杂度为o ( 1 3 2 2 6 n ) 的精确算法 其他有关边控制问题的算法方面的研究成果可参阅文献【6 ，1 6 ，2 5 ，2 9 ，5 8 ，7 0 ， 8 7 关于符号边控制数的研究，给出下面主要结果： 定理2 2 1 6 ( 【8 6 】) 若m ，g 为正整数，1 g m ，g = m ( m o d 2 ) ，并且当m 是 奇数时，g 竹l ，当m 是偶数时，9 m 一2 ，则存在一颗m 条边的树t 使得 t ( 丁) = g z e l i n h 【8 6 】猜测对于所有的树，( t ) 1 均成立y u 【8 2 】在他硕士论文里证 实了这个猜想j 比外，他还对z ( t ) = 1 所须具备的条件做了说明 定理2 2 1 7 ( s 2 1 ) 若t 是n 3 阶的树，则t ( t ) = 1 ，当且仅当对每个点 移v ( t ) 有d ) 兰l ( m o d 2 ) 并且对每个点u v ( b r ) 有d ( u ) 2 d b t ( u ) 一1 b t 的定义见文献【8 2 】 定理2 2 1 8 ( 【7 8 】) 若g 为一个边数为m 的图，令皿( m ) = m 讯“( g ) ) ，则 晰冲b 逝掣1 1 - m 定理2 2 1 9 ( 【7 9 1 ) 若g 为竹阶图，边数为m ，则z ( g ) 竹- m ，且此界是可达 的 定理2 2 2 0 ( s o d 若g 为扎阶图，则能( g ) 【警一1 j 至q q 墨生上整太堂亟堂焦迨塞 ! 墨 - _ _ _ - _ - _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ - _ - - - _ _ _ - _ - _ - _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - - _ _ - _ _ - _ _ - _ _ _ _ _ l _ - - _ _ _ _ _ _ _ _ _ _ _ - 。 _ _ _ _ - _ _ 。一一 下一个定理证明了文献【8 0 】中的一个猜想是不正确的 定理2 2 2 1 ( 【3 。】) 能( g m 。：一丛! 二旦型( 南2 ，m 1 ) g 。七的具体构造见文献【3 0 】 关于符号星控制数和b 符号星控制数方面的研究主要有以下结果： 定理2 2 2 2 ( s o d 若g 为佗4 阶图，则吒( g ) 2 n 一4 ，且此界是可达的 定理2 2 2 3 ( s o d 若g 为铭阶图，边敷为m ，令眈( g ) = p v ( a ) ld ( 移) 3 ， 则吒( g ) = m ，当且仅当d 3 ( g ) = d 或者d 3 ( g ) 是g 的一个独立集 定理2 2 2 4 ( 【7 3 】) 若g 为n g 2 阶图，边数为m g ，且有k a 个奇度点，日为 扎日2 阶图，边数为仇日，且有b 个奇度点，则 ，( g 3 h ) m i n n l t t u ( g ) + n a t ( h ) ，r 垴t u ( h ) + 死日丁( g ) ) ， 丁( g ) = m i 佗 ( g ) ，七g + 芈) ，丁( 日) = m m t u ( h ) ，忌日+ 兰芈 定理2 2 2 5 ( 【6 5 】) 若g 为阶数n 2 且无孤立点的图，则 吨( g ) 坠半型 定理2 2 2 6 ( 【6 5 】) 若g 为阶数佗2 且无孤立点的图，边数为m ，度序列为 ( d l ，厶) ，并且d l 奶厶，则 花( 啦学一 定理2 2 2 7 ( 【6 5 】) 若g 为阶数礼2 且无孤立点的图，边数为m ，则 吨( g ) ( m + 后) 一( 2 m + n ) a 砺+ ( n 一- k ) a 2 2 3 函数全控制数的主要结果 近些年来对函数全控制的研究已经越来越深入，下面我们给出相关的主要研 究结果 关于全控制数方面的研究主要有以下结果t 定理2 3 1 ( 1 0 1 ) 若g 是阶佗( 3 ) 的连通图，更l l ( g ) 2 n 3 ，且此界是可达 的 定理2 3 2 ( 【3 8 】) 若g 为阶n 的连通图，最小度6 ( g ) 2 ，且g 譬 岛，g ，岛，g i n ， 则m ( g ) 4 n 7 定理2 3 3 ( 2 3 1 ) 若g 为阶n 的图，最小度艿( g ) 3 ，则能( g ) 7 绍1 3 下一个定理是文献【2 3 】中的猜想，2 0 0 4 年分别被a r c h d e a c o n 等八位研究者 独立地解决了 定理2 3 4 ( 【1 】) 若g 为阶n 的图，最小度j ( g ) 3 ，则仉( g ) 冬2 ，且此界是 可达的 ， 2 0 0 7 年，t h o m a s s e 和y e o 得到了关于全控制数的一个新上界 定理2 3 5 ( 7 1 1 ) 若g 为阶佗的图，最小度6 ( g ) 4 ，则m ( g ) 3 n 7 最近，h e n i n g 和k a n g 等人研究了图的匹配教和全控制数的关系 定理2 3 6 ( 【4 4 】) 若g 为k - 正- 1 l l i 图， 詹3 ，则m ( g ) 口( g ) 0 ，( g ) 为图g 的匹配数 其他有关全控制数的研究成果可参阅文献【1 1 ，1 3 ，2 6 ，4 0 ，4 1 ，4 3 关于上全控制数方面的研究主要有以下结果 定理2 3 7 ( 【2 4 】) 若g 为佗阶的连通无爪图，最小度为6 ( g ) ，则 蹦哪伊裂k 此外，r ( g ) = 2 + 1 ) 3 当且仅当g 多lu 疡i 若艿 3 ，4 ，5 ) ，则r t ( g ) = 4 n ( 6 + 3 ) 当且仅当g 玩或6 = 5 时g 乃若6 6 ，则r t ( g ) = n 2 当且仅 当g 厂 玩u 岛，玩和厂的构造见文献【2 4 】 下面介绍些有关全控制数和上全控制数的复杂性方面的研究结果， 定理2 3 8 ( 【6 l 】) 对于一个给定的二部图或弦图g 和一个正整数七i y i ，判定 m ( g ) k 是否成立是p 完全的 定理2 3 9 ( 【2 2 1 ) 对于一个给定的图g 和一个正整数k i v l ，判定r t ( g ) k 是否成立是p 皖全的 关于符号全控制数的研究，给出下面主要结果。 定理2