（运筹学与控制论专业论文）图的控制划分数.pdf

2 0 0 7 年上海大学硕士学位论文 摘要 在过去的三十多年里，随着计算机科学的迅速发展，图论也得到了飞速发展， 而控制数理论的研究是图论中发展最快的几个领域之一控制数理论能够快速发 展的主要原因是它在组合优化、编码理论、计算机科学、通信网络、监视系统和社 会网络等理论与实践中有着重要的应用背景随着研究的深入和应用的激发，各种 新的参数不断涌现其中图的控制划分数就是在图的控制集的基础上被提出的 由于图的控制划分数在社会网络的选址问题中有很多的应用，越来越多的研究人 员开始关注这个参数 长期以来，图的控制划分数( d ( g ) ) 和全控制划分数( 也( g ”一直受到关注 之后，由于图的控制函数的 孽埝的引入，人们开始借助函数性质来研究控制划分 数本文主要研究了符号全控制船分数( 啦( g ) ) ，并且给出了一些关于符号控制划 分数( 以( g ) ) 和符号全控制划分数( 啦( g ) ) 的n o r d h a u s - g a d d u m 型结果 其相应的结果分为以下两部分： 第一部分，首先定义了图的符号全控制划分数；接着给出了它的一些基本性 质和它在正则图上的可达界，同时得到了在完全图上和在一些特殊图上的符号全 控制划分数( 有关结果被j o u r n a lo fs h a n g h a iu n i v e r s i t y 录用) 第二部分，建立了图的符号控制划分数与其补图的符号控制划分数两者的和 的上界，并且对达到上界的极图进行了刻画，同时得到了这两个参数的积的下可 达界和上界；然后给出了图的符号全控制划分数与其补图的符号全控制划分数两 者的和的可达上界，同时得到了这两个参数的积的下可达界和上界；最后研究了 图的符号( 全) 控制数与其符号( 全) 控制划分数的和的上界，并且对达到上界的极 图进行了刻画 关键词： 图；符号全控制划分数；符号控制划分数；符号全控制数；符号控制数 2 0 0 7 年上海大学硕士学位论文 i i a b s t r a c t w i t ht h er a p i dg r o w t ho fc o m p u t e rs c i e n c e ，t h el a s tt h i r t yy e a r sh a v ew i t - n e s s e dt h ee x p l o s i v eg r o w t ho fg r a p ht h e o r y t h es t u d yo fd o m i n a t i o ni ng r a p h si s o n eo ft h ef a s t e s tg 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 sa 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 s a 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 i n - 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 kt h e o r y w i t hd e e pr e s e a r c h ，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 t h ei n t r o d u c t i o no fd o m a t i cn u m b e ri sb a s e do i lt h ec o n c e p to fd o m i n a t i o n s e t t h ed o r a a t i cn u m b e rw h i c ha t t r a c t sa t t e n t i o nf r o mm o r ea n dm o r er e s e a r c h e r s a r ea t t r i b u t a b l em a i n l yt oi t sa p p l i c a t i o n so fl o c a t i n gf a c i l i t i e si nan e t w o r k t h ed o m a t i cn u m b e r ( d ( g ) ) a n dt o t a ld o m a t i cn u m b e r ( d r ( g ) ) o fg r a p h sh a v e b e e nr e s e a r c h e d f o r a l o n g t i m e b e c a u s e o f t h e i n t r o d u c t i o n o f d o m i n a t i n g f u n c t i o n i ng r 印h s ，i ti sp o s s i b l et os t u d yd o m a t i cn u m b e ri nt e r m so ff u n c t i o n a lp r o p e r - t i e si nr e c e n ty e a r s t h i sp a p e ri n t e n d st oi n v e s t i g a t es i g n e dt o t a ld o m a t i cn u m b e r ( d s ( g ) ) ，a n dg i v es o m en o r d h a n s - g a d d u mt y p er e s u l t sa b o u ts i g n e dd o m a t i ch u m - b e r ( 也( g ) ) a n ds i g n e dt o t a ld o m a t i cn u m b e r ( 哦( g ) ) t h ec o r r e s p o n d i n gr e s u l t s a 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 ) ，s i g n e dt o t a ld o m a t i cn u m b e ri sf i r s td e f i n e d ，w h i c h i sf o l l o w e db yt h es t u d yo fi t sb a s i cp r o p e r t i e s as h a r pu p p e rb o u n do nt h es i g n e d t o t a ld o m a t i cn u m b e ro fr e g u l a rg r a p hi sa l s oe s t a b l i s h e d f u r t h e r m o r e ，t h es i g n e d t o t a ld o m a t i cn u m b e ro fc o m p l e t eg r a p ha n ds o m es p e c i a lg r 印h sa r ed e t e r m i n e d i nt h es e c o n dp a r t ( c h a p t e r4 ) ，t h eu p p e rb o u n do nt h es u mo fs i g n e d ( t o t a l ) d o m a t i cn u m b e ro nag r a p ha n di t sc o m p l e m e n ti se s t a b l i s h e d t h es h a r pl o w e r b o u n da n du p p e rb o u n do nt h ep r o d u c to fs i g n e d ( t o t a l ) d o m a t i cn u m b e ra n d s i g n e d ( t o t a l ) d o m i n a t i o nn u m b e ro nag r a p ha r ea l s oe s t a b l i s h e d ，f u r t h e r m o r e ， t h eu p p e rb o u n do nt h es u mo fs i g n e d ( s i g n e dt o t a l ) d o m i n a t i o nn u m b e ra n ds i g n e d ( s i g n e dt o t a l ) d o m a t i cn u m b e ro nag r a p hi sg i v e n m e a n w h i l e ，t h es u f f i c i e n ta n d 2 0 0 7 年上海大学硕士学位论文 i i i n e c e s s a r yc o n d i t i o n sf o rt h ee q u a l i t ya t t a i n i n gt h eu p p e rb o u n da r eg i v e n k e yw o r d s ：g r a p h ；s i g n e dt o t a ld o m a t i cn u m b e r ；s i g n e dd o m a t i cn u m b e r ； s i g n e dt o t a ld o m i n a t i o nn u m b e r ；s i g n e dd o m i n a t i o nn u m b e r 原创性声明 本人声明t 所呈交的论文是本人在导师的指导下进行的研究工作除了文中特 别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果， 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示了谢意 签名 罐梅 日期：助声6 月日 一 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即t 学校有权保留论 文及送交论文复印件；允许论文被查阅和借阅；学校可以公布论文的全部或部分 内容。 保密的论文在解密后应遵守此规定 签名 日期 僦名：传勺奚 6 只j | b槲盼 2 0 0 7 年上海大学硕士学位论文 第一章引言 在近四十年里，随着计算机科学的迅速发展，图论的发展也非常迅猛，其中图 的控制数理论是图论中发展最快的几个领域之一控制数理论能够快速发展的主 要原因是它在组合优化、编码理论、计算机科学，通信网络，监视系统和社会网络 等理论与实践中有着重要的应用 对图的控制数的研究最早可追溯到十九世纪中期当时有一种棋盘比赛，棋 赛的目的就是用某些棋子覆盖或者控制棋盘上的所有方格人们注意到了在棋盘 上如何放置最少几个皇后就可控制( 覆盖) 或占据所有的方格这样的阿题，这就是 图的控制数问题的最初形式 在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 u m 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 的控制数，此符号一直沿用至今 图的控制集必定存在且往往具有不唯一性，那么对一个确定的图g 而言，它 的点集v ( a ) 可以分成多少个互不相交的控制集这样一个问题也是很有意义的。 以前面的棋盘比赛为例，要想以几个皇后来控制整个棋盘可以有不同的布局，如 果说每个棋格在所有的布局中只能被皇后占用一次的话，那么可以采用的不同的 布局总数也是人们常常思考的问题针对这类问题的出现，在1 9 7 7 年，c o c k a y n e 和h e d e t n i e m i 驯提出了控制划分“d o m a t i cp a r t i t i o n ”的概念，并进一步给出 了控制划分数“d o m a t i cn u m b e r ”的定义，用符号d ( a ) 来表示在1 9 8 0 年， c o c k a y n e 刮等又在全控制划分。t o t a ld o m a t i cp a r t i t i o n ”的基础上提出了全控制 划分数4t o t a ld o m a t i cn u m b e r ”的概念，并且用符号吨( g ) 来表示此后的1 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 【1 4 ，曲】在对控制数这一领域进行系统 2 0 0 7 年上海大学硕士学位论文2 总结后，首次出版了两本关于图的控制数理论的专著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 ，其中均有专 门的章节介绍图的控制划分数的相关结果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 e 6 9 随着控制数理论研究的深入和应用领域的拓宽，各种控制参数也不断涌现 到目前为止，控制参数种类已经多达几十种，控制函数“d o m i n a t i n gf u n c t i o n ” 概念的提出使得各种函数控制数如雨后春笋般纷纷涌现，与此同时，各种控制划 分参数也被纷纷引入1 9 9 0 年，r a u 9 0 1 给出了控制划分数的的函数角度的解 释在此基础上，他进而定义了一类新的图的控制划分数一一图的分数控制划分 数“f r a c t i o n a ld o m a t i cn u m b e r ”相隔十五年之后，仿照图的分数控制划分数 的定义。v o l k m a n n i j u l 等在2 0 0 5 提出了图的符号控制划分数“s i g n e dd o m a t i c n u m b e r ”的概念，使得控制划分数的研究往前进了很大一步，进而，使得控制划 分参数的成员拓宽到了符号控制的领域其相关研究结果可参见文献f 3 2 ，3 3 ，3 5 ， 3 9 ，4 5 ，4 6 1 它们的定义具体见本文第二章 图的控制划分数在网络的设备选址问题中有很强的应用背景例如，在某个 社会网络中要配备一些必需的公共设施，例如学校、医院等等，并且对这个网络中 的每个地点有这样的要求，如果在该地点上没有配备公共设施，那么必定在它邻 近的地方配备这样的设施社会网络不可能只需要一种设施，人们总是期望在附 近可以有尽可能多的便利设施，如果每个地点都有一个有限的容量，那么整个网 络中可以提供的资源量必定是有限的这个网络中所能配置的最多的资源数是人 们经常需要解决的问题 现在我们把这个社会网络看成是一个图，每个地点看成是图中的节点，每个 地点问的道路看成是图中的边那么上面的资源配置问题就可以理解成；如果在 某节点上没有配备公共设施，那么必定在它的邻点上要有这样的设施显然这些 设施所占用的节点在一起构成的就是这个网络所对应的图的控制集如果每一个 节点上都最多只能配备一种设旌也就是说，每种设施要占用一个控制集，那么， 一个社会网络中可以配备的最多的设魉的数目就是其对应的图的控制划分数在 统筹安排中，人们就可以根据其对应的图的控制划分数的值，将这些公共设施按 照其重要性进行排序，从而完成对该社会网络的资源配置事实上，每个节点配备 有限个资源量的问题可以转化为每个节点最多只能配备一种资源的问题来考虑， 2 0 0 7 年上海大学硕士学位论文 3 所以人们主要研究每个节点最多只能配备一种资源的问题，也就是去研究与这些 实际问题相应的图的控制划分数的问题 目前，对于图的控制划分数的研究主要集中在以下几个方面。 ( 1 ) 确定各种控制划分参数的上下界，在一些特殊图上计算它们的值； ( 2 ) 寻找控制划分数和其他控制参数之间的关系； ( 3 ) 给出极端图类的结构性质的刻画； ( 4 ) 讨论各种控制划分参数的复杂性问题，算法及应用问题 本文的主要工作是研究了符号控制划分数和符号全控制划分数，其相应的结 果为以下两部分： 第一，首先提出了符号全控制划分数的概念；接着得到了符号全控制划分数 的一些基本性质；最后给出了一些特殊图上的符号全控制划分数的值或上界 第二，建立了图的符号控制划分数与其补图的符号控制划分数两者的和的上 界，并且对达到上界的极图进行了刻画，同时得到了这两个参数的积的下可达界 和上界；然后给出了图的符号全控制划分数与其补图的符号全控制划分数两者的 和的可达上界，同时得到了这两个参数的积的下可达界和上界；最后研究了图的 符号( 全) 控制数与其符号( 全) 控制划分数的和的上界，并且对达到上界的极图进 行了刻画 2 0 0 7 年上海大学硕士学位论文 4 第二章基本符号和结论 2 1 基本概念和记号 本文所讨论的图均是无向、无环且无多重边的有限简单图凡是文中未加定 义的术语和符号，可参看文献| 1 ，1 4 1 为了叙述方便，我们首先引入一些定义和记 号设g = e ) 是简单图，y ( g ) ，e ( g ) 分别表示图g 的顶点集和边集，g 的 顶点的数日n = i y ( g ) f 称为图g 的阶数如果图日满足条件v ( h ) v ( v ) 和 e ( h ) e ( g ) ，则称日为图g 的一个子图对s y ( g ) ，用g 翻表示由s 导 出的子图 图g 中点z 的开邻域定义为n ( x ，g ) = ix y e ( g ) ) ，x 的闭邻域为 n x ，g = n ( x ，g ) u z ) 更一般地，对任意的x 量y ( g ) ，我们定义n ( x ，g ) = u 。x n ( x ，g ) ，n x ，q = n ( x ，g ) ux 在不引起混淆的情况下，上述符号可分别 简记为忙) ，n i x ，u ( x ) 和】我们称d ( x ) = i ( z ) f 为点x 的度数，度数 为1 和0 的点分别被称为图的悬挂点和孤立点分别用6 ( g ) 和( g ) 表示图 g 的最小度和最大度所有顶点的度都等于k 的图g 称为“正则图 由n 个顶点构成的路和圈一般记作r 和g 如果对g 中任意两个顶点u 和 v ，在g 中都可以找到连接这两个点的路，则称图g 是连通的，对于子图的连通性 可类似定义连通的无圈图称为树由条路和一个与这条路上每个顶点都邻接的 新的顶点共同构成的图称为扇图，由一个圈和一个与这个圈上每个顶点都邻接的 新的顶点共同构成的图称为轮图，记作i 若图g 中的任意两个相异点之间都有 边相连，则称g 为完全图，n 个顶点的完全图记作用g = ( u ，y k ；e ) 表示顶点集是u 坠1 m ，边集是 z g e ( g ) lz k ，y y j ，1 i j ) 的舡部 图特别地，当k = 2 时，g 称为二部图或偶图，若i k | = m ，1 i = n ，且 的每个顶点都与k 的每个顶点相连，则称此二部图为完全二部图或完全偶图， 记作，特别地，如果i l = m = 1 ，称其为星图，记作匝， n 阶图g 的补图记为0 = ( v 啻) ，定义如下：y ( 0 ) = y ( g ) ，e ( g ) u e ( g ) 一 e ( k ；) 且e ( g ) n e ( g ) = 0 两个图g = ( y ( g ) ，e ( g ) ) ，h = ( y ( 日) ，e ( 凹) ) 的积 图g 日的定义如下：g h = y ( g ) y ( 日) ，e ) ，其中e = “( 1 ， 1 ) ，( u 2 ，吨) ) 1 2 0 0 7 年上海大学硕士学位论文 5 u 1 = “2 v ( g ) 且v l v 2 e ( 日) ；或者口1 = 0 2 v ( h ) 且u l 地e ( g ) ) 特别地， 如果g = p n 。和h = r ：都是路，它们的积图被称为网图，记作瓯。；r ，r ： 两个图g ，日的联图g + h 的定义如下：g + h = ( v ( a ) u y ( 日) ，e ) ，其中 e = e ( g ) u e ( h ) u ( ， ) iu y ( g ) ，口y ( 日) ) 下面我们给出与本文相关的一些控制参数的概念 设s y ( g ) ，s 称为g 的控制集，如果对每一个点口v ，或者口在 s 中，或者口至少邻接于s 中的一个点，也即【司= y ( g ) 图g 的控制 数7 ( g ) 定义为g 的最小控制集的点数，也即1 ( g ) = r a i n i s l ls 是g 的控 制集) 如果集合a 的i 个子集a 1 ，a 满足：a = ：l 山且4 矾其 中j = 1 ，2 ，i ，则称集合a = a 1 j ，a ) 为集合a 的一个划分1 9 7 7 年 c o c k a y n e 和h e d e t n i e i i l i 酬首先引入了控制划分数的概念给出图g 的的点集 v ( a ) 的一个划分 ( g ) ，k ( g ) ，k ( g ) ) ，如果k ( g ) 是图g 的控制集，其中 j = l ，2 ，i ，则称这个划分是图g 的一个控制划分图g 的控制划分数d ( g ) 定义为t d ( g ) = m a x l i l | m ( g ) ，k ( g ) ，k ( g ) ) 是图g 的一个控制划分 下面我们以一个具体的图为例， ob dc 图2 1 1 在图2 1 1 中，集合 o ) ， c ， 6 ，田) 是该图的一个控制划分，同样，集合 n ，吣， c ，以 也是该图的一个控制划分，又注意到，集合 o ) ， 6 ) ， c ， d ) ) 不 是这个图的控制划分，由控制划分数的定义，图2 1 1 的控制划分数为3 在图g 不含孤立点的前提条件下，1 9 8 0 年c o c k a y n e 4 1 等人首先引入了全控 制的概念设s y ( g ) ，s 称为g 的全控制集，如果对每一个点v v ，v 至少 2 0 0 7 年上海大学硕士学位论文 6 邻接于s 中的一个点，也即n ( s ) = y ( g ) 图g 的全控制数7 t ( g ) 定义为g 的 最小全控制集的点数，也即m ( g ) = r a i n i s ls 是g 的全控制集) 在该篇文章 中，他们同时给出了全控制划分数的定义给出图g 的的点集v ( g ) 的一个划分 ( g ) ，k ( g ) ，k ( g ) ) ，如果巧( g ) 是图g 的全控制集，其中j = 1 ，2 i 则 称这个划分是图g 的一个全控制划分图g 的全控制划分数d t ( g ) 的定义为t 也( g ) = m a x l i ii k ( g ) ，k ( g ) ，k ( g ) 是图g 的一个全控制划分 在图g 连通的前提条件下，s a m p a t h k u m a r 和w a l i k a r z 6 】在1 9 7 9 年给出了 连通控制集的定义设s y ( g ) ，s 称为g 的连通控制集，如果s 是g 的控 制集且g s 1 是连通的h e d e t n i e m i 和l a s k a r 川】则提出了连通控制划分数的概 念；给出图g 的的点集v ( a ) 的一个划分 ( g ) ，k ( g ) ，k ( g ) ) ，如果k ( g ) 是图g 的连通控制集，其中j = 1 ，2 ，i ，则称这个划分是图g 的一个连通控 制划分图g 的连通控制划分数d c ( g ) 的定义为z d c ( g ) = m a x l i ii ( g ) ，k ( g ) ，k ( g ) ) 是图g 的一个连通控制划分) 设，是定义在点集v 上的实值函数，w ( f ) = 。，f ( v ) 称为，的权对任 意子集s y ，我们定义l ( s ) = 。s ，( 口) ，因此w ( f ) = ，( y ) 下面我们从函数 的角度来分析图g 的控制数和控制划分数设，：v ( c ) 一 o ，1 ) 是定义在y 上 的函数，我们称，是g 的控制函数，如果对每一个点口v 有，( m ) 1 图 g 的控制数7 ( g ) 定义为： 7 ( g ) = m i n w ( f ) i ，是g 的控制函数) r a l l 2 6 1 从控制函数的角度给出了控制划分数的函数定义，设 ，2 ，丘) 为图 g 的一族控制函数构成的集合，并且满足对任意z v 有垒l ( z ) = 1 ，那么符 合该种条件的控制函数的集合的最大基数就是图g 的控制划分数d ( g ) ，即 d d ( g ) = m a x di 五( z ) = 1 ，其中 ，2 ，矗都是图g 的控制函数) i = 1 如果将上述定义中的闭邻域n v 】换成开邻域( 口) ，就可以得到图g 的全控制数 和全控制划分数的函数角度的定义 2 0 0 7 年上海大学硕士学位论文 7 对于控制函数和全控制函数而言，它的值域都是 o ，1 ) 随着控制函数参数 的不断发展，人们不断尝试改变值域去开拓新的研究领域h e d e t n i e m i 1 6 等在 1 9 8 7 年正式引入了分数控制函数的概念设，：v ( a ) 一【0 1 】是定义在y 上的函 数，我们称，是g 的分数控制函数，如果对每一个点v v 有，( m ) 1 图 g 的分数控制数w ( g ) 定义为； 竹( g ) = m 伽扣( ，) i 促g 的分数控制函数 r a l l ( 2 6 1 在对控制划分数进行函数角度的分析之后，引入了分数控制划分数的概 念设 ，2 ，d ) 为图g 的的一族分数控制函数，如果对任意z v 满足； 冬1 ( z ) 1 ，那么符合该种条件的分数控制函数的集合的最大基数就是图g 的 分数控制划分数d s ( g ) ，即 d d y ( g ) = m a x dl 五( z ) sl ，其中 ，2 ，厶都是图g 的分数控制函数) i = l d u n b a r l 7 等在将控制函数定义中的值域 o ，1 ) 换成了 1 ，一1 ) 以后，提出了 符号控制函数的概念设f ：v ( a ) 一 l ，- 1 是定义在y 上的函数，我们称，是 g 的符号控制函数，如果对每- - 4 点口v 有f ( n i v ) 1 图g 的符号控制 数( g ) 定义为： - y , ( g ) = m 讥 t ，( 门i ，是g 的符号控制函数) z e l i n k a 4 3 1 把上述定义中的闭邻域n w l 换成开邻域g ( v ) 后，引入了图g 的符 号全控制函数和图g 的符号全控制数的概念 v o l k m a n n ；j 0 1 等在2 0 0 5 年仿照分数控制划分数的定义提出了符号控制划分 数的概念设 ，2 ，d ) 为图g 的的一族符号控制函数，如果对任意z v 满足：垒，五( z ) 1 ，则称这一族符号控制函数为图g 的一个符号控制族图 g 的符号控制划分数以( g ) 定义为： 也( g ) = m a x df ，五，d ) 是图g 的一个符号控制族) 2 0 0 7 年上海大学硕士学位论文8 2 2 图的控制划分参数的现有主要结果 近些年来对上述各种控制参数的研究主要集中在界、判定问题的复杂性、算 法、各种参数之问的关系以及极图的刻画等方面下面我们给出相关的主要研究 结果 关于控制划分数方面的研究主要有以下结果； 定理2 2 1 ( 5 1 ) 若g 是阶n 、最小度为6 ( g ) 的图，则d ( g ) j ( g ) + 1 定理2 2 2 ( 【1 4 】) 设阶n 的图g 的控制划分数，控制数分别为a ( g ) 、7 ( g ) ，则 d ( c ) n n ( g ) 定理2 2 3 ( 【4 1 】) 若g 是阶n 、最小度为d ( g ) 的图，则d ( c ) 【i 焉丽j 定理2 2 4 ( 【5 ) 对于图g 的控制划分数d ( g ) ，有如下性质成立t ( 1 ) d ( 风+ g ) = n + d ( g ) ，其中玩为n 阶完全图 ( 2 ) d ( 风) = n ；d ( j 乙) = 1 ，其中为n 阶完全图 ( 3 ) 徊俐d ( g ) 2 当且仅当图g 不合孤立点 ( 4 ) 如果图g 是阶 2 的树，则d ( c ) = 2 ( 5 1 对于阶竹3 的圈c ；有下式成立， f3 d ( g ) = 【2 n 能整除3 ； n 不能整除3 ( 6 ) d ( ，。) = m ，其中，。为满足2 m n 的完全二部图， 定理2 2 5 ( 【3 】) 对满足n 12 他22 的网图g 。= r ，x p 。，如果( k ，。g 2 ，2 且g 。g 4 ，2 ，那么d ( g 。) = 3 定理2 2 6 ( 【5 】) 若g 为阶订的图，则d ( g ) + d ( g ) 墨n + 1 定理2 2 7 ( 【5 】) 若g 为阶n 的图，则d ( g ) + d ( g ) = 扎+ 1 当且仅当g = 或 g z 赢 定理2 2 8 ( 【3 8 】) 若g = ( p ，q ；e ) 是阶n ，最小度为j ( g ) 1 的二部图，设 p = i p i ，q = l q l ，p q 2 ，则d ( g ) = d ( 0 ) 当且仅当下列条件同时成立； ( 1 ) 在图g 中，对每一个点口p ，有d ( 口) q 一1 成立； ( 2 ) p 中度数等于q 的点的数目大于等于q 中度数等于p 的点的数日； ( 3 ) q 中至少有一个点的度数等于p 或p 2 q 一1 定理2 2 9 ( 【3 8 】) 若g 为阶n 的二部图，如果d ( c ) = d ( 0 ) ，那么7 ( g ) = 7 ( g ) 2 0 0 7 年上海大学硕士学位论文9 定理2 2 1 0 ( 【6 】) 若t 为阶n 2 的树，则3sd c t ) + d ( 于) 【j + 2 i2 d ( t ) d ( t ) n ，且这两个下界等号成立当且仅当t 垒甄一1 i 这两个上界等号成立 当且仅当d ( t ) = 【n 1 2 j ，对于积的上界，n 必须为偶数 定理2 2 i i ( 【6 】) 若t 是阶n 2 的树，则d ( 亍) = h 2 j 当且仅当ac t ) s m 2 定理2 2 1 2 ( 【5 】) 若g 为阶 的图，则d ( a ) + 7 ( g ) n + 1 ，且等号成立当且仅 当g = 壕或g = 赢 定理2 2 1 3 ( 【1 2 】) 若g 和g 均为阶n ，不合孤立点的的囤，则d ( g ) + 7 ( a ) 【詈j + 2 定理2 2 1 4 ( 【3 1 】) 若g 和0 均为阶n 、不合孤立点的的图，则d ( a ) + 7 ( a ) = l 利+ 2 当且仅当下列条件之一成立， ( 1 ) - y ( a ) ，d ( g ) ) = 引，2 ) i ( 2 ) n = 9 且7 ( g ) = d ( a ) = 3 定理2 2 1 5 ( 【6 】) 若g 为阶n 4 的图，则2 d ( g ) d ( 0 ) n 2 4 ，且此上、下界 是可达的 关于全控制划分数方面的研究主要有以下结果( 该部分定理默认图不含孤立 点) ： 定理2 2 1 6 ( 【4 】) 若g 是阶n 、最小度为j ( g ) 1 的图，则画( g ) j ( g ) 定理2 2 1 7 ( 【1 5 】) 设图g 的控制划分数、全控制划分数分别为d ( g ) 、也( g ) ， 则l d ( g ) 2 j 也( g ) d ( g ) 定理2 2 1 8 ( 【4 】) 设n 阶图g 的全控制划分数、全控制数分别为d t ( g ) ，m ( g ) ， 则也( g ) n m ( g ) 定理2 2 1 9 ( 【4 4 】) 若g 是阶n 、最小度为j ( g ) 1 的图，则d ( g ) 2 【再i 啬丽j 定理2 2 2 0 ( 【4 】) 对于图g 的全控制划分数也( g ) ，有如下性质成立。 ( 1 ) d r ( 风) = l j ，其中为n 阶完全图 ( 2 ) d t ( c “) = 2 ，其中a 。为长度为4 n 的圈 ( 3 ) 西( ，。) = m i n m ，n ) ，其中，。为完全二部图 定理2 2 2 1 ( 【1 5 】) 若图g = w n 为阶n 的轮图，则也( i ) = 2 定理2 2 2 2 ( 【4 】) ( 1 ) 若g 是阶n 的图，则d t ( g ) + 7 t ( a ) n + 1 ，且等号成立当 且仅当g = m j 已， 2 0 0 7 年上海大学硕士学位论文 1 0 ( 2 ) 若g 是阶n 3 的连通图，则画( g ) + m ( g ) n ，且等号成立当且仅当 g = k 12 ，蚝，c 4 ，k 4 或尬去掉任意一条边 定理2 2 2 3 ( 3 1 1 ) 若g 是阶n 、全控制划分数d t ( g ) 22 的图，则d t ( a ) + t t ( g ) 【j + 2 ，在n 9 时，等号成立当且仅当 m ( g ) ，也( g ) ) = 2 ，【2 j ) 定理2 2 2 4 ( 1 4 1 ) 若g 是阶n 、最大度为a ( g ) = 1 或一1 ，所以d 五( z ) 0 ，进一 步，我们有； d ( 。) = ( z ) 0 这与性质3 1 3 矛盾性质证毕 下面的推论可由性质3 1 2 ，3 1 3 及3 1 4 和引理3 1 1 和3 1 2 直接推出 推论3 1 1 若g 是阶n ，最小度为6 ( g ) = 1 或2 的图，则啦( g ) = 1 ，特别地， 哦( c k ) = 成( r ) = 窿( k 1 ，。1 ) = 喀( 丁) = 1 引理3 1 1 ( 4 3 】) 若g 是阶n 的一正则图，则 臂c g ， 辜2 n ，：竺：萋： 且此界是可达的 推论3 1 2 若g 是阶n 的k - 正则图，则 且此界是可达的 磁( g ) kk 为奇数； k = 2 1 且l 为奇数； 1 - 1 k = 2 1 且l 为偶数 g h 一 p 。” 州 z | i 扛 u 洲 。：l 一 d 2 0 0 7 年上海大学硕士学位论文 1 5 下面我们来看些使得推论3 1 2 中等号成立的图对任意的1 正则图，2 j e 则图日， 由推论3 ，1 ，2 ，可得霹( 日) = 1 ；对任意的阶n 的4 - 正则图g _ ，由引理3 1 1 ，很容易 得到；w ( g 4 ) n 2 ，那么再由性质3 1 2 、3 1 3 和3 1 4 ，可得磁( g 4 ) = 1 = 一1 引理3 1 2 ( 1 4 3 】) 若g = ，。是完全二部图，则 ， l2 ，仇，”均为奇数； w ( k i n ，n ) = 3 ，m ，”一奇一偶； l4 ，7 7 ，n 均为偶数 推论3 1 3 若g = 。是完全二部图，则 ( 。) m i n m ，n ，m ，n 均为奇数； 字， m ，n 一奇一偶； m 4 + n ， m ，n 均为偶数 且此界是可达的 下面我们来看一些使得推论3 1 3 中等号成立的图我们很容易验证；喀( ，。) = 1 ( = m i n 1 ，n ”；成( k 1 ，2 ) = 1 ( = ( 1 + 2 ) 3 ) ；d ；( ( 2 ，2 ) = 1 ( = ( 2 + 2 ) 4 ) 3 2 完全图和轮图的符号全控制划分数 人们发现图上的很多数字变量在完全图上的值都是不变的，然而，在本节中 我们将说明完全图的符号全控制划分数不属于此类情况 引理3 2 1 ( 【4 3 】) 若g = j 厶是阶n 的完全图，则 w ( g ) ： 3 ，”为奇数； i2 ，n 为偶数 定理3 2 1 若g = 是阶的完全图，则 i 磁( g ) = p ， n = 2 p 且p 为奇数； 啦( g ) = p 一1 ，n = 2 p 且p 为偶数； l 喀( g ) n 3 ， n 为奇数 且此界是可达的 2 0 0 7 年上海大学硕士学位论文 1 6 证明：设n 阶完全图g 的点集为 1 ，2 ，n ) ，喀( g ) = d 下面我们根据n 的奇 偶性分两种情况给出证明 情况1 设 = 2 p 为偶数我们先说明d p ：由引理3 2 1 ，我们有臂( g ) = 2 ， 再由性质3 1 2 ，可得，2 d n = 2 p ，即d p 接下来，我们根据p 的奇偶性再分 两种小情况来证明 情况1 1 设p = 2 q + 1 为奇数，我们定义如下这样一族符号全控制函数 ，2 ，厶 ： y 1 ( 1 ) = ( 2 ) = ( 3 ) _ ，2 ( 3 ) = ，2 ( 4 ) = ，2 ( 5 ) = ( 5 ) = ( 6 ) = ，3 ( 7 ) 一 = ( p ) = 0 ，+ 1 ) = 1 = ，2 + 2 ) = ，2 p + 3 ) = 1 = 矗+ 4 ) = ，3 ( p + 5 ) = 1 厶( 印一1 ) = 厶( 2 p ) = ，p ( 2 p + 1 ) 一一矗( 劬一2 ) = 厶( 3 p 一1 ) = 1 对于其他的情况，我们都定义：， ( j ) = 一1 ，这里所有的数都是取的模n 后的 值我们很容易验证：对任何点口v ( a ) 均有。五( ) 1 成立，其中 i = 1 ，2 ，p ；对任何点。v ( a ) 均有警1 ( z ) = 1 所以， ，1 ，2 ，矗) 是 图g 的一个符号金控制族，由图的符号全控制划分数的定义有僻( g ) p 另一方 面，我们已经在前面说明d p 故磁( g ) = p 情况1 2 设p = 2 q 为偶数，我们定义如下这样一族符号全控制函数 ，1 ，2 ，p 一1 ) f 1 ( 1 ) = ( 2 ) = = f l ( 2 q ) = ( 2 q + 1 ) = 1 ，2 ( 4 ) = ，2 ( 5 ) = = ，2 ( 2 q + 3 ) = ，2 ( 2 q + 4 ) = 1 ，3 ( 6 ) = ，3 ( 7 ) = = ，3 ( 2 q + 5 ) = ，3 ( 2 q + 6 ) = 1 ，4 ( 8 ) = ，4 ( 9 ) = = ，4 ( 2 q + 7 ) = ，4 ( 2 q + 8 ) = 1 l ( 2 q ) = ，口( 2 9 + 1 ) = = l ( 4 q 一1 ) = l ( 4 q ) = 1 矗+ 1 ( 2 q + 3 ) = l + l ( 2 q