（应用数学专业论文）图的κ限制边连通度的存在性及上界.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名：弓长帚欠瞬 导师签字： 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权i 堑可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：弦每次声筝 签字日期2 。s 年辱月2 ) 日 导9 醛氧为苗 签字日期：2 0 0 吝年年月2 山东师范大学硕士学位论文 图的七限制边连通度的存在性及上界 中文摘要 图论的研究始于2 0 0 多年前关于图论的第一篇论文是1 7 3 6 年e u l e r 发表的他 用图的方法解决了哥尼斯堡七桥问题二十世纪三十年代以来图论在科学界异 军突起，活跃非凡图论中有很多著名的问题，如哈密顿问题，四色问题，中国邮递 员问题等，并且应用图论来解决化学，生物学，信息和计算机科学等学科问题已显 示出极大的优越性同时，图论在工程技术领域及社会科学中也有着广泛的应用 它作为离散数学的一个重要分支，受到了各方面的普遍重视 条件边连通度是分析和刻画图的有力工具有大量的问题可以归结为图的条 件边连通度问题，所以这方面是图论的热点研究领域目前，互联网络已经与人们 的工作、日常生活等方面息息相关网络的可靠性和容错性是近年来国内外研究 的热点问题我们知道连通度是反映图的连通性质的一个重要参数而要精确地 刻画图的连通性质经典连通度存在着不足：首先连通度相同的图可靠度可能不 同其次不能区分删掉k 个割断点或a 条割断边得到的图的不同类型即未考虑对 网络的伤害程度第三，默认图的任何子集中所有元素能潜在地同时失效为克服 以上不足自然要将经典连通度的概念加以推广。自1 9 8 3 年h a r a r v 【3 】提出条件连 通度的概念以来经过二十来年的发展条件连通度所涉及的内容日益丰富和具 体，象限制边连通度等 设计和分析大规模网络的可靠性和容错性时通常包括某些类型的图模型 针对不同的模型都有诸多相关理论问题需要研究其中一个重要模型是这样的 网络g ：其节点不会失效，但节点问的连线可能相互独立地以等概率p 失效贝0 g 不 连通的概率为尸( g ，p ) = g 矿( 1 一p ) 卜 ，其中e 为g 的边数g 表示基数为 的边 割的数目则图g 的可靠度为l p ( g 确定p ( g ，p ) 的问题在可靠度的研究中受 到了广泛关注但p r o v a n 和b a l l 【4 已经证明，对一般图g ，尸( g p ) 的计算是n p - h a r d 的 为此，e s f a h a n i a n 和h a l 【i m i 【5 j 提出了限制边连通度的概念本文在前人工作的基础 上，继续研究限制边连通度的相关性质 在第一章中，我们主要介绍了本文的研究背景以及已有的一些结果，以及文 章中所涉及的一些概念和术语符号 g = ( ve ) 是连通图，s 是g 的边子集，若g s 不连通且g s 的每个分支至 1 山东师范大学硕士学位论文 2 少有七个点则s 称为g 的七限制边割，记为月七一边割g 的足一限制边割的最小基数 称为g 的七一限制边连通度记为入k ( g ) 或九( g ) = m i n a ( x ) ：ixi = 七，g 】连 通 ，这里g x 表示点集x 在g 中的导出子图 在第二章中，对直径d ( g ) = 2 的图的七限制边连通度进行了研究，得到了下面 的结果： 定理2 2 设g 是一个直径为2 的图则或者对于任意的忌l 掣j ，儿( g ) 存 在：或者g 恰好含有一个饱和点它是割点 称相邻于所有其它顶点的顶点为图的饱和点 在第三章的第一节中，具体讨论了关于3 一正则图限制边连通度的存在性，得到 了下面的结果： 定理3 1 3 设g 是一个阶数至少是1 2 的连通3 正则图，若g g + ，则a 6 ( g ) 存在 在第二节中，研究了正则图七限制边连通度的上界问题，证明了下面的结果： 定理3 2 6 设g 是一个正则连通图，若入7 ( g ) 存在，则入7 ( g ) f 7 ( g ) 关键词：正则图：条件边连通度：存在性；上界 分类号： 0 1 5 7 5 e x i s t e n c ea n db o u n do n 尾r e s t r i c t e de d g e c o n n e c t i v i t yo fg r a p h s a b s t r a c t s t u d yo fg r 印ht h e o r ys t a r t e do v e rt w 0h u n d r e d sy e a r sa g o t h ee a r l i e s tk n o w n p a p e ri sd u et oe u l e r ( 17 3 6 ) a b o u tt h es e v e nb r i d g e so fk 6 n i g s b e r g s i n c e1 9 3 0 s ： g r a p ht h e o r yh a sd e v e l o p e dv e u f a s ta n dn u m e r o u sr e s u l t so ng r a p ht h e o d ，s p r u n g f o r t h t h e r ea r em a n i c ea n de e l e b r a t e dp r o b l e m si ng r 印ht h e o r 、s l l c ha sh a m i l - t o n i a np r o b l e m ，f o u r - c o l o rp r o b l e m ，c 1 1 i n e s ep o s t m a np r o b l e m je t c m o r e o 、，e r ，g r a p h t h e o r yi sw i d e l y 印p l i e di nc h e m i s t w ：c o m p u t e rs c i e n c e ：s o c i a ls c i e n c e b i 0 1 0 鼬，a n d o t h e rd i s c i p l i n e s a sas u b f i e l di nd i s c r e t em a t h e m a t i c s g r a p ht h e o r yh a sa t t r a c t e d m u c ha t t e n t i o nf t o ma up e r s p e c t i v e s r e s t r i c t e de d g ec o n n e c t i 啊妙i sat o o lw h i c hs t u d yg r a p h s i nf a c t ，m a n yp r a c t i c a lp r o b l e m sc a nb ea t t r i b u t e dt ot h ep r o b l e mo fr e s t r i c t e d e d g ec o n n e c t i v i t 、r t b e r e f o r e ，t h er e s e a r c ha b o u tt h e mi sv e h a c t i v e i np r e s e n t ，n e t w d r k sh a ，v ec l o s e l v r e l a t i o l l s l l i pw i t hv a r i o u sa s p e c t so fp e o p l e s u c ha sw o r k ? e 玎t e r t a i n m e n ta n d1 i f e t h e r e s e a r c ha b o u tt h e r e l i a b i l j t ya n dt o l e r a b i l i t yo fn e t w o r k si sv e n ta c t i v e w ek n o wt h a t c o n n e c t l v l t yp l a y sa nl m p o r t a mr o l ei nt h ec o n n e c t i v i t 、o fg r a p h b u tt h ec l a s s i c a l c o n c e p to 士t h ec o n n e c t i v i t ) ，h a st h r e eo b 、j o u sd e 6 c i e n c i e s f i r s t e v e nt ，of a p h s 飘呕t h t h es a m ec o n n e c t i 订t ym b ec o n s i d e r e dt oh a 、，ed i 矗e r e n tr e l i a b i l i t v s e c o n d l 、，t h e v d on o td i 娲r e n t i a t eb e t w e e nt h ed i 髓r e n t 心p e so fd i s n n e c t e dg r a p h sw h i c hr e s u l t n o n lr e m o v l n gk ( 1 i s c o n n e c t i n gv e r t i c e so r 入d i s c o n n e c t i n ge d g e s t h i r d l v t h es h o r t c o m i n go fu s i i 培t h e ma sm e a s u r e s0 ff a u l tt o l e r a n c ei st h a ti t i st a c j t l va s s u m e d t h a ta 1 1e l e m e n t si na n ys u b s e to fgc a np o t e n t i a l l yf a i la tt h et i m e c o n s e q u e n t l v ，t o c o m p e n s a t ef o rt h e s es h o r t c o m i n g s i tw o u l ds e e mn a t u r a lt og e n e r a l j z et h en o t i o n o fc l a s s i c a lc o n n e c t i v i t y s i n c e 胃口r n r 秒 3 】p r o p o s e dt h ec o n c e p to fc o n d i t i o n a lc o n n e c t i v 时i n1 9 8 3 ，a 丹e rs e v e r a ld e c a d e so fd e v e l o p m e n t t h ec o n t e n t si nc o n d i t i o n a l c o n n e c t i v i t yb e c o m em o r er i c ha n ds p e c i f i c t h ed e s j g l la n da n a l y s i so fr e l i a b l el a r g e - s c a l en e t w o r l ( st y p i c a l l yi n v o i v es o m e t y p eo fg r a p ht h e o r e t i cm o d l e t h e r ea r ea 面e t yo ft h e o r e t i c a lp r o b l e m st h a ta r i s e d e p e n d i n go nt h ee x a c tn e t w 0 北r e l i a b i l i t ym o d e lt h a ti su s e d o n ei m p o r t a n tm o d e l i san e t w o r ko fs u c ha l s ：ag r 印hg t o g e t h e r 而t hap r o b a b i h t yo ff a i l u r epa s s o c i a t e dw i t he a c he d g e w 色a s s u m e dt h a tt h ee d g ef a i l u r ep r o b a b i l i t i e sa r ee q u a la i l d 3 山东师范大学硕士学位论文 4 i n d e p e n d e n t ：i ti sa l s oa s s u m e dt h a tt h en o d e sd on o tf a i l t h e nt h ep r o b a b i i i t yt h a t gi sd i s c o n n e c t e dc a nb ee x p r e s s e da sp ( g ，p ) = c k p ( 1 一p ) 。一 、 h e r eei st h e t o t a ln u m b e ro fe d g e si ng ：gi st h en u m b e ro fe d g ec u t so fs i z e t h e r e f o r e t h e r e l i a b i l i t yo fg i s1 一尸( g ，p ) t h ep r o b l e m so fd e t e r m e n t 尸( g ，p ) f o rg i v e ng a n d ph a er e c e i v e dc o n s i d e r a b l ea t t e n t i o ni nt h er e i i a b i l i t y1 i t e r a t u r e h o w e v e r ，p r o u e n a n db n f z1 4 jh a v es h o w nt h a tt h ec a l c u l a t i o no fp ( g ，p ) f o ra na r b i t r a r yg r a p hg b e l o n g st ot h ec l a s so fc o m p u t a t i o n a u yi n t r a c t a l b l ep r o b l e m sk n r na sn p h a r d 1 b s o l v et h i sp r o b l e m ，e 5 ，n o 礼i o na n d 日。惫i 7 n i 【5 j p r o p o s e dt h ec o n c e p to fr e s t r i c t e d c o n n e c t i v i t y i nt h i sp a p e r ，伦m a i n l yc o n t i n u et od i s c u s st h er e l a t e dp r o p e r t i e so f r e s t r i c t e dc o n n e c t i v i t ) ro nt h eb a s i so fp r e v i o u sw o r k i nt h e 丘r s tc h a p t e r ，w eg i v eab r i e fi n t r o d u c t i o na b o u tt h eb a s i cc o n c e p t s ， t e r m i n o l o 舀e sa n ds y m b o l sw h i c hw i l lb eu s e di nt h i sp a p e r i nt h em e a n t i m e ，w e a l s og i v es o m er e l a t e dr e s e f 玎c hb a c k g r o u n d sa n ds o m ek n o w nr e s u l t s i nt h es e c o n d c h 印t e r ，w em a i n l ys t u d yt h e “r e s t r i c t e de d g ee o n n e c t i v i t yo fg r 印h s ( d ( g ) = 2 ) a n d o b t a i nt h er e s u l ta sf o u 弧r s ： t h e o r e m2 2l e tgb eag r 印h ( d ( g ) = 2 ) ，t h e na r b i t r a r y 忌l 华j ，入七( g ) e ) ( i s t 0 rt h eg r 印hj u s tc o n t a i nas a t u r a t i o nv e r t e xa n di “st h ec u tv e r t e x i ns e c t i o nio ft h et h i r dc h a p t e r ，w em a i n l ys t u d yt h ee 妇s t e n c ea n db o u n do n r e s t r i c t e de d g ec o n n e c t i 、，i t yo f 孓r e g u l a rg r a p h sa n d 酉v et h ef o l l o w i n gr e s u l t s ： t h e o r e m 3 1 3l e tgb ea3 - r e g u l a rc o n n e c t e dg r a p ho fo r d e ra t1 e a s t1 2 ，i f gi sn o ta6 - f l o w _ e r ，t h e n 入6 ( g ) e x i s t i ns e c t i o ni i w em a i n l ys t u d yt h ee 妇s t e n c ea n db o u n do nr e s t r j c t e de d g e c o n n e c t i v i t yo f 后一r e g u l a rg r a p h sa n do b t a i nt h er e s u l ta u sf o l l a w s ： t h e o r e m3 2 6l e tgb ea “r e g u l 盯c o n n e c t e dg r a p ho fo r d e ra tl e a s t1 4 w i t h 南2 i fgc o n t a i n s7 - r e s t r i c t e de d g ec u t ，t h e nk ( g ) 7 ( g ) k e y w o r d s ：r e g u l a rg r a p h ；r e s t r i c t e de d g ec o n n e c t i v i t y ；e x i s t e n c e ；b o u n d c l a s s i f i c a t i o n ：0 1 5 7 5 山东师范大学硕士学位论文 第一章预备知识 1 1 研究背景及已有结果 众所周知信息时代的到来促使互联网络迅猛发展网络已与人们的生活以及 各行各业息息相关，网络的可靠性和容错性是近年来国内外的研究热点大型互 联网络的拓扑结构通常用某些图模型来刻画，其中一个重要模型是这样的图g = ( 矿e ) ：其节点不会失效，但节点间的连线可能相互独立地以等概率p 失效若设g 的 边数为e 令g 表示基数为 的边割的数目，则g 不连通的概率为： p ( g ，p ) = 瓯p ( 1 一p ) m h = 1 对任意图g 称函数尸( g p ) 为g 的不可靠度多项式，则图g 的可靠度为1 一j p ( g p ) 显然p ( g p ) 越小网络越可靠，但p r o v a n 和b a l l 【4 】证明了：对一般图p ( g p ) 的计算是 n p h a r d 的 本文中我们考虑有限简单图用q ( n ：e ) 表示九个顶点和e 条边的图的集合我们 知道，当p 充分小时，为在q ( n ：e ) 中最小化尸( g ，p ) 边连通度入( g ) 起重要作用事实 上b a u e re ta l f 6 】已经证明对g l ，g 2 q ( n e ) ，如果a ( g 1 ) 入( g 2 ) ，那么，当p 充分 小时p ( g 1 p ) 入2 ( g 2 ) ，则当p 充分小时，p ( g 1 ，p ) 七2 + 1 ，则入七( g ) 颤( g ) z z h a n g 和j j y u a n 【1 6 证明了： 定理1 8 设g 是阶至少为2 ( 6 ( g ) + 1 ) 的连通图若g 不同构于g 麓 f ，= 6 ( g ) ，则 对任意的七6 ( g ) + 1 儿( g ) 存在，且k ( g ) & ( g ) 其中g 麓。是如下构造的图：令g l ，g 2 g m 均为完全图k ，添加一个新点u ，使 得u 与v ( g 。) ( 1 i m ) 的每个顶点相邻，所得新图即为g p 李建利和王世英 2 ( ) 】证明了： 定理1 9 设g 是一个礼阶连通图若d ( g ) = 2 ，且最大度n 一2 ，则对于任意 的七【号j g 存在吼一边割 高敬振和张淑芹例证明了： 定理1 1 0 设g 是连通，阶至少为2 七的( 奄一2 ) 一正则图( 七5 ) ，则g 的七一限制边 连通度k ( g ) 存在当且仅当g 不属于g ；一2 其中阶至少为2 七，( 詹一2 ) 一正则图( 七5 ) ，包含割点6 使得删掉6 点后每个分支 的阶为尼一1 的图类记为g ：一2 然而要设计并分析大规模的可靠网络，我们自然首先要确定出使得七一限制边 连通度存在应满足的图结构这也是一个前提条件进而，为使得网络的可靠性尽 可能的大，即为了最大化扎( g ) ，我们需要找到a 七( g ) 的上界，并确定出其上界是否 可达即研究入( g ) 的最优性问题 基于以上研究背景，本文选择七限制边连通度的相关性质，即后限制边连通度 的存在性、上界作为研究的内容，主要沿着推广已有结论和探索新结果两个思路 进行研究 山东师范大学硕士学位论文 1 2符号概念介绍 本文仅考虑有限无向简单图所使用的记号和术语约定如下其中未加说 明的部分将在必要时予以阐述或请参照文献 1 设g = ( ve ) 是一个图v ( g ) ，e ( g ) 分别表示g 的顶点集和边集用蚓表示集 合s 中元素的个数g 的顶点的个数称为g 的阶，记为f y ( g ) l 或i g | - 专用扎表示g 的 阶 若mz y ，e = ? ，e ，则说 和t ，( 在g 中) 相邻，又说c 与2 t 相关联，也说e 饱和乱或 说“为e 所饱和设s 为g 的一个边子集，s ( 让) 表示s 中与u 相关联的边所成的边子集 当l s ( 乱) i = 1 ( 或2 ) 时，称u 是s 单饱和的( 或双饱和的) 如果对每一个乱xcy ，都 有 s ( u ) f 1 ，则称s 饱和x g 中最短圈的长称为g 的同长，记为9 ( g ) g 中最长圈的长称为g 的周长，记为 c ( g ) 设乱u y xcy ，将d ( 仳x ) = m i n d ( 札秒) ：u x ) 称为u 到x 的距 离把d = d ( g ) = m n z d ( u u ) ：( 儿_ j y 1 7 叫做g 的直径g 的边连通度记 为入( g ) 9 山东师范大学硕士学位论文 1 0 第二章直径为2 的图的后限制边连通度 风边割在通信网络的可靠性分析起了很大的作用，并引起了强烈的关注，例 如文献【1 8 和【1 9 对于一般图而言，目前只解决了七4 的瓜一边割的存在性问题r 膏边割的存 在性的研究有困难人们转而研究一些有限制图类的玩边割的存在性王世英等 人给出了直径为2 的图的r 七一边割存在的一个充分条件 定理2 1 ( 2 0 】设g 是一个n 阶连通图若d ( g ) = 2 ，且最大度n 一2 ，则对于任 意的崩l 詈j ，g 存在见一边割 在此基础上，我们把定理2 1 的条件进行减弱得到了下面的结果称相邻于所 有其它顶点的顶点为图的饱和点 定理2 2 设g 是一个直径为2 的图：则或者对于任意的七l 竽j ，九( g ) 存 在：或者g 恰好含有一个饱和点它是割点 证明我们对七用数学归纳法 当七= 1 时凡边割就是一般意义上的边割，这样的边割是存在的 图g 的阶记为礼假设对于某个尼 七，i y i 七，则s 就是一个凰+ l 一边割，得证 下面考虑l x l = 尼或i y i = 后的情况? 不失一般性，设i x i = 尼因为七+ 1 l 号j ，l x i + i y i = 礼，所以i y i 尼+ 2 记k 为g 2 中与s 相关联的所有顶点的集合，h = y 一，显然有y 谚 山东师范火学硕士学位论文 若中存在一点珈? 使得g 2 一蜘还连通：由k 的定义可知珈与s 中某条边关联故 珈与x 中的某点如相邻结合这和g l 的连通性，可知g u 珈) 】是连通的记s = u 珈) ，y 珈】那么s 7 就是g 的一个忍+ 1 - 边割 下设k 中的每个点都是g 2 的割点m d 否则设丁为g 2 的支撑树，珈为丁的悬 挂点，则珈不是g 2 的割点矛盾 若存在玑m 不邻于蜘k ，设g 2 一鼽的分支为g 2 1 g 2 2 ，g 2 。( 5 2 ) 不妨设1 y ( g 2 1 ) ，取沈y ( g 2 2 ) 因为y l 耽e ( g ) d ( g ) = 2 ，所以在g 中存 在路秒1 z 可2 又因为耖1 隹k 所以z = 珈，矛盾 所以k 中的点与k 中的点间均有边相连又因为k 中的点均为g 2 的割点所以 = 珈) 又因为对于任意z x g 中存在路y l 蜘z ，所以x 中的点与珈均有边相连所以g 含 唯一饱和点珈，且珈是割点 定理2 2 证明完毕 1 1 山东师范大学硕士学位论文 1 2 第三章正则图后限制边连通度的存在性及上界 这一章主要研究正则图七限制边连通度的存在性和上界问题第一节我们研 究6 - 限制边连通度的存在性问题，给出了3 正则图六阶限制边连通度存在的条 件第二节我们给出了正则图7 - 阶限制边连通度的上界 5 3 1 3 正则6 限制边连通度的存在性 n g 7 】已证明了对阶至少为8 的连通正则图，若入4 ( g ) 存在，则a 4 ( g ) 矗( g ) 0 u 【2 3 利用凡一边割和4 一阶限制边连通度的性质，确定了不可靠多项式的前a 4 个 系数，并证明了对阶至少为1 0 的正则图g ，若入5 ( g ) 存在，则a 5 ( g ) 5 ( g ) 高敬振，张 淑芹【2 6 证明了阶至少为2 七的( 后一2 ) 正则图( 尼4 ) ：儿( g ) 存在当且仅当g 不属 于嚷- 2 这里：我们将阶至少为2 七( 惫一2 ) 一正则( 七5 ) ，包含割点6 使得删掉6 点后每个分 支的阶为七一l 的图类记为g ；一2 在此基础上，本节将研究3 - 正则图a 6 ( g ) 的存在性 引理3 1 1 f 1 3 对连通图g ，k ( g ) 存在当且仅当g 存在两个阶至少为南的点不 交的连通子图 引理3 1 2 设g 是阶至少为2 七的连通图，若g 是2 一连通的，则儿( g ) 存在 将图1 记为9 定理3 1 3 设g 是一个阶数至少是1 2 的连通3 - 正则图，若g g ，则入6 ( g ) 存在 证明若g 是2 一连通的，则由引理3 1 2 知，入6 ( g ) 存在 以下设g 不是2 一连通的，则g 含有割点，无妨设叫为g 的一个割点因为g 是3 正 则图，有d g ( 叫) = 3 ，所以g 一叫恰有2 个或3 个分支 山东师范人学硕士学位论文 图1g + ( 订) 若g 一例恰有3 个分支，不妨设为日，2 风由于g 是3 正则的故g u ，的每 个分支的外度均为1 ，从而每个分支的阶至少为5 如果3 个分支的阶1 日l l = l 凰i = i 风i = 5 这时g = 伊，其入6 显然不存在如果这三个分支中有一个其阶不小于6 ，比 如1 日1 i 6 ，则日1 与g 一日1 是两个阶至少为6 的点不交的连通子图，由引理3 1 1 知 入6 ( g ) 存在 ( 6 ) 若g 一”恰有2 个分支不妨设为日。，凰g u ，中必有一个分支的外度为2 ：不 妨设为日l ，另一个外度为1 的分支为圩z 同样根据g 的3 正则性得到日1 的阶至少为4 且1 日1 l 5 当1 日1 = 4 时因为i g f 1 2 所以i h 2 7 此时存在两个点不交的阶至 少为6 的子图，由引理3 1 1 知a 6 存在：当l 1 l 6 时令x = u ，) u 凰，则 x 日1 为一 个忍一边割即入6 存在 定理3 1 3 证明完毕 1 3 山东师范人学硕士学位论文 1 4 3 2正则图7 邛艮制边连通度的上界 关于图的限制边连通度的上界问题1 9 8 8 年，e s f a h a n i a n 和h a k i m i 证明了下面 的结果： 定理3 2 1 5 】设g 为阶至少为4 的连通图? 若g 不同构于k l ，3 ，则a 2 ( g ) ( g ) 1 9 8 6 年b o e s c h 和w a n g 给出了正则图a 3 ( g ) 的上界： 定理3 2 2 【2 5 】令g 是阶至少为6 的七正则图若入3 ( g ) 存在：则入3 ( g ) 3 ( g ) 2 0 0 2 年、a n g 【7 】给出了正则图入4 ( g ) 的上界： 定理3 2 3 【7 】令g 是正则图若( g ) 存在，则儿( g ) ( g ) 2 0 0 3 年欧见平，张福基教授给出了正则图a 5 ( g ) 的上界： 定理3 2 4 【1 5 】 令g 是一个正则图若k ( g ) 存在，则a 5 ( g ) 5 ( g ) 张淑芹给出了正则图久6 ( g ) 的上界： 定理3 2 5 2 4 】 令g 是一个正则图若a 6 ( g ) 存在，则a 6 ( g ) 6 ( g ) 本节我们给出正则图a 7 ( g ) 的上界： 定理3 2 6 设g 是一个正则连通图若a 7 ( g ) 存在，则入7 ( g ) 7 ( g ) 证明设g 的正则度为七当后= 2 时g 为2 正则图显然g 是阶至少为1 4 的圈此 时入7 ( g ) = 2 ，7 ( g ) = 2 ，结论显然成立以下不妨设七23 由定理1 7 和定理1 8 ，不妨 设尼5 ，9 ( g ) 4 令f 是g 的7 阶连通点导出子图，使得a ( f ) = 7 ( g ) 若g f 中含有阶至少为7 的 分支c ，则s = 【c ，g c 显然为一个r 7 一边割，显然入7 ( g ) 俐f 7 ( g ) 以下不妨 设g f 的分支的阶至多为6 我们先来证明：e ( f ) 7 设鼠为g f 的分支( z = 1 ，2 ，p ) ，则p 2 由a ( f ) 的 山东师范大学硕士学位论文 极小性我们得到：e ( 日i ) se ( f ) 一( 7 一 日t 1 ) 因此 p 7 尼一2 e ( f ) = a ( f ) = a ( 日。)、，、 ，- 一 o ， = ( 骨一2 ) ( i gj 一7 ) 一2 p e ( f ) + 1 4 p 7 ( 七一2 ) 一2 p e ( f ) + 1 4 p( 1 ) 所以有7 尼一2 e ( f ) 7 ( 角一2 ) 一2 p e ( f ) + 1 4 p 即有( 2 p 一2 ) e ( f ) 1 4 p 1 4 ，所 以e ( f ) 7 情形1f 中存在一度点 若f 中存在一度点，不妨记为u ，则e ( f ) 1 6 若有一个点u g j f l 使得：用i 3 ，则h = g f ( 豇) up ) 也是一个阶为7 的点导出子图，且h 的边数e ( 胃) e ( f ) ，这 与e ( f ) 的极大性矛盾所以对于g f 中的任意一点u ，都有，f 】f 2 成立又因 为七3 所以g f 无孤立点从而g f 的每个分支的最小度至少为矗一2 ，阶至 少为骨一1 由( 1 ) 式我们推得 7 矗一2 e ( f ) ( 膏一2 ) ( | gj 一7 ) 一2 p e ( f ) + 1 4 p 所以 ( 2 p 一2 ) e ( f ) ( 七一2 ) ( i g l 一7 ) + 1 4 p 一7 后 p ( 后一1 ) ( 七一2 ) + 1 4 p 一7 七( 2 ) 情形1 1 若詹= 3 ，则由g 的3 一正则性知e ( f ) 等等= 8 一南 1 0 p 4 时，e ( j f l ) 8 又因为d f ( 札) = 1 ，所以e ( f ) 9 a ( f ) = 7 膏一2 e ( f ) 2 1 1 6 = 5 ，而p 4 ，且a ( 鼠) 1 ，所以a ( f ) 4 ，故a ( f ) = 4 或a ( 尸) = 5 又因 为a ( f ) 不可能小于等于4 ，所以a ( f ) = 5 ，此时e ( f ) = 8 ，p 4 又因为a ( 凰) l ，所 以4 p 5 当p = 4 时即分支个数为4 个时，必定有3 个分支的外度为1 ，剩下一 个的外度为2 ，又每个分支的阶至少为2 ，所以每个分支的阶可能为2 ，3 ，4 ，5 ，6 ，又根 h一一f 川 p r ：，、l 爿睦渊 “ 一 2 ， 爿一 州 h 一 g p 渊圳 i i 一 山东师范大学硕士学位论文 1 6 据3 _ 正则性只能是边数为7 的5 阶分支的外度为1 ，但此时存在边数大于e ( f ) 的7 阶 连通子图，与e ( f ) 的极大性矛盾当p = 5 时同理可证 2 0 p = 3 时e ( f ) 7 a ( f ) = 7 后一2 e ( f ) 2 1 一1 4 = 7 若e ( f ) = 7 ，则a ( f ) = 7 又p = 3 所以各分支的外度分配可能为：( 3 2 2 ) ：( 4 ，2 ，1 ) 或( 5 ，1 ，1 ) 由g 的3 一正则性知，必存在边数大于e ( f ) 的7 阶连通子图，与e ( f ) 的极大 性矛盾 若e ( f ) = 8 ，则a ( f ) = 5 各分支的外度分配可能为：( 3 ，1 ，1 ) 或( 2 2 ，1 ) 此时也 存在边数大于e ( f ) 的7 阶连通子图与e ( 尸) 的极大性矛盾 若e ( f ) = 9 ，则a ( f ) = 3 各分支的外度只能为：( 1 ，1 ，1 ) 这时a 7 ( g ) = 1 矗( g ) = 3 从而a ? ( g ) s 7 ( g ) 成立 3 0 p = 2 时，由断言1 知e ( f ) 7 若e ( 尸) = 7 ，则a ( f ) = 7 此时分支的外度分配可能为：( 1 ，6 ) ，( 2 ，5 ) ，( 3 ：4 ) 由e ( f ) 的极大性可知与日i 关联的f 中的点互不相同且它们之间不相邻但此时必存在边 数大于e ( f ) 的7 阶连通子图：矛盾 若e ( f ) = 8 ，则a ( f ) = 7 七一2 e ( f ) = 2 1 1 6 = 5 此时分支的外度分配可能 为：( 1 ，4 ) 或( 2 3 ) ，此时存在r 7 一边割，并且满足入7 ( g ) 7 ( g ) 若e ( f ) = 9 ，则a ( f ) = 3 ，而p = 2 ，g 是3 正则此时两分支的外度只能为( 1 ，2 ) ，此 时兄7 一边割也存在且有a 7 ( g ) = 2 ，7 ( g ) = 3 ，从而入7 ( g ) 7 ( g ) 成立 情形1 2 若露= 4 ，则由g 的缸正则性知e ( f ) 1 2 由( 2 ) 式可得： ( 2 p 一2 ) e ( f ) p ( 七一1 ) ( 七一2 ) + 1 4 p 一7 七 所以 e ( 耻筹州一者 ( 3 ) 1 0 p 6 时，e ( f ) 1 0 此时各分支的阶大于等于七一1 = 3 所以各分支的阶 山东师范大学硕士学位论文 为3 ，4 ，5 或6 又因为a ( f ) = 7 七一2 e ( f ) 2 8 2 0 = 8 ，而由g 的垂正则性知，a ( 鼠) 2 p 2 ，所以a ( f ) = a ( 凰) 6 2 = 1 2 矛盾 1 = l 2 0 p = 5 时e ( f ) 9 a ( f ) = 7 七一2 e ( 尸) 1 0 。由g 的4 - 正则性知，此时各分支 p 的外度至少为2 ，又a ( f ) = a ( 日i ) 5 2 = l o 所以a ( f ) = 1 0 ，e ( f ) = 9 ，此时各 i = 1 分支均是外度为2 的5 阶或6 阶连通子图但此时都存在边数大于e ( f ) 的7 阶连通子 图矛盾 3 0 p = 4 时e ( f ) 9 a ( j f l ) = 7 七一2 e ( f ) 1 0 若e ( f ) = 9 ，则a ( f ) = 7 艮一2 e ( f ) = 1 0 此时各分支的外度分配为：( 4 2 ，2 ，2 ) ，但 此时存在边数大于e ( f ) 的7 阶连通子图：与e ( f ) 的极大性矛盾 若e ( f ) = 1 0 ，则a ( f ) = 7 岛一2 e ( f ) = 8 此时各分支的外度分配为：( 2 2 ，2 ，2 ) ，此 时也存在边数大于e ( f ) 的7 阶连通子图与e ( f ) 的极大性矛盾 若e ( f ) = 1 1 ，则a ( 尸) = 7 后一2 e ( f ) = 6 由g 的4 正则性知，此时各分支的外度 p 至少为2 从而a ( 尸) = a ( 凰) 4 2 = 8 得到矛盾 1 = 1 若e ( f ) = 1 2 ，则a ( f ) = 7 七一2 e ( f ) = 4 ，同e ( f ) = 1 1 一样证明得出矛盾 4 0 p = 3 时，e ( f ) 8 a ( f ) = 7 七一2 e ( f ) 1 2 若e ( f ) = 8 ，则a ( 尸) = 7 詹一2 p ( f ) = 1 2 此时各分支的外度分配可能为：( 2 4 6 ) ( 2 ，2 ：8 ) 或( 4 4 4 ) ，但此时三种分配方式都存在边数大于e ( 尸) 的7 阶连通子图：与 e ( j f l ) 的极大性矛盾 若e ( j f l ) = 9 ，则a ( f ) = 7 七一2 e ( f ) = 1 0 此时各分支的外度分配可能为：( 2 ，2 ：6 ) 或( 2 ，4 ，4 ) ，但此时的2 种分配方式都存在边数大于e ( j f l ) 的7 阶连通子图，与e ( f ) 的极 大性矛盾 若e ( f ) = 1 0 ，则a ( f ) = 7 七一2 e ( f ) = 8 此时各分的外度分配只能为：( 2 ，4 ，2 ) ，同 上得出矛盾 1 7 山东师范大学硕士学位论文 1 8 若e ( f ) = 1 1 ，则a ( f ) = 7 七一2 e ( f ) = 6 此时各分支的外度分配只能为：( 2 2 2 ) 但此时存在边数大于e ( f ) 的7 阶连通子图与e ( f ) 的极大性矛盾 若e ( f ) = 1 2 则a ( f ) = 7 七一2 e ( f ) = 4 由g 的4 - 正则性知，a ( 凰) 2 ，从 而a ( f ) = a ( 凰) 3 2 = 6 矛盾 2 = l 5 0 p = 2 时，由( 3 ) 式得e ( f )