（运筹学与控制论专业论文）正则图的上负全控制数.pdf

论文摘要 在过去的三十多年里，随着计算机科学的迅速发展，图论也得到了迅速发 展，而控制数理论的研究是图论中发展最快的几个领域之一随着研究的深入 和应用的激发，各种新的控制参数不断涌现其中图的函数控制数就是控制数 的自然推广由于函数的引入致使利用函数性质来研究控制数成为可能目 前函数控制数已成为图的控制理论中一个崭新而富有挑战的研究方向对一 般图而言，几乎所有的函数控制数的判定问题均是p 完全的，所以对它们的上 下界进行精确估计以及图的结构性质刻画是人们很感兴趣的问题，这对于设 计相应的近似算法也有重要的实际意义 h 耐s 2 l 】等人引入图的上负全控制数的概念厂：h g ) _ 卜l ，0 ，l l 称为图g 的负全控制函数，如果对任意点v y ，均有九y 】l ，其中九v 】= 州订八v ) 如果对 每一个点，矿，不存在负全控制函数g ：坎g ) - 一l ，o ，l ，g ，满足g ( y ) 八v ) ， 则称厂是一个极小负全控制函数图的上负全控制数f ( g ) = m a x i 山l 是g 的极小负全控制函数 ，其中洲= e 玎g 1 八v ) 本文主要研究了函数的上负全 控制数，其相应的结果分为以下两部分： 第一部分，首先介绍了3 正则图，5 一正则图的f ( g ) 的可达上界，接着归纳出 度为奇数的正则图的f ( g ) 的可达上界，并刻画了达到此上界的极图 第二部分，首先介绍了2 - 正则图，4 一正则图的f ( g ) 的可达上界，接着对6 正 则图的f ( g ) 的可达上界进行了探试并对度为偶数的正则图的f ( g ) 的可达 上界给出了猜想 关键词： 肛正则图；上负全控制数；控制数； a b s t r a c t w i t 垃n 也el a s tm o r e 也a nm i r t yy e a r s ，c o n c u f r e n tw i 也也e 争d w t l lo fd o m i n a t i o ni n 铲a p h si so n eo ft h e 伍s t e s tg r o w i n ga 陀皓w i t l i i n 伊印ht h e o r y w i t hr e s e a r c h i i l gd e 印l y ， m a r l yd i f l e r e n t 帅e so fd o m i i l a t i o np a r a m e t e r sh a v es p m n gu pr a p i d l y d o m i n a t i n g 向n c t i o n i n 粤a p hi sm en a t u r a l 谢a t i o no fd o m i n a t i o n t h u s ，i ti sp o s s i b l et 0s t u d yd o m i n a t i o ni i l t e 姗so ff u n c t i o n a lp r o p e n i e s n o w a d a l y s ，l es t u d y0 nd o m i n a t i n gf h n c t i o 璐i san e wa n d c h a l l e n g i n gr e s e a r c hf i e i di nd o m i n a t i o nt h e o 叫a sa l m o s ta ud c c i s i p r o b l e m so fd o m i i l a t - i n g 缸c t i o n sa r e p c o m p l e t cf o r 彤m e m l 孕a p h s ，i ti si n t e r e s t i n g 的i n 、，e s t i g a t eb o l m d so f t l l o s e 龃dc h a r a c t e r i z et h es m j c t i l r eo f 鲫h s ，w h i c hi s 璐e 缸lt od e s i g nt t l e i ra p p r o x i i n a t i o n a l g o r i m m s h a r r i si n 打d d u c e du p p e rm i n u st o t a ld o m i l l a t i o ni nr e f e r e n c e 2l 】at h r e e - v a l u e d 向n c - t i o n 厂d e 矗n e do nt h ev e n i c e so f ag r a p hg = ( k d ，一f l ，0 ，1 l ，i sam i r m st o t a ld o m i n a t i n gf h n c t i o n ( m t d f ) ，i e v e d ry y ，九v 】l 川= 删d ) = 酬订八d ) a nm t d f 厂i sm i n i i n a l i ft h e r ed o e sn o te ) 【i s t 蛆m t d fg ：以g ) _ l 一1 ，0 ，l ，厂g ，f o rw h i c h 氧v ) s 八df o re v e r yv 坎g ) t h ew e i 曲to f a nm t d f i su = 俺悯八，) t h eu p p e r m i n u st o t a ld o 血n a t i o nr - ( g ) = m a ) 【f u i 厂i sm i i l h a lm i n u st o t a l d o m i m t i n g 血n c t i o no f g h 1t h i sp a p e r w em a i l l l yi n v e s t i g a t eu p p e rm i n u st o t a ld o m i n a t i n g 如n c t i o n smr e g u l a r g r a p l l s ，a l l dt l l ec o r r e s p o n d i n gr e s u l t s 盯e 也ef 0 1 1 0 w i n g 铆op a n s ： i nt h e6 r s tp a r t ，w ef i r s t l yi n t r o d u c eu p p e rb o u n d so nr ：( g ) o f3 一r e g u l a rg r a p ha n d5 一 r e g u l a r 野a p h a l s o ，w ee s t a b l i s h 锄u p p e rb o 岫do nf ( g ) o ft l l e 肛r e g u l a rg r a p h i s 粕 o d d ) 锄dc h a r a c t e r i z et h ee x t r e m a l 卿h sa t t a i n i n gt h eu p p e rb o u n d i nt h es e c o n dp a r t ，w ef i r s t i yi n 仃o d u c eu p p e rb o u n d so nf ( g ) o f2 r e g i l l 甜乒a p h 柚d 4 r e g u l a r 轳a p h a l s o ，w es t u d yu p p e rb o u n do nc ( g ) o f6 r e g u l a r 蓼a p h a n dg i v e 也e c o n j e c t u r eo f u p p e rb o u n do nf ( g ) o f t l l e 肛r e g u l 甜g r a p h ( 七i s 锄e v i m ) k e y w o r d s ：缸r e g u l a rg r a p h s ；u p p e rm i i m s t o t a ld o m i n a t i o n ；d o m i n a t i o nn u m b e r i i 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成果据我所知，除文中已经注明引用的内容外，本文不包 含其他个人已经发表或撰写过的研究成果对本文的研究做出重要贡 献的个人和集体，均已在文中作了明确说明并表示谢意 作者签名： 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版有权将学位论文用于非盈利目的的少量复制并允许论 文进入学校图书馆被查阅有权将学位论文的内容编入有关数据库进 行检索有权将学位论文的标题和摘要汇编出版保密的学位论文在 解密后适用本规定 学位论文作者签名：赳导师签名：兰么妙 日期：山立：上：2 口 日期：型皇彰裂刍 第一章背景 在过去的三十多年里，随着计算机科学的迅速发展，图论也得到了飞速发 展，而控制数理论的研究是图论中发展最快的几个领域之一控制数理论能够 快速发展的主要原因是它在组合优化、编码理论、计算机科学、通讯网络、 监视系统和社会网络等理论与实践中有着重要的应用 对图的控制数的研究最早可追溯到十九世纪中期当时有一种棋盘比赛， 棋赛的目的就是用某些棋子覆盖或者控制棋盘上的所有方格，人们注意到了 在棋盘上如何放置最少几个皇后就可控制( 覆盖) 或占据所有的方格这样的问 题，这就是图的控制数问题的最初形式 在1 9 6 0 年前后，人们开始对图的控制数迸行数学理论方面的研究所公 认的图的控制数理论是在1 9 5 8 年由b e 唱e 和1 9 6 2 年由o 托共同建立的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 t 。和。d o i i l i n a t i o nn 哪b e r ”1 9 7 7 年，c o c k a ) r n e 和 h e d c t n i e m i 在一篇报告中综述了当时已知的有关图的控制数的结果，并且首次 使用符号y ( g ) 表示图g 的控制数，此符号一直沿用至今此后的1 0 多年里，这一 理论开始引起人们的广泛关注并得到迅速发展，众多的研究者纷纷投入到控 制数问题的研究中来据1 9 9 0 年d i s c r e t e m a t h e m a t i c s 出版的一期专集统计，截 止当时累计的文献就达到了4 0 0 篇随后控制数理论成为图论中一个重要的 研究热点鉴于此理论的迅速发展，1 9 9 8 年，美国学者h a y n e s ，h e d e 血e m i 和s l a 衙 在对次领域进行系统总结后，首次出版了两本关于图的控制数理论的专著 d o m i n a t i o ni ng r a p h s - a d v a n c e dt 0 p i c s 和嵌f u n d a m e n t a lo fd o m i n a t i o ni ng r a p h s ， 其中在f 1 1 i l d 锄e n t a lo fd o m i n 撕0 ni ng r a p h s 中引用了1 2 0 0 多个文献2 0 0 0 年， a m s 为d d 历砌口砌刀s p 括，加却p ，? d 锄f s p 黯，c ，f g “甜在分类条目中专列了一项0 5 c 6 9 随着控制数理论研究的深入和应用领域的拓宽，各种控制参数也不断涌现 到目前为止，控制参数种类已经多达几十种，其中，函数控制数就是控制数的一 种自然推广1 9 9 6 年，b a n g e 等引入了一类推广的图的控制数p - 控制函数设p 是一实数集，函数：h g ) p 称为图g 的只控制函数，如果对每个点，坎g ) ， 有八 v 】) l ，这里，m = 材lz ，v e ( g ) lu v ，八 川) = 蜒【，】八甜) 图的p 控制 数定义为：枷= m i n 八功j 是g 的尹控制函数 当尹= 1 0 ，1 时则是图的标准控 制数；当尹= i 一1 ，l 和尹= l 一1 ，0 ，1 时 则分别是图的符号控制数和负控制数把 上述定义中的八 ，】) 1 改为八( d ) 1 就得到相应的全控制数、符号全控制 数和负全控制数。 吴建刚：正则图的上负全控制数 文献 2 1 中给出了关于负全控制数的一个有趣的研究背景例如，我们考 虑某个社会群体网络中的投票问题假定每个个体都有一张投票并持有最初 的意见；进一步，假定具有某种关系的个体之间的最终投票意见是互相影响的， 且每个个体对与之有某种关系的所有个体的投票意见的影响权重都相同如 果与某个体有某种关系的所有个体中持赞成票的个体数多于持反对票的个体 数，那么该个体最终就投赞成票；否则，就投反对票对此社会群体进行最初投 票意见的分配如果使每个个体最终都投赞成票的话，则把此投票意见分配称 为一致赞成分配在所有的一致赞成分配中，我们主要对最初持赞成票或中立 票的最少个体数目感兴趣 下面，我们对上述问题做个图论模型图中的点表示个体，两点之间的边表 示对应的两个个体具有某种关系给持有赞成意见的顶点赋值+ l ，给持中立意 见的顶点赋值0 ，给持反对意见的顶点赋值一l ，这样图中度大的顶点具有较大 的。影响力”图的负全控制数就是某个一致赞成分配中所有意见的最小可能 和因此负全控制数也可以表示某个一致分配中持赞成票或中立票的最少个 体数目，且与之对应的意见分配可迫使每个个体最终都投赞成票 目前，对于函数控制数的研究主要集中在以下几个方面； ( 1 ) 确定他们的上下界，计算一些特殊图的值； ( 2 ) 寻找各种控制参数之间的关系； ( 3 ) 给出极端图类的结构性质的刻画； ( 4 ) 讨论其复杂性问题、算法及应用问题 本文主要研究了函数的上负全控制数，其相应的结果分为以下两部分： 第一部分，首先介绍了3 - 正则图，5 正则图的f ( g ) 的可达上界，接着归纳出 度为奇数的正则图的f ( g ) 的可达上界，并刻画了达到此上界的极图 第二部分，首先介绍了2 一正则图，4 正则图的r - ( g ) 的可达上界，接着对6 正 则图的f ( g ) 的可达上界进行了探试并对度为偶数的正则图的f ( g ) 的可达 上界给出了猜想 2 第二章基本符号和结论 2 1 基本概念和记号 设g = ( k 日是一个简单图i h g ) i 称为图g 的阶数如果图何满足条 件h 仞y ( g ) 并且e ( ee ( g ) ，则称胃为图g 的一个子图对s 以g ) ， g s 】表示由s 导出的子图图g 中点x 的开邻域( 工，g ) = 圳砂e ( g ) ，工 的闭邻域kg 】= ( 石，g ) u x 更一般地，对xeh g ) ，i 忑g ) = u 剃( 工，g ) 和g 】= m xg ) u 石在不引起混淆的情况下，上述符号可分别简记为 ( 力，m 胡，和啪我们称吠曲= 眦曲i 为点j 的度双g ) 和( g ) 分别表示图 g 的最小度和最大度。度为l 和o 的点分别称为图的悬挂点和孤立点，所有顶点 的度都等于七的图称为七正则图图g 中度为奇数和偶数的点分别称为奇点和 偶点s h g ) 是g 的一个独立集，如果s 中任意两个不同的点在图g 中不邻 接凡是文中未加定义的术语和符号可参看文献 5 2 】 由刀个顶点构成的路和圈一般记作r 和g 若图g 中的任意两个相异点之 间都有边相连，则称g 为完全图，刀个顶点的完全图记作焉用g = ( n ，坎，“；e ) 表示顶点集是u 笔巧，边集是l 砂e ( g ) b k ，y 巧，l f 0 ，至少存 在一个点“( v ) ，使得九“】1 1 ，2 1 类似地，图的符号全控制数和上符号全控制 数即为： w ( g ) = m i n i 是g 的符号全控制函数 和 e ( g ) = m a ) 【 山i 厂是g 的极小符号全控制函数 x i n g 4 5 】等人引入图的多数全控制数( m a j o r i 妙t o t a ld o m i n a t i o n ) 的概念，函数 ：h g ) 一 一1 ，1 称为g 的多数全控制函数，如果矿中至少一半的点满足 月v 1 多数全控制数定义为s 吒。，( g ) = m i n l 是g 的多数全控制函数j 最近x i n g 4 6 】等人还引入了七一符号全控制数限s i 萨e dt o t a ld o m i l l a t i o n ) 设七为正 整数，l 七i 吲函数：以g ) _ 一l ，1 l 称为g 的缸符号全控制函数( 尼s t f ) ，如果 y 中至少存在七个点，满足九v 1 一个烬t f 厂是极小的，如果对每个点1 ，y ， 不存在g 的一个七s t fg ，使得g ，且甙，) 八y ) 图的七一符号全控制数和肛上 符号全控制数分别为： 4 第二章基本符号和结论 和 住( g ) = m i n i 蝴i 厂是g 的七s t fl 屹( g ) = m a ) i 酬i 是g 的极小髂t f 显然当j | = r 譬1 ，l 明时，吃( g ) 分别为多数全控制数和符号全控制数，而当七= l 明 时，屹( g ) 就是上符号全控制数 2 2 函数全控制数的主要结果 近些年来对上述各种函数控制参数的研究主要集中在界、判定问题的复 杂性、算法、各种参数之间的关系以及极图的刻画等方面下面我们给出相关 的主要研究结果 关于( 上) 全控制数方面的研究主要有以下结果。 定理2 2 1 ( 【5 ) 若g 是刀3 阶的连通图，则竹( g ) 挚，并且此界是可达的 定理2 2 2 ( 2 5 】) 若g 为刀阶的连通图，最小度6 ( g ) 2 ，并且g 不属于 c 3 ，c 5 ，c 6 ，c l o l ，则竹( g ) 挈 定理2 2 3 ( 【1 6 】) 若g 为栉阶的图，最小度故g ) 3 ，则竹( g ) 台 下一个定理是文献 1 6 中的猜想，2 0 0 4 年分别被觚h d e a c o n 等八位研究者 独立地解决了 定理2 2 4 ( 1 】) 若g 为髓阶的图，最小度故g ) 3 ，则竹( g ) 51 ，并且此界是可 达的 最近，1 1 1 0 m s s e 和y e o 又得到了关于全控制数的一个新上界 定理2 2 5 ( 4 3 ) 若g 为刀阶的图，最小度以g ) 24 ，则y f ( g ) 孚 其他有关全控制数的研究成果可参阅文献 8 ，2 8 ，2 9 】 定理2 2 6 ( 1 7 】) 若g 为刀阶的连通无爪图，最小度6 ( g ) ，则 5 吴建刚：正则图的上负全控制数 r ，( g ) 掣如果6 l ，2 急如果6 3 ，4 ，5 如果6 6 此外，r f ( g ) = 掣半，当且仅当g 侈iu 院；若6 3 ，4 ，5 l ，则r f ( g ) = 急当且仅当 g 玩或占= 5 时g 厂；若6 6 ，则r f ( g ) = 等当且仅当g 厂够iu 伤，玩和厂 的构造见文献【1 7 】) 下面介绍一些有关全控制数和上全控制数的复杂性方面的研究结果，我 们首先介绍p 完全理论中判定问题( d e c i s i p r o b l e m ) 的概念一类问题，如果 它的每个实例都可以表述为用。是”或。否”来回答的形式的话 那么称之为 判定问题 定理2 2 7 ( 3 9 ) 对于一个给定的二部图或弦图g 和一个正整数七i 吲，判 定m ( g ) 后是否成立是p 完全的， 定理2 2 8 ( 1 4 ) 对于一个给定的图g 和一个正整数七i 吲，判定n ( g ) 七 是否成立是p - 完全的 关于( 上) 负全控制数和( 上) 符号全控制数的研究，给出下面主要结果： 定理2 2 9 ( 3 8 ) 若g = ( n ，圪，k ；e ) 为，l 阶缸部图，七2 ，则 脚2 辱一刀 且此界是可达的 定理2 2 1 0 ( 4 2 】) 若g 为厅阶3 一正则图，则f ( g ) 等，等式成立当且仅当 g 厂 厂是一类3 正则图的集合，它的具体构造可参阅文献 4 2 】 定理2 2 1 l ( 4 2 】) 若g 为甩阶4 - 正则图，则f ( g ) 焉，等式成立当且仅当 g 尹 厂是一类4 一正则图的集合，它的具体构造可参阅文献 4 2 】 定理2 2 1 2 ( 5 0 ) 若g 为甩阶肛正则图，则 6 第二章基本符号和结论 且此界是可达的 焖 委譬翥萋 定理2 2 1 3 ( 2 7 】) 若g 为刀阶图，则w 订茅订+ l 一刀，等式成立当且仅当 g j 了是一类图的集合，它的具体构造可参阅文献【2 7 】 定理2 2 1 4 ( 2 7 】) 若g 为玎阶图，最小度6 2 ，最大度，则 焖c 黔粉卷名措咖 且此界是可达的 定理2 2 1 5 ( 2 7 】) 若g 为刀阶图，边数为埘，则w 2 伽一朋) 定理2 2 1 6 ( 2 7 】) 若r 为刀2 阶的树，( 丁) 为所有叶子的集合，则w ( g ) 2 ， 等式成立当且仅当每个点1 ，( h d 一三( 刃) 是奇度点且至少与( 硪d 一1 ) 2 个叶 子邻接 定理2 2 1 7 ( 2 7 ) 若g 为刀阶缸正则图，则 熊薹笔霜萋 且此界是可达的 此外，文献 4 0 中也给出了几乎正则图上c ( g ) 的上界 定理2 2 1 8 ( 4 2 】) 若图g 的所有顶点都是奇度点，则e ( g ) f ( g ) 下面介绍一些有关符号全控制数和负全控制数的复杂性和算法方面的研 究结果，我们首先给出图的符号全控制数和负全控制数的判定问题形式： 符号全控制数问题 实例：给出图g 和正整数七i 以g ) i 问题：谚( r ) 七是否成立? 7 吴建刚：正则图的上负全控制数 负全控制数问题 实例：给出图g 和正整数七sl y ( g ) 1 问题：万( 刃七是否成如 2 0 0 4 年，h 咖i i l g 证明了符号全控制数的判定问题是p - 完全的，而h 删s 和 h a t t i i l g 证明了负全控制数的判定问题是b 完全的 定理2 2 1 9 ( 2 7 】) 图的符号全控制数的判定问题是p - 完全的，即使对于二 部图或弦图也是成立的 定理2 2 2 0 ( 【2 l 】) 图的负全控制数的判定问题是只完全的，即使对于二部 图或弦图也是成立的 此外，在文献 2 1 】中h 删s 和h a t t i n 曲还给出了树上计算w ( n 和万( 乃的线 性时间算法 最后我们介绍一些有关多数全控制数和缸符号全控制数方面的研究结果 2 0 0 5 年，x i n g 等人研究了图的多数全控制数，并得到了下列结果： 定理2 2 2 1 ( 4 5 】) 对疗2 ，则 号学珂 8 第二章基本符号和结论 定理2 2 2 6 ( 4 5 】) 若g 为玎阶图，最小度和最大度分别为6 和，且图中的点 都为偶度点，则 ，一 6 2 + 2 ( g ) 岢刀 定理2 2 2 7 ( 4 5 】) 若g 为疗阶后正则图 1 ) ，则 且此界是可达的 c 回滢笔翥萋 2 0 0 5 年，x 血g 等人还对“符号全控制数进行了研究 并得到下列结果： 定理2 2 2 8 ( 4 6 】) 对刀2 ，则 住( ) s l 行为奇数卧 ! o 力为偶数且七s ； 3 狞为奇数且； 七s 拧 2 刀为偶数且； 七刀 定理2 2 2 9 ( 4 6 】) 对刀所l ，则 以；) s l 一刀 2 一刀 2 3 4 肌为奇数且七s 刀 朋为偶数且七s 刀 m ，行为奇数且刀 j | m + 厅 册+ 彬g 奇数且刀 j | 朋+ 刀 所，以为偶数且刀 七sm + 定理2 2 3 0 ( 【4 6 ) 若g 为拧阶，- 正则图( 厂之1 ) ，则 郴， 草笔霜萋 下列结果由x i n g 等人和h 删s 等人独立地得到 定理2 2 3 l ( 4 6 】) 对疗2 ，则 删玎劝奇筹叫 9 吴建刚：正则图的上负全控制数 定理2 2 3 2 ( 4 6 ) 对刀3 ，则 一+ 2 劝等2 定理2 2 3 3 ( 4 6 ) 若g 为疗阶图，最小度和最大度分别为6 l 和，则 吃( 回坚等警坐刀 1 0 第三章度为奇数的正则图的上负全控制数 本章给出了度为奇数的正则图的c ( g ) 的可达上界，并刻画了达到此上界 的极图 3 13 ，5 一正则图的上负全控制数 在介绍本节的主要定理之前，我们作以下准备工作： 设g = ( k e ) 为胛阶图厂：矿一i l ，o ，l 为g 上一个极小负全控制函数称 为g 的c ( 辞函数，如果酬= c ( g ) 对vey 和s 矿，用慨( v ) 表示s 中与v 相邻 的点集，且令i 慨( v ) i = 西( v ) 对x y ，且x ns = 0 ，令s ) = w e l “xv s l ，p s ) = i e s ) 1 p ，q ，和m 的定义分别为： p = 1 1 ，n 厂( v ) = + 1 l q = 1 ，明厂( 叻= o 肘= ，唧d = 一1 l 设i p i = p ，lq i = g 和i m = 脚因此，c 们= p 一加此外，我们还给出下列定义s = v p | 而( d = f ，州d = l 鳓= i v q l 纵v ) = f ，州d = _ ，l = 1 1 ，m 办( v ) = f ，如( v ) = j f l h o n gy a n ，x i a o q iy 粕g ，e 渤gs h 姐在文献 4 2 】中，给出了3 正则图的f ( g ) 的 可达上界 定理3 1 1 ( 4 2 ) 若g 为”阶的3 - 正则图，则f ( g ) ；刀，且这个界是可达的 h a i c h a ow a n g ，e 梳gs h a n 在文献 5 l 】中，给出了5 一正则图的f ( g ) 的可达上 定理3 1 2 ( 5 1 】) 若g 为刀阶的5 - 正则图，则f ( g ) 号，且这个界是可达的 下面的引理在证明本文的主要结论时有很重要的作用，它可以从文献 4 2 】 中得到 引理3 1 1 ( 4 2 】) 图g = ( k 司上的一个负全控制函数是极小的当且仅当 对每个点 ，矿且八，) 之0 ，则存在一个点甜( d 使得九z ， = 1 吴建刚：正则图的上负全控制数 3 2 度为奇数的正则图的上负全控制数 下面给出本章的主要结果t 定理3 2 1 若g 为刀阶的，- 正则图( ，为奇数) ，则f ( 回芸击刀并且这个 界是可达的 证明：设为图g 的一个c ( g ) 一函数令旧= p ，i d = g 和l m = 坍，则 c ( g ) = c = i 尸i l m = p 一所由定义可知，对任意点，y ，办( d 姒d + 1 l ， 如( 力，一l 一2 姒d ( 若如( v ) ，一2 姒d ，贝0 廓( d ，一( ，一2 州d ) 一d ，( v ) = z 材( d ， 故九y 】s0 1 矛盾) 因此可以把p ，q 和肘分别划分为以下集合； p 盯= ，p l 如( 叻= i ，d 以d = 工o j s 孚，osjs ，一1 2 ，l q 玎= i y q i 办( v ) = d “v ) = 工o5j f 譬，j + l j ，一_ ， 坞= 1 ，m 砟( d = 如( = 工o _ s ，一l ，l 孚j f 厂一且 且令i 户玎i = 砌，i 鳓i - 的和i 坞i 研盯，则 气1 ，一l 一巧气1r 一，r i，一 p = 胁g = 蛳m = 朋口 户o f o 户of 可+ l卢oh 掣j 令，= 0p 2 掣，q ，= 0q j + 1 ，吖= 0 脚盈显然，每个点 ，uq ，u ， f = o ，；0扛o 在下是g 的临界点，即月v 】= 1 ；而对每个点v ( y 一，uq ，u 膨) ，介v 】2 通 过计算边数配q ) ，“q ，岣，和d 只胸我们立即得到下列等式： ( 3 2 2 ) 根据引理3 1 1 ，对点，尸一，存在一个点“( d ，使得九甜】- 1 因此，对任 意点v p 一，总存在，uq ，u 吖中一个点与y 相邻，所以我们可以得到； 1 2 2 玎g 叫州学间 一 一ug力 一一 驴 叫叫争脚 一 w i l 9 只“ = 一up 蚺神 孚脚 一u m h好 一剧 = 聊g“ i l ug 一圳 争触 动0 一ug _：i宁脚 一 u m 力 一一 叫岬 舢 一删 = 坳 只 “ = 一u p 峋枷 宁脚 第三章度为奇数的正则图的上负全控制数 p p 妒一p ，p ，uq ，u ) = p ( p 一尸，p ，) + p ( p 一尸，q ，u ) = 主妒一，气，学) + 妒一尸，q ，u ) ( 3 2 4 ) 进一步，注意到对每个点 ，b l 掣，一定存在v 的一个邻点满足 九川= l ，也即，甜pu m u ( 对，ep 2 掣，如( d = 2 j ，州v ) = 笋， d p ( v ) = ，一2 f 一目净= 掣一o 若“，则v 至多邻接p 一，中的掣一f l = 譬一f 个 点但是，若“uq ，则v 至多与p 一，中的孚一f 个点相邻因此，可把p 2 ，掣划 分为两个子集气掣= i ，气掣i 啦p ( v ) = 学一f 和气掣= 尸2 f 半一气掣- 设i 哆掣i - 成掣，则i 掣l - 见f 学一p 幺掣因每个点 ，t l 学至少邻接 q ，u 凹中的一个点，所以p ：f 掣s “哆f 鸟芦，q ，u 膨) 因此，可得： 妒一尸，气学) = p ( p p ，气掣u 气，学) = 妒一p ，乞学) + 妒一尸，吆学) ( 孚一仰掣十( 孚- f ) 慨学一吆甲) = 吆学+ ( 孚一慨。学 甙哎学，q ，u m ) + 2 等砘甲 ( 3 2 5 ) ( 3 2 5 ) 式代入( 3 2 4 ) 式得： 单 p 一曼e 【p p ，& l 学】+ e ( p 一尸，q ，um ) j = o 1 3 吴建刚；正则图的上负全控制数 至( p ( l 掣，um ) + 璺笋尸2 l 掣) + 卵一p ，q ，u m ) 萎学见学+ 萎嚷掣刚脚俨哪u m ) 争 = j = o 孚 = j = 0 笋勉与等+ d 只q ，u m ) 学见t 掣+ 主( f +1 ) g + 昱掣埘掣2 j瑚一 下一步，我们开始建立f ( g ) 的上界，首先可得； 以2g + ，刀+ p = g + ，打+ p p + 掣犁犁 ( 拿+ m ) + 壶鼍p 如半+ 砉( f + 1 ) g + l + 奏半所掣力+ p扭o f = o_ o 。 z 一 掣犁犁 = ( 2 ，+ 1 ) 国+ 加) + 砉丘笋p 2 l t 学+ 言( f + l 妇扭i + 砉d 笋脚学2 ，+ 夕一2 ，q + 掰) = ( 2 ，+ 1 ) ( g + 所) 一口 一 犁犁犁掣 这里：口= 2 哟+ 所) 一 砉鼍p p z 。掣+ 耋o + 1 ，+ 喜气等册掣盈+ 砉p z t 学】 所以q + 聊玄i - 刀+ 荔旨口 所以p = 刀一( g + ，刀) 刀一( 丢：旨刀+ 五暑口) = 毒备刀一五：l _ 口 ( 3 2 6 ) 另一方面： 孕掣犁卑 p 2 p 一少+ p 7 砉旦笋p 2 半+ 砉( i + 1 州。，+ 喜g 竽研学盈+ 砉p 2 学 = 船差7 菅巾u 一船差7 营巾岍咖口 掣r l 一2 ， 由( 3 2 3 ) 得：_ ，砌= p ( 只胸= 删一 ，= oj = o 代入上式得： p 糌m 一多乏三署6 一、r j警r j 三( r f d 肌口一_ ，g 玎 卢o j = 【掣j 户of 叫+ l 这里6 = 蔫董。岍研口崔和”盖苫巾盯+ 貉口一帮( g + m ) 这里6 = ( ，一f 一力研口+ 杰一，g l ，+ 杰。p 盯+ 嬲口一掣黼( g + ，1 ) ，= o _ f = i 掣i 户o i 叫+ l ，= o 扛o 。 一 一 第三章度为奇数的正则图的上负全控制数 所以，竹勰p + 耥貉6 = 所以；c ( g ) = p 班p 一( 勰p + ；) = 笔糌p 一； ( 3 2 6 ) 式代入上式得： r 厂( g ) 苗毒碧( 南疗一由口) 一； = 毫基了刀一五圭五口一； = j 万一( 盎口+ ) = 妄基了刀一五拓【( ，2 + 1 ) 口+ ( 2 r 2 + 4 ，一2 ) 6 】 = 糌刀一万由写c 这里c = ( ，2 + 1 ) 口+ ( 2 厂2 + 4 厂一2 ) 6 ：酽+ 1 ) 口+ ( 2 户+ 和一2 ) 熏皇( 厂一f 一力所盯+ 差莹幻+ 差 歹p u 户。吼掣j 。户。蛳i剧脚 。 + 簧粒口一萼鲁字( g + 所) 】 = ( 4 ，2 4 力口+ ( 2 厂2 + 4 ，一2 ) ，一i ，o ， 户o f = 【字j 警r _ j ( ，一f 一力脚盯+ 户0 ，可+ i 争，- l 一巧 j q i j + j p i a 一2 ，( 3 户一4 ，一1 ) ( g + 肌) ：2 ( 户+ 1 ) ( w + 朋) + ( 2 户+ 4 ，一2 ) 型暑( 厂一f 一力蛳+ 差皇_ ，的 = o f = l 字j 。户o ，- ，+ i 。 争r 1 - 2 ，学犁犁 + 砉善。p 玎】一( 4 户一4 一 砉巴笋n l 学+ 言( f + 1 ) g 川，+ 砉巴笋脚学2 ，= o 括o l = o 。 o j = o = 0 2 一 争 + p 2 霉芦】 扛o 由式( 3 2 - 1 ) 得：，g ：差7 主刀 = ob o 由式( 3 2 3 ) 得：删= 。砌+ 孕r - l 一2 ， j = o j o 叼和册的表达式代入c 得： 警r j ( ，一f d g u + - g u j ：电i j + 、 r t r j 2 r j 三( ，一f 一力研玎+ - ，g 户o h 掣j 卢o ，叫+ i 争r 1 一巧争r 争，o争，一l 一巧 c = 2 ( 户+ 1 ) 二王f p 盯+ 三( ，一f 一力g + g u + p ， = o i = o 户o ，可+ l，- 0 仨一l f - 0i _ o 。 叫 - 卜触 + 一u p 吴建冈! ! 至型堕堕占壅全丝剑墼一 一一一一 犁争 + 砉学历掣盈+ 蠢勉掣】j = o i = u 勺删+ 1 ) ( 薹苫谢+ 1 ) ( 盖7 苫川+ ( 2 阳哇苫川 勺= 2 ( ，2 + 1 ) ( 杰。f p 玎) + 2 酽+ 1 ) ( 萎圣j p 盯) + ( 2 r 2 + 4 r 一2 ) ( 量- ，p 玎) i = oi 卸j = u 删 j 1 簟犁 一( 4 r 2 4 ，) 砉学p 2 l 学+ 毒n 掣】 ：+ 4 以薹7 菪歹咖) - ( 4 ，2 4 啾薹掣p ：。学) + 2 ( 产+ 1 ) 蓬7 苫7 即玎) ，= 0 f = o l = uj 一” 争 一( 4 r 2 4 r ) ( p 2 2 ；单) 1 = u 令2 j 吐则茎学p ：洋= 茗学p ，学再令学= 则至掣p z 洋2 茗字p ，甲= 丢- ，。办一t 一珊 所以m 4 r ) ( 营川州训( 薹掣鼢学w 蓬苫巾玎吾f = of - o l o u一” j” 另一方面： 2 ( 产+ = 2 俨+ = 4 ( r 2 + ) ( 羞7 营一( 4 阳顺耘掣) ) ( 宝f - p 玎) 一( 4 r 2 4 r ) ( ：墨p 2 j ，巴掣) ，= of = o f u 龃掣犁 ) ( 壹壹2 f p 2 u ) 一( 驴一4 r ) ( 堇p 2 学) 犁墨掣学 ) ( 杰芝i p 2 u ) 一( 4 r 2 4 r ) ( 圣p 2 j 号p ) 在上式中只有项_ 4 r 溉学为负而晒4 以盖7 营删_ ( 4 ，) ( 薹譬如掣) 中有项( 4 ，2 4 慨譬所以项胁争系数为o 综上可得：勺中所有项的系数都为正所以勺0 1 6 叫到争培 脚 学 崖脚 学 、， ， 2 h ， 土一 4 刍一2 一 学 产 学脚 q 晰 广 h h 盼 小 - 卜舢 审 ：= 句j 0附岫 力 _ 卜触 ， 叫蝌叫州一触争脚 一一笙三童鏖塑童墼笪至型堕丝占鱼全量型垫，_ _ - - - _ _ _ - _ - _ - _ 一一一一 c 研= 2 ( ，2 + 1 ) 【皇丢( 广一i 一力坍盯】+ ( 2 ，2 + 4 ，一2 ) 【皇莹( r f d m 口】 铲2 酽+ 1 ) 嚆，：舀j 卜卜抄嘶】+ ( 2 “4 卜2 呸j - 毒j ”卜伊脚】户o f 【掣j；u i = l 争j 犁 一( 4 ，2 4 r ) ( 言掣历半2 j ) = + 4 ，) 蓉；羔( 川一力哪卜( 4 r 2 4 ，) ( 至掣半d = ( 4 产+ 4 厂) ( ，一f 一力所i ；2 】一( 4 产一4 厂) ( 三2 笋! = 2 j ) 户o 扛l 年j 5 u 。 ：( 4 r 2 + 4 ，) 嘿鬟o ，一f 一力卜( 4 产一4 ，) ( 萎掣所学一 = ( 4 r 2 + 4 ，) ( r f 一力】一( 4 产一4 ，) ( 三2 笋研c = 学2 j ) 间户l 孚j = o = ”，2 + 4 r ) 嘿浏蔓( ，一i 一力】+ ( 铲+ 4 ，) 【娶，一2 i 一学) 埘学胡l = ( 4 ，2 + 4 r ) 【 ( ，一i 一力坍】+ ( 4 r z + 4 ，) 【( ，一2 i 一旦专= 生) 埘丝乒埘】 = 0 户l 争j 十l = u 训盖半哗圳 = ( 4 ，2 + 4 力崖莹( ，一f d 脚】+ 4 ， 至( ，一2 f ) 历皇犁函】一4 户丢聊吗掣埘 = ( 4 ，2 + 4 力 磊。互( ，一卜。d 脚】+ 4 r 盖( ，一2 ) 历学函】一4 产磊所学埘 枷产l 掣j + i 。2 0 。= u ，i ，一j宁 = ( 4 户+ 4 力 ( ，一f d 坳】一和2 f m 吗芦盈 j = o - 生挈 。 = o 由( 3 2 2 ) 式得差皇，锄：皇皇- ，m 驴所以c 中项2 ( r 2 + 1 ) 差皇j g u 可 由( 3 2 2 ) 式得邑i 1 ，的2 善，一笔- ，+ m 盯。所以c 中项2 ( r 2 + 1 ) 善f 参l j g u 可 芦i 卟l间f - i 掣i ：u ，叫+ 1 写成2 ( ，2 + 1 ) 皇皇j m 玎而2 ( ，2 + 1 ) 皇暑_ ，坍盯一4 ，歪2 f 历掣盈o 户o f = l 掣j 。 j = o 信l 掣j 扛o 综上可得：0 白= 2 ( 户+ 1 ) 薹；笺驴- f 一力劬+ 盖量_ ，g 胡+ ( 2 产+ 4 ，_ 2 ) 盖善。_ ，的 。j ：| o 净卜l j = o i - 挣、 j 2 国i j + l 单 一( 4 r 2 4 ，) 三( f + 1 ) g 件l ， f = o ：2 ( r 2 + 1 ) 【差宅。一f 一力g 胡+ ( 4 户