（应用数学专业论文）图的函数控制数.pdf

图的函数控制数 摘要 图的控制理论是图论中的一个重要分支，在编码理论，计算机科学，通信网 络，社会网络等学科中都有广泛的应用。随着计算机科学兴起及函数方法的加入， 使得图的控制理论成为图论近几十年发展最快的领域之一1 9 9 8 年美国图论学 者h a y n e s 等人出版了两部专著【l 】【2 】，较为系统地综述了几千篇关于函数控制数 的研究成果 本文所做工作主要包括以下二个部分：( 1 ) 确定几类函数控制数的界( 2 ) 某 些特殊图的函数控制参数值的确定 在第一章，我们给出了本论文要用的相关概念及图的函数控制数的研究概 况 在第二章，我们得到了图的反符号圈控制数的上界，并且给出了几种特殊 图的反符号圈控制数，主要得到了下面几个结果： 对任意的图g 都有心c ( g ) 2 i v ( g ) l i e ( g ) i 一2 且等式成立当且仅当 g 是树 坼。( ) = 2 嘲一( 笏 z 。( + 1 ) = - 2 f 薏 坼。c ( 五，n ，m ) = m 札一m m ( m 一1 ) n ，m ( 礼一1 ) ) 在第三章，给出了图的分数划分数的界： 对任意一个n 阶图g ，均有t a g ) d i ( g ) 亿 对任意一个最小度为6 的图g ，均有6 d r ( g ) 6 + 1 在第四章，通过反证法及构造全符号函数的方法给出了完全图的全符号控 t -r-ri-ir 制数的精确值：憾( ) = i i t , 在第五章，给出图的全减符号控制数的上界应用图的距离为2 的减符号 控制数与其细分图的全减符号控制数相等的性质给了路的全减符号控制数的精 确值并且给出圈的全减符号控制数的精确值 关键词：图；圈；控制数；控制函数；划分数 i i 111 i l l i f u n c t i o nd o m l n a t l o nn u m b e ri ng r a p h s a b s t r a c t d o m i n a t i o nt h e o r yi sa ni m p o r t a n tb r a n c ho ft h e g r a p ht h e o r y , i th a saw i d er a n g e o fa p p l i c a t i o n si nc o d i n gt h e o r y , c o m p u t e rs c i e n c e ，n e t w o r k s ，s o c i e t ys t u d ya n ds oo n 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 rs c i e n c ea n dt h ef u n c t i o nm e t h o du s e d ，m a k e s t h ed o m i n a t i o nt h e o r yb e c o m eo n eo ft h ef a s t e s tg r o w i n ga r e a si nr e c e n td e c a d e so f g r a p ht h e o r y t h o u s a n d sl i t e r a t u r eo nt h et o p i ch a sb e e ns u r v e y e da n dd e t a i l e di nt h e t w ob o o k sb yh a y n e s ，e ta l 1 】【2 】i n1 9 9 8 i nt h i sp a p e r , w e p a y o u ra t t e n t i o nm a i n l yo nt h e f o l l o w i n g t w o p a r t s o fd o m i n a t i o n i ng r a p h s ：( 1 ) d e t e r m i n i n gt h eb o u n d so nd o m i n a t i n gf u n c t i o n si ng r a p h s ( 2 ) c o m p u t e t h ee x a c tv a l u e so fd o m i n a t i n gf u n c t i o n sn u m b e rf o rs o m ec o m m o n g r a p h sd o m i n a t i n g f u n c t i o n s i nc h a p t e r1 ，w eg i v es o m et e r m i n o l o g ya n dn o t a t i o n s ，a n ds o m er e c e n tr e s u l t s c o n c e r n i n gd o m i n a t i n gf u n c t i o n i nc h a p t e r2 ，w ei n v e s t i g a t et h eb o u n d so nr e v e r s es i g n e dc y c l ed o m i n a t i o na n d d e t e r m i n es o m ec o m m o ng r a p h so fr e v e r s es i g n e dc y c l ed o m i n a t i o n m a i n l yb yt h e f o l l o w i n ga s p e c t s ： i tw a so b t a i n e dt h eu p p e rb o u n d o f 彤。c ( g ) f o rg e n e r a lg r a p h sg w h i l e iy ( g ) i = i e ( g ) i = m 吒。( ) = 2 【】一( 笏 亿c ( 眠+ 1 ) = 2 嘲 坼。( 玩，m ) = 仇n m i n ( m 1 ) n ，m ( n 一1 ) ) i nc h a p t e r3 ，w eg a v eb o u n d so ft h ef r a c t i o n a ld o m a t i cn u m b e ra sf o l l o w i n g ： t t t f o re v e r yg r a p ho fo r d e r 竹，w eh a v e 竹( g ) d s ( g ) 礼 i fgi sa g r a p hw i t hm i n i m u md e g r e e6 ，t h e n5 d s ( g ) 5 + 1 i nc h a p t e r4 ，w eg a v e7 ：( g ) = 嘲b yr e d u c t i oa da b s u r d u m i nc h a p t e r5 ，w eo b t a i n e dl o w e rb o u n df o rt h et o t a lm i n u sd o m i n a t i o nn u m b e ro f ag r a p hga n dt h ee x a c tv a l u e so f 嚅( g ) w h e ngi sp a t ha n d c y c l e k e yw o r d s ： g r a p h s ；c y c l e s ；d o m i n a t i o nn u m b e r ；d o m i n a t i o nf u n c t i o n ；d o - m a r i en u m b e r i v 1 一 - k 目录 摘要i a b s t r a c t m 目录v i l 绪论1 1 1 基本概念1 1 2 图的函数控制数的概念 2 1 3 图的函数控制数的研究概况3 2 图的反符号圈控制数 6 2 1 图的反符号圈控制数的上界 6 2 2 特殊图的反符号圈控制数7 3 图的分数划分数l l 3 1 图的分数划分数的界1 1 3 2 特殊图的分数划分数1 2 4 图的全符号控制数1 8 4 1 完全图的全符号控制数1 8 5 图的全减符号控制数2 4 5 1 图的全减符号控制数的下界2 4 5 2 路、圈的全减符号控制数2 5 参考文献3 2 攻读学位期间取得的研究成果3 4 致谢3 5 浙江师范大学学位论文独创性声明3 6 学位论文使用授权声明3 6 v 浙江师范大学学位论文诚信承诺书3 7 v i 1 1 基本概念 1 绪论 在本节中，我 t 6 1 入一些本学位论文中要用到的图论的基本术语与符号 一个有序对g = ( ke ) 称为一个无向图，其中y 是一个有限集合，e 是y 中的不同元素的无序对的集合y 中的元素叫做图g 的顶点，e 中的元素叫做图 g 的边通常用y ( g ) ，e ( g ) 分别表示图g 的顶点集合与边集合没有重边和环 的图叫做简单图本文研究的图均指有限简单无向图 常用u ，u 表示g 中的点，e 表示g 中的边若边e = 删e ( g ) ，则说t ，秽在 g 中相邻，这时又说让和u 是e 的两个端点，也说，u 与e 相关联设口y ( g ) ， 在图g 中与u 相邻的点的全体构成的集合称做u 的开邻域，记作n o ( v ) ，简记为 n c v ) 叫m = n ( v ) u 钉) 为点口的闭邻域称i g ( 口) i 为点t ，在图g 中的度 数，记作d a ( v ) ，简记为d ( 口) g 中的点的最小度和最大度分别记作6 ( g ) 和( g ) ， 简记为6 和 图g 中的一个点边交替序列叫= v i e l v 2 e 2 e k - l v k 叫做一条途径，其中 e = u i 仇+ 1 e ，1 isk 一1 若u 1 = 仇，则称叫为一条闭途径又若途 径w 上的顶点访，v 2 ，互不相同，则称w 为一条( 口1 一v k ) 路，记作r 称 u l ，分别为路最的起点和终点起点和终点相同的路称为圈如果g 中存在 m 一口) 一路，则从u 到钉的距离记为d g ( u ，钉) 或简记为d ( u ，t ，) 是m 一口) 一路的最 短长度如果g 中不存在一 ) 路，则d ( u ，u ) = o o 设u y ( g ) ，我们分别把 乞( 口) = u ：d ( u ，t ，) 2 ，乱y ( g ) ) ，n 2 7 3 】= 缸：d ( u ，t ，) 2 ，u y ( g ) u 1 【 ) 称 为口的距离不大于2 的开邻域及闭邻域 对于图g = ( ve ) 和图h = ( v 7 ，e ) ，若有y 7 v e ，则称图h 是图 g 的子图我们用a v 7 】表示g 中由生成的子图，若对圈c 有g ( c ) 】= c ， 则称c 为g 的生成圈 文中其它未定义的术语和符号请参阅文献【3 】 1 绪论 1 2 图的函数控制数的概念 图的控制集理论是应用数学的一个重要分支，在编码理论，计算机科学，通信 网络，监视系统和社会网络等学科中都有广泛的应用图的函数控制集是图的控 制集概念的自然推广，而且由于函数的加入，使利用分析性质进行处理图的控制 集成为可能设g = ( ke ) 为一个图，f ：v _ 冗为一个实值函数，s y ，为了 方便，记f ( s ) = y e s ，( t ，) ，并且，m = u m ，( u ) d u n b a r 等人在文献 4 】和【5 】中分别引入图的符号控制数和减控制数的概 念函数f ：v 一 一1 ，1 ) 如果满足对任意的口y ( g ) ，均有f v 】1 成立，则称 ，为图g 的一个符号控制函数图g 的符号控制数定义为：( g ) = m i n f ( v ) ： ，是g 的符号控制函数】- 函数f ：v 一 - - 1 ，0 ，1 ) 如果满足对任意的u y ( g ) ， 均有s 7 3 】1 成立，则称，为图g 的一个减控制函数图g 的减控制数定义为： ，y _ ( g ) = m i n f ( v ) ：f 是g 的减控制函数) d o r n k e 等人在文献【6 】6 中引入了图的分数控制数的概念，函数f ：v _ 【o ，1 】 如果满足对任意的 y ( g ) ，均有，m 1 成立，则称，为图g 的一个分数控制 函数图g 的分数控制数定义为：r s ( c ) = m i n f ( v ) ：f 是g 的分数控制函数) 1 9 9 0 年，r a i l 在文献【7 】中引入了图的分数划分数的概念，若集合d = ，厶，d ) 满足d 中的元素都是g 的分数控制函数，且对任意的点u v ( a ) 都有五( 口) 1 则称集合d 为图g 的分数控制簇把略( g ) = m a x l d l ： d 是g 的分数控制簇 叫做图g 的分数划分数 2 0 0 5 年，v o l k m a n n 等人在文献【8 】中引入了图的符号划分数，若集合d = ，厶，丘) 满足d 中的元素都是g 的符号控制函数，且对任意的点秒 v ( c ) 都有五( t ，) 1 则称集合d 为图g 的符号控制簇把以( g ) = m a x l d i ： d 是g 的符号控制簇 叫做图g 的符号划分数 2 0 1 0 年，a t a p o u r 等人在文献【9 】9 中引入了图的符号星划分数，若集合 d = ，厶，丘) 满足d 中的元素都是g 的符号星控制函数，且对任意 的边e e ( g ) 都有五( e ) 1 则称集合d 为图g 的符号星控制簇把 缸( g ) = m a x i d l ：d 是g 的符号星控制簇) 叫做图g 的符号星划分数 在文献【1 0 】中给出了图的全符号控制数，函数f ：vue _ 一1 ，1 ) 如果满 足对任意元素z v ( a ) ue ( g ) ，均有t m ，( 可) 1 成立，则称，为图g 的 2 _ - 1 绪论 一个全符号控制函数其中坼m = 秒：y 与z 相邻或y 与z 关联，y v ( c ) u e ( g ) ) u z ) 图g 的全符号控制数定义为：霄( g ) = i n j n z y ( g ) u e ( g ) f ( x ) ：f 是g 的全符号控制函数) 徐保根在文献【i i 】中引入了图的符号圈控制数，函数f ：e 一 - 1 ，1 1 如果 满足对图g 中的任意生成圈g 都有。e ( ( e ) 1 成立，则称，为图g 的一 个符号圈控制函数图g 的符号圈控制数定义为：能c ( g ) = m i l l 。e ( g ) f ( e ) ：f 是g 的符号圈控制函数 2 0 0 8 年，徐保根在图的控制理论中介绍了图的反符号圈控制数，函数 ，：曰一 - 1 ，1 ) 如果满足对图g 中的任意生成圈c 都有。e ( g ) f ( e ) 0 成 立，则称，为图g 的一个反符号圈控制函数图g 的反符号圈控制数定义为： 坼卵( g ) = m a x 0 ，矛 盾即吒。( g ) 2 n m 一2 下证吒。( g ) = 2 n r r $ 一2 时，g 是一棵树 充分性：充分性是显然的 必要性： 由彤。( g ) = 2 n m 一2 可知口= j ( 吒。( g ) + m ) = 礼一l ，设g 1 是g 的生成子图，定义同上假设g 1 中含有圈，由上面同样的证明可得到一个矛 盾，故g l 中不含有圈因i e ( g 1 ) l = a = 礼一1 ，故g l 是一棵树 下证g = g 1 假设g g t ，则m = e ( g ) e ( g 1 ) 0 ，令e = 伽m 使得 在所有的m 中d = d c ，( 让，移) 最小则c d + 1 = g l + 伽是g 中的一个生成圈且 ，( c d 十1 ) = d + y ( u v ) l ，矛盾故g = g 1 ，即g 是一棵树证毕 2 2 特殊图的反符号圈控制数 定理2 2 对任意的礼1 都有嘭。( 玩) = 2 吲一( ；) i i e 明：先证吒c ( ) 2 吲一( 三) 令，是g 的反符号圈控制函数，因对任意的e e ( ) 都存在一个三 角形蚝使得e e ( k 3 ) ，又由性质2 2 可知，( 蚝) 冬一1 ，故对任意两条满 足，( e ) = 1 的边都不相邻因此，中最多存在【鸶】条边满足，( e ) = 1 ，故 亿c ( ) 2 吲一( 笏 下证z 。c ( ) 2 嘲一( 笏 记y ( 玩) = v l ，v 2 ，) ，e i d = 忱( i ，j 1 ，2 ，n 1 ) ，i 歹) 定义 7 2 图的反符号圈控制数 f ：e 一 一1 ，1 如下： ，c e 幻，= 二1 ，j 其= 它i + 1 i = 1 3 一 2 瞪】一1 ， 易知f 是的一个反符号圈控制函数且，( e ( ) ) = 2 嘲一( n ) ，故嘭。c ( 玩) 2 吲一( 三) 综上即得坼。( ) = 2 嘲一( ；) 定理2 3 对任意的n 3 都有嘭。( 眠+ 1 ) = - 2 r 7 1 证明：先证嘭。c ( + 1 ) - 2 r 7 1 令，是+ 1 的最大反符号圈控制函数，记y ( 帆+ 1 ) ，= 咖， 0 1 ，) ，其中 伽是轮图巩+ 1 的中一f i , ，t ，1 ，v 2 ，构成圈c k ，则2 亿。( 矾+ i ) = ，( 恐) + ，( g ) 由图+ 1 的构造可知，帆+ l 中有n 个恐且l e ( 眠+ 1 ) i = 2 n 下面对n 进行分类： ( 1 ) 礼为偶数 由性质2 1 及反符号圈控制函数的概念可知，( k 3 ) i i ，( g ) 0 ，则 “。( 眠+ 1 ) = f ( k 3 ) + f ( c n ) 一n + o ， k 3 e w n + i 即嘭。c ( 巩+ ) 一f 鸶 ( i )当佗= 4 k 时，嘭。( w 名+ 1 ) 一鸶 = 一2 k = 一2 r 7 1 ( i i ) 当佗= 4 k + 2 时，嘭。c ( 取+ 1 ) 一詈1 = - 2 k 一1 1 t i 性s ：, j i2 1 可知 嘭。( + 1 ) - 2 k - 2 - - - 2 r 4 1 ( 2 ) 礼为奇数 i t l f 生j l2 1 及反符号圈控制函数的概念可知，( 甄) 一1 ，( g ) - 1 ，则 2 嘭。( 眠+ - ) = ，) + ，( g ) 一死一1 ， k 3 e w k + 1 8 i2 图的反符号圈控制数 即彤。( + 1 ) 一下n + 1 ( i ) 当扎= 4 七十1 时，嘭。c ( 矾+ 1 ) 一学1 = - ( 2 k + 1 ) ，由性质2 1 可知 嘭；。( + 1 ) - 2 ( k + 1 ) = 一2 署1 ( i i )当n = 4 忌+ 3 时，嘭。( w 名+ 1 ) - r l n + 广1 = 一2 七一2 = 一2 f 等1 综上所述，对任意的几3 都有嘭。( + 1 ) 一2 鼍1 下证嘭。c ( + 1 ) 一2 署1 记y ( 巩+ 1 ) = v o ，口1 ，) ，其中如是轮图的中心令e i = u i v i + l ，e n = v 1 u n ，e n 钾= 蜘其中i = 1 ，2 ，n 一1 ，j = 1 ，礼定义i ：e _ 一1 ，1 ) 如下： 当n = 4 k 时， f 1 ， 1 一 i 0 ，矛盾故嘭。c ( ，m ) m n 一2 m i n ( m 1 ) 佗，m ( n 1 ) ) 综上即得亿。( ，m ) = m n 一2 m i n ( m 一1 ) n ，仇( n 一1 ) ) 1 0 3 图的分数划分数 图的分数划分数，早在1 9 9 0 年r a l l 在文献【7 】中就证明了：对任意图g 都有 d ，( g ) = 6 + 1 但是我们对圈的分数划分数的讨论发现对任意图g 不一定都有 由( g ) = 6 + 1 ，从而本文重新给出了分数划分数的界及一些特殊图的分数划分数 3 1 图的分数划分数的界 定理3 1 对任意一个礼阶图g ，均有t a g ) d ，( g ) n 成立 证明：令 ，厶，厶) 是g 的分数控制簇，其中d = d s ( g ) 由定义可知 ddd 7 i ( g ) d i ( g ) = r a g ) 五( ) = 五( ) 1 = 佗 i = 1i = 1t ，y ( g ) v e v ( a ) i = 1 , e v ( a ) 定理3 2 对任意一个最小度为6 的图g ，均有6 d r ( g ) 6 + 1 且两个界都是可 达的 证明：先证d r ( a ) 6 + 1 令 ，五， ) 是g 的分数控制簇，其中d = d r ( g ) ，幻为g 中的一个最 小度点，则有 下证由( g ) 6 令是g 中的一个最小度点，对1 i 石_ 1 ，定义五：v _ 【0 ，1 】如下： 施，= 渺x 舵2 - - u ， + l l 洲 一 d：l 洲 = 五 州 d 甜 一 d 甜 = g 略 3 图的分数划分数 对i = 6 ，定义 ：v 一【0 ，1 】如下： f 五( z ) = 【 + j 1 吾1 ) 6 ，z = u ， ， 其它 则可知对任意的1 i 6 ，五都是g 的分数控制函数且对任意的点x v ( c ) 都 有 ( z ) = 1 故由( g ) 6 这样我们证明了定理的第一部分为了说明两个 界是可达的，考虑n 阶圈图g 在本章的定理3 4 中，我们将证明t t 是3 的倍数 时，d i ( c n ) = 3 ；扎不是3 的倍数时，则d l ( g ) = 2 这与定理中的界是一致的，从 而完成了定理的证明 3 2 特殊图的分数划分数 定理3 3 若g 是一棵树，则有d ，( g ) = 2 证明： 因6 ( g ) = 1 ，所以由定理3 2 易知d ，c a ) 2 下证d l ( g ) 2 令秽是g 中的一个端点，缸t ，曰( g ) ，b 1 = 叫： t t w 曰( g ) ，d ( w ) = 1 ) 定义 ，2 ：v _ 【o ，1 】如下： ( z ) = 厶( z ) = z b t ， z = 乱， x v ( c ) 一b l 一 u ) x b i ， x = t 正， x v ( g ) 一b l 一 u ) 则 ，厶均是g 的分数控制函数且对任意的x v c c ) 均有 ( z ) + 厶( 。) = 1 所 以由( g ) 2 综合上述，定理3 3 得证 1 2 ，i，、_，lll_l，、i-l一， 3 图的分数划分数 定理3 4 对任意7 , 阶圈g ， ( a ) 若n 是3 的倍数，则d ，( g ) = 3 ， 嘞若不是3 的倍数，则d a c ) = 2 证明： 因巧( c k ) = 2 ，则由定理3 2 易知2 d a c k ) 3 令g = 钉1 忱t ，1 下面分别通过n 是否是3 的倍数两种情况证明定理 情况1 ：礼是3 的倍数，则d a c ) 3 定义 ，厶，1 3 ：v t o ，1 】如下： 他) = ， 2 一 ；：嘉4 ，3 肛2 | ：嘉4 ，3 2 ， 则 ，厶，1 3 均是g 的分数控制函数且对任意的z y ( g ) 均有 ( z ) + 厶( z ) + 厶( z ) = 1 所以d a g ) 3 情况2 ：n 不是3 的倍数，则d i ( c ) 2 假设结论不成立，则办( g ) = 3 不妨设 x ，f 2 ， ) 是g 的分数控制函数 簇，由分数控制函数簇的定义可知 注意到 3 五( z ) = 五( z ) 1 = n z e v ( g )v e v ( c ) - e n | , , lv e v ( c k ) 1 3 d n = 1 n：i 一 愀方 3 触 n 汹 3 图的分数划分数 即五( u ) 詈因此有 v e v ( “) ( 3 2 ) 由( 3 1 ) 和( 3 2 ) 可知，对任意的z v c c ) 都有 ( z ) = 1 令a = 正m m ) ，尼池) ， 陬) ) ，则当l i 一引三o ( m o d3 ) 时，有a i = 坞因为n 不是3 的倍 数，所以a i = 一p 五 吣 3：l ，-，、i_，-i，、一， 3 图的分数划分数 证明：因石( g ) = 3 ，则由定理3 2 易知d l ( g ) 4 下证由( g ) 4 令 口l ，v 2 ，) 是g 的点集，其中u 1 是轮图的中心定义 ，厶，厶，4 ： y _ 【0 ，1 】如下： ( 仇) = g = 1 ，2 ，n ) ， 。 腓，= ；| ：嘉 一滢是 一垤蒜 则 ，1 2 ，3 ，1 4 均是g 的分数控制函数且对任意的z v ( a ) 均有 ) + 厶( z ) + ，3 ( z ) + ) = 1 所以办( g ) 4 综合上述，定理3 6 得证 定理3 7 若g 是n 阶的完全图，则有d i ( a ) = n 证明： 因艿( g ) = n 一1 ，则由定理3 2 易知d l ( g ) 礼 下证以( g ) n 令v l ，忱，) 为g 的点集，对任意的1 i 歹佗，定义五：y _ 0 ，1 】 如下： 五( ) ： l t = 五 【0 ，i 歹 则 均是g 的分数控制函数且对任意的z y ( g ) 均有壹 ( z ) ：1 所以 i - - - - 1 由( g ) n 综合上述，定理3 7 得证 1 5 3 图的分数划分数 定理3 8 若g = n 是完全二部图，其中m ，他2 ，则有 粥= r a i n r e , n ，+ 1 证明：因6 ( g ) = m i n m ，n ) ，则由定理3 2 易知 m i n m ，n ) d s ( g ) m i n m ，n + 1 m 佗 m = n ( 3 3 ) 下面通过m 与竹之间的关系进行分类证明： ( 1 ) 若m 礼，则d ，( g ) m i n m ，n ) + 1 令x = z l ，z 2 ，z m ，y = 1 ，沈，) 是g 的两个分部不失一般性， 设m n ，对1 i m + 1 ，1 歹仇和l 忌扎定义五：v _ 【o ，1 】如下： 五) = 而1 地，= 溶 则五都是g 的分数控制函数且对任意的z v ( a ) 均有五( z ) = 1 ，所以 d ，( g ) 仇+ 1 即m n 时，有d ，( g ) m i n m ，钆) + 1 ( 2 ) 若m = n 2 ，则办( g ) m i n m ，n ) 假设仇= 扎时，办( g ) m i n r a ，佗) 不成立，则由( 3 3 ) 可知由( g ) = m i n ( m ，n ) + 1 不妨设d = _ ，丘，厶1 ) 为图g 的分数控制簇设 x = z 1 ，z 2 ，) ，y = 秒1 ，沈， 为图g 的两个部，x 中的点x i 在 办下的赋值为，y 中的点讥在办下的赋值为，我们分别用矩阵a ，b 来表 1 6 1 l m = 或 ， 一 m 仇 磊 办 l k = = b 办 + + ，j ， 7 - = = “吲鸵 一 3 图的分数划分数 。二二一 示这种赋值关系其中矩阵a ，b 如下： a 性爱h 蠹5 1 1b12-哥bl,(m+1) m + 1 令a 2 j 菱= 1 ，群= 对任意的i 1 ，2 m m + 1m 圣，最= ，弓= 由分数划分簇的概念可知， l = l j = li = 1 ，仇) ，都有a i 1 ，最1 且对任意的 1 1 ，2 ，m + 1 ，都有+ 彰1 ，+ 群1 贝有 m + 1 j = l l r b + 1 j = l m + 1 ( a i j + 彰) = 缸 彰m + 1 j = l l t t + 1 ( 6 巧+ ) = 鼠+ 码m + 1 j = l 由a ，q ，b i ，彰的定义可知，m + l 码：曼 j = 1 l = 1 i 1 ，2 ，m ) ，j ( 3 4 ) ( 3 5 ) m + 1m a ，弓= 鼠因a i 1 ，鼠1 ， j 2 1l = l 所以芝码：曼a m ，芝彰：曼最m 结合( 3 4 ) ，( 3 5 ) 可得对任意的 j = l i = 1 j = l i = 1 i 1 ，2 ，仇) 都有a i = 鼠= 1 。旦世1 1m1mtj m + l 因l 一彰，所以有善薹蚤暑( 1 一彰) 2i 茎- - - - ( m + 1 一暑弓) = l = 1j = 1 l = lf = ii i 一1 mm ( m + l 一 i = i i = 1 m 恳) = ( m + 1 一m ) = m i = i 结合两个不等式，我们有。巧= 1 一 mm 4 - 1 m 另一方面，= i = 1j = li - - - - 1 i = 1 弓对任意的i 1 ，2 ，m ) 均成立，则对 任意的g ，h 1 ，2 ，m ) 均有a g j = 同理我们有：1 一码对任意 的i 1 ，2 ，m ) 均成立，则= 对任意的g ，h 1 ，2 ，m ) 均成立 所以由a j = 1 一目可知，对任意的k 1 ，2 ，m ) ，均有：警又因 + 群= 1 可知，气箸+ 仇= 1 ，则a j = 赤同理我们可得= 矗则 有f x = 厶= = 厶+ l ，这与集合的互异性相矛盾故当m = n 2 时，有 d ，( g ) m i n m ，n ) 综合上述，定理3 8 得证 1 7 m | i 1 仇 f 争 这与竹( ) f 詈1 矛盾故引理4 1 成立 令n l = e e ( ) ：，( e ) = - 1 ，g 1 是g 中由e - 1 生成的子图 ( 4 2 ) 引理4 2 若，是m 4 ) 的一函数，且y 中含有t 个点在，下赋值为 一1 则 1 9 4 图的全符号控制数 ( a )当n 为偶数，e ( g 1 ) 譬一t - f1 时，( g 1 ) 譬； ( b ) 当n 为奇数，e ( g 。) 堡坐4 一t 时，( g 1 ) 譬 首先我们先证引理4 2 ( a ) 假设引理4 2 ( a ) 不成立，即g l 中存在点钉使得d a 。( t ，) = a ( g x ) 鼍令 亿1 = 钍：f ( u v ) = 一1 ) ，= u ：，( 让t ，) = 1 ) 且设亿1 中含有七个点在，下赋 值为一1 因 1 ，心叫= ，( u ) + ，( 钉) + ，( e ) + ，( e ) 一，( 牡u ) ( 4 3 ) e e ( u )e e e ( v ) 下面我们通过，( u ) 的取值进行分类讨论： ( a 1 ) ，( 钞) = 1 则由( 4 3 ) 可知对任意的乱亿1 ，若f ( u ) = 一1 ，则d g 。( “) 礼一2 一z x ( a x ) ； 若，( u ) = 。1 ，则d g ，( u ) sn l 一( g 1 ) 对任意的u v x ，若，( t ) = - 1 ，则 d g 。( 钍) n 一3 一z x ( g 1 ) ；若f ( u ) = 1 ，则如。( u ) 死一2 一( g 1 ) 故有 e ( g x ) ( ( g 1 ) + ( ( g 1 ) 一南) 一1 一( g 1 ) ) + 七一2 一( g 1 ) ) + 一七) 一3 一z x ( a x ) ) + 一1 一( g 1 ) 一t + 忌) ( 礼一2 一( g 1 ) ) ) = ( n 2 3 n h a ( g 1 ) + 3 a ( g 1 ) 一t + 2 ) ( 舻一3 n 一譬+ 3 鸶一t + 2 ) 。 = 下n f 2 - - 3 n 一 + 1 由引理4 1 知t 嘲，故e ( g 1 ) 丁n z - 3 n 一 + 1 百1 1 , 2 一t + l 矛盾 ( a 2 ) ，( 钐) = - 1 则由( 4 3 ) 可知对任意的乱亿1 ，若，( 仳) = - 1 ，则d e 。( 让) n 一1 一( g 1 ) ； 若，( 让) = 1 ，则d g 。( u ) 佗一( g 1 ) 对任意的i f , ，若，( u ) = 一1 ，则 4 图的全符号控制数 d g 。( 乱) 礼一2 一( g 1 ) ；若，( u ) = 1 ，则d g ，( 也) t , 一1 一z x ( a 1 ) 故有 e ( g 1 ) ；( ( g 1 ) - t - ( ( g 1 ) 一七) 一( g 1 ) ) + k c n 一1 一( g 1 ) ) + ( t 一七) ( n 一2 一( g 1 ) ) + ( 扎一1 一a ( a x ) 一t + 后) ( 佗一1 一( g 1 ) ) ) = ( 舻一2 n n a ( g 1 ) + 3 a ( g 1 ) 一t + 1 ) ( n 2 2 n 一譬+ 3 警一亡+ 1 ) = t n 2 - n 一；+ i 1 由引理4 1 知t 吲，故e ( g 1 ) 丁1 1 , 2 - - n 一+ 譬一t + 1 矛盾 综合上述，引理4 2 ( a ) 成立 下证引理4 2 ( ” 假设引理4 2 ( b ) 不成立，即g 1 中存在点口使得d g 。( u ) = ( g 1 ) 孚令 v _ t = 让：，( 删) = - 1 ，= u ：，( 伽) = 1 ) 且设亿l 中含有k 个点在，下赋 值为一1 下面我们通过，( t ，) 的取值进行分类讨论：。 ( b 1 ) ，( u ) = 1 由( 4 3 ) 可知对任意的u 忙1 ，若，( 牡) = 一1 ，则d g 。( u ) 佗一2 一z x ( v 1 ) ； 若，( 心) = 1 ，则d g 。( 牡) 佗一1 一( g z ) 对任意的u 若，( 让) = 一1 ，则 如。( 乱) n 一3 一( g 1 ) ；若，( 让) = 1 ，则如。( u ) n 一2 一( g 1 ) 故有 e ( g 1 ) ( ( g 1 ) + ( z x ( a x ) 一尼) ( 仃一1 一( g 1 ) ) + 忌( 扎一2 - 二( g 1 ) ) + ( t 一后) ( n 一3 一a c a , ) ) + ( 竹一1 一a ( a t ) 一t + 尼) ( 礼一2 一( g 1 ) ) ) = ( 舻一3 n n x ( a 1 ) + 3 ( g 1 ) 一t + 2 ) ( 佗2 3 n 一佗苎尹+ 3 警一t + 2 ) = 血4 一t 一旦2 一互1 牮一t 这与条件矛盾所以当，( 口) = 1 时引理4 2 ( b ) 成立 2 1 4 图的全符号控制数 ( b 2 ) f ( v ) = - i 由( 4 3 ) 可知对任意的t 亿1 ，若f ( u ) = - 1 ，则d g 。( 让) n 一1 一a ( a 1 ) ；若 f ( u ) = 1 ，则d g 。( 心) 耐n ( g 1 ) ，佗一( g 1 ) ) 对任意的u ，若( u ) = - i ， 则d g 。( 让) 礼一2 一( g 1 ) ；若，( u ) = 1 ，则如。( 乱) 佗一1 一( g 1 ) 故当( g 1 ) n + 2 l 时，有 e ( g i ) ( ( g 1 ) + ( ( g 1 ) 一七) ( n a ( a 0 ) + 尼一1 一( g 1 ) ) + ( t 一尼) ( n 一2 一( g 1 ) ) + ( 他一1 一a ( g 1 ) 一t + 尼) ( 礼一1 一( g 1 ) ) ) = ( n 2 2 n n a ( g 1 ) + 3xa ( g 1 ) 一t + 1 ) ( 礼2 2 n n 1 n + r l + 3 丁n + l t + 1 ) n 2 + 5 n + t 42 由引理4 1 知t 吲，古k e ( c 1 ) f ( v ) = 一1 时，引理4 2 成立 丁n 2 + 5 一n r + t 牮一亡矛盾所以当a ( g 1 ) 墨笋， 下证当( g 1 ) = - - _ _ 2 1 ，f ( v ) = 一1 时，引理4 2 ( b ) 也成立 当a ( g 1 ) = , , 2 - - 1 时，设g 1 中含有z 个点的度为孚因 n 2 r + 3 一亡e ( g 1 ) 互1 ( t n - - 1 z 十t n - 3 唧一z ) ) 可知z 幽22 t ，则z 一( n t ) 幽2 2 t 一佗+ t 2 即g 1 中含有两 个点v i ，吩满足f ( v i ) = f ( v j ) = - - i ( 否则由( b 1 ) 的证明可知引理4 2 ( b ) 成立) ， d g 。心) = d a 。( ) = 孚则 f v i v j = ，( 优) + ，( ) + ，( e ) e e e ( m ) + ，( e ) , e e ( v d ( v i t 3 j ) - 1 这与全符号控制函数的定义矛盾故引理4 2 ( b ) 对( g 1 ) = 孚也成立 综合上述，引理4 2 得证 4 图的全符号控制数 引理4 3 若，是玩4 ) 的臂函数且y 中含有t 个点在，下赋值为一1 则f ( e ) 鸶1 + 2 t n 假设引理4 3 不成立，即f ( e ) 詈1 + 2 t n 当他是偶数时，f ( e ) 詈1 + 2 t n 即f ( e ) 詈+ 2 t 一礼，则e 中至少含有 譬一+ l 条边在，下赋值为一1 由鸽笼原理可知g l ( 定义同上) 中至少存在一 个点竹g 1 满足d a 。( u ) 鸶一挈1 ，则( g ) 鼍一警1 f 纠这与引理 4 2 ( a ) 相矛盾 ，当死是奇数时，( 刀) 一 竹 ， 。似 鲫 i i 佻 八 n：l l i rm 仇 一 八 6 芦 “汹 + 扣， i f 咙 八 竹汹 = rm忱 5 图的全减符号控