（应用数学专业论文）图的k限制边连通度的若干性质.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得 ( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名：戳选嘶 聊箨摩吃洲乙 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权趁可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：妖淑彳 导师签字： 签字日期：2 0 0 岔年午月o 日 签字日期：2 0 02 为巩 年牟月o 日 山东师范大学硕士学位论文 图的足限制边连通度的若干性质 张淑芹 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 目前，互联网络已经与人们的工作，日常生活等方面息息相关网络的可靠性和 容错陛是近年来国内外研究的热点问题我们知道，边连通度是反映图的连通性质 的一个重要参数而要精确地刻画图的连通性质，经典边连通度存在着不足之处： 首先，边连通度相同的图可靠度可能不同其次，不能区分删掉k 个割断点或a 条 割断边得到的图的不同类型，即未考虑对网络的伤害程度第三，默认图的任何子 集中所有元素能潜在地同时失效为克服以上缺陷，自然要将经典边连通度的概念 加以推广自1 9 8 3 年日n r a r y 2 j 提出条件连通度的概念以来，经过约二十年的发 展，条件连通度所涉及的内容日益丰富和具体，包括超级连通度、过边连通度、限 制边连通度等 设计和分析大规模网络的可靠性和容错性时，通常包括某些类型的图模型针 对不同的模型，都有诸多相关理论问题需要研究其中一个重要模型是这样的网络 g ：假设其节点不会失效，但节点间的连线可能相互独立地以等概率，失效则g 不连通的概率为： p ( g p ) = ：c k p “f 1 一p ) 。一“ = l 其中p 为g 的边数，g 表示基数为而的边割的数目，则图g 的可靠度为1 一尸( g j p ) 确定p ( g ：p ) 的大小问题在可靠度的研究中受到了广泛关注但p 7 铡。钉和b o f f 3 已经证明，对一般图g 尸( g ，p ) 的计算是a 尸一 n r c 的为此，s ，n a m n n 和 日n 后i m 搏提出了限制边连通度的概念本文在前人工作的基础上，继续研究限制 边连通度的相关性质 在第一章中，我们主要介绍了本文的研究背景和已有的一些结果，以及文章中 所涉及的一些概念和术语符号 定义1 2 【7 令g = ( 扩e ) 是连通图，s 是g 的边子集，若g s 不连通且 g s 的每个分支至少有七个点，则s 称为g 的后限制边割，记为见边割 1 山东师范大学硕士学位论文 g 的“限制边割的最小基数称为g 的“限制边连通度，记为a 七( g ) 或“ 若入k ( g ) 存在，则称g 是k - 连通的 定义l 3 设x ：y 是g = ( 1 ，e ) 的顶点集i ，7 的两个不交的非空子集或g 的 两个不交的子图，g 的端点分别属于x 和y 的所有边构成的集合记作! x y 当 义= z ) 时，用江川代替f x y ：称a ( x ) = f 【x y x f 为天的外度 令瓢( g ) = m i n p f 义) ：l 义i = 七g ：x ：连通) 这里g ! 表示点集x 在g 中 的导出子图 设g 是入2 一连通的，将满足入2 ( g ) = 善2 ( g ) 的图称为入2 一最优图 在第二章中，我们具体讨论了正则图、2 一连通图的七一限制边连通度( 七6 ) 的存在性和上界问题，得到以下几个结果： 定理2 1 7 令g 是阶至少为1 0 的连通正则图，则入5 ( g ) 存在，且a 5 ( g ) 矗( g ) 定理2 2 2 设g 是阶至少为8 的2 一连通图，若g 不属于g 则a 4 ( g ) 存在， 且入4 ( g ) 矗( g ) 其中g 定义如下：设f 是边数至少为5 的4 阶连通图，令f 的顶点集为 f ) = n 6 c d ) 且设如( n ) = 如( c ) = 3 设g 1 g 2 是阶为2 或3 的连通子 图，在 n ：c ) 与g 。g 2 之间添加4 条边，使得口( 。分别与g 。g 2 相邻，得到的新 图构成g 定理2 3 1 令g 是连通的正则图若a 6 ( g ) 存在，则入6 ( g ) 三6 ( g ) 在第三章中，我们研究了( 七一2 ) - 正则图七限制边连通度的存在性，得到下 面的结果： 定理3 1 设g 是连通，阶至少为2 七的( 后一2 ) - 正则图，则g 的七一限制边 连通度入k ( g ) 存在当且仅当g 不属于g 一2 这里，我们将阶至少为2 七，( 詹一2 ) 正则( 七5 ) j 包含割点6 使得删掉6 点后 每个分支的阶为七一1 的图类记为g ；一2 在第四章中，我们研究了限制边连通度的最优性，证明了下面的结果： 定理4 2 设对n 阶图g 的任意一对不相邻的顶点z ，可都有d ( z ) + d ( y ) n 如果g 不是入2 一最优图，则g 同构于g + 其中g 定义如下：设g 是n 阶连通图若g 的顶点可剖分成两部分a 和b ， 记g 1 = g 4 j ，g 2 = g b 】，f g t i = 仃l ( i = l ，2 ) ， 5 ，= 4 ：b ：使得若“矿( g 1 ) ，r 1 ( g 2 ) ：d g 。( u ) = n 1 1 d g 2 ( u ) = n 2 1 且仳，r 都是s 单饱和点，则u ： 在g 中 2 山东师范大学硕士学位论文 不相邻记这样的图g r 为g 4 关键词：图；正则图；边连通度；骨一限制边连通度 分类号： 0 1 5 7 5 3 山东师范大学硕士学位论文 s o m er e s u l t so n 尼一r e s t r i c t e de d g ec o n n e c t i v i t y o fg r a p h s s h u q i nz h a n g s h a n d o n gn o r m a lu n i v e r s i t j 7 j i n a n s h a n d o n g 2 5 0 0 1 4 p e o p l e sr e p u b l i co fc h i n a a b s t r a c t i np r e s e n t ? n e t w o r k sh a v ec l o s e l yr e l a t i o n s h 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 n t e r t a i n m e n ta n dl i f e t h er e s e r c ha b o u t t h er e l i a b i l i t ) a n dt 0 1 e r a b i l i t yo fn e t w o r k si sv e r ) a e t i v e 、ek n o w t h a te d g ec o n n e c t i v i t ) p l a y sa ni m p o r t e n tr 0 1 ei nt h ec o n n e e t i 、r i t y o fg r a p h b u tt h ec l a s s i c a le o n c e p to ft h ee d g ec o n n e c t i v i t yh a st h r e e o b 、r i o u sd e 丘c i e n c i e s f i r s t l y e v e nt w og r a p h sw i t ht h es a m ec o n n e c t i v 。 i t ym a yb ec o n s i d e r e dt oh a v ed i f k r e n tr e l i a b i l i t y s e c o n d l y ，t h e ) d o n o td i 矗色r e n t i a t eb e t w e e nt h ed i 丘色r e n tt y p e so fd i s e o n n e c t e dg r a p h s w h i c hr e s u l tf r o mr e m o 、r i i l gkd i s ( ：o i l i l e c t i n gv e r t i c e so r 入d i s ( ：o n n e c t i i l ge d g e s t l l i r d l y ，t h es h o r t c o h l i n go fu s i n gt h e ma si n e a s u r e so ff a u l t t o l e r r a n c ei st h a ti ti st a c i t l ya s s u m e dt 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 订a tt h et i m e c o n s e q u e n t l 弘t oc o m p e n s a t e f 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 l i z et h en o t i o n o fc l a s s i e a le d g pc o n n e c t i v i t y s i n e e 日o r o r 秒【2 】p r o p o s e dt h ee o n e e p t 4 山东师范大学硕士学位论文 o fe o n d i t i o n a lc o n n e c t i 、r i t 、i n19 8 3 a f t e ra b o u tt w e n t 、，v e a r sd e v e l o p m e n t ，t h cc o n t e n t si ne o n d i t i o n a lc o n n e c t i v i t yb e e o m em o r er i c h a n ds p e c i 矗c i n c l u d i n gs u p e rc o n n e c t i v i t ) 7 c x t r ae d g cc o n n e c t i v i t y r e s t r i c t e de d g pe o n n e c t i 、r i t ) ，：a n ds oo n t h pd e s i g na n da n a l y s i so fr e l i a b l pl a r g p s c a l pn e t w o r k st ) r p i e a l l y i n 、7 0 l 、堆s o m et ) p e so fg r a p ht h e o r e t i cm o d l e t h e r ea r eav a r i e t ) o f t h e o r e t i c a lp r o b l e m st h a ta r i s ed e p e n d i n go nt h ee x a c tn e t w o r kr e l i a b i l i 母m o d l et h a ti su s e d o n ei m p o r t e n tm o d l ei san e t w o r ko fs u c h a s ：ag r a p hgt o g e t h e rw i t hap r o b a b i l i t ) o ff a i l u r epa s s o c i a t e dw i t h e a c he d g e v 沌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 l a n di 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 n t h ep r o b a b i l i t ) t h a tgi sd i s c o n n e c t e de a nb ee x p r e s s e da s _ 、， 尸( g p ) = ，o 。p ( 1 一p ) 8 一向 ，j = l w h e r eei st h et o t a ln u m b e ro fe d g e si ng g ji st h en u m b e ro fe d g e c u t so fs i z e 九t h e r e f o r e t h er e l i a b i l i t ) o fgi s1 一p ( g p ) t h ep r o b l e m s o fd e t e r m i n g 尸( g p ) f 6 rg i v e nga n dph a v 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 l i a b i l i t yl i t e r a t u r e h o w e v e r p r o t j e 饥a i l db 0 2 7 【3 h a v e s h o w nt h a tt h ec a l c u l a t i o i lo f 尸( g ：p ) f 6 ra na b i t r a r yg r a p hg b e l o i l g s t ot h ec l a s so fc o n l p u t a t i o n a l l yi n t r a c ta b l ep r o b l e m sk n o w na sn p h a r d t os 0 1 v et h i sp r o b l e m 旦s t 厂n 口礼i o 竹a n d 日n 七i m i 【5 i p r o p o s e dt h e c o n e e p to fr e s t r i c t e dc o n n e c t i 、，i t y i nt h i sp a p e r ：w em a i n l yc o n t i n u e t od i s c u s st h er e l a t e dp r o p e r t i e so fr e s t r i e t e dc o n n e c t i v i t yo nt h eb a s i s 5 o fp r e 、r i o u sw o r k 山东师范大学硕士学位论文 i nt h ef i i r s tc h a p t e r ：w pg i v eab r i e fi n t r o d u e t i o na b o u tt h pb a s i c e o n c e p t s t e r m i n 0 1 0 9 i e sa n ds ) 7 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 n t h em e a n t i m e w ea l s og i v es o m er e l a t e dr e s e a r c hb a c k g r o u n d sa n d s o m ek n o 、矿nr e s u l t s d e f i n i t i o n l 2 f a n 七r e s t r i c t e de d g ec u t o rs i m p l ) a nr 矗一e d g e c u t i sa ne d g ec u t 5 ro fac o n n e c t e dg r a p hgs u c ht h a te v e r yc o m p ( ) - n e n to fg sh a l so r d e ra tl e a s t 七t h es i z eo fam i n i m u mr 七一e d g ec u t o fg r a p hgi si t s 七一r e s t r i c t e de d g ec o n n e c t i v i t y ：d e n o t eb y 入砖( g ) o r s i m p l y 入膏i fg r a p hg c o n t a i n sr 矗一e d g ec u t s t h e ngi s 入七一c o n n e c t e d d e f l n i t i o n l 3f b rx 1 7 y ( g ) 1 e t x b et h es e to fe d g e s w i t ho n ee n di nxa n dt h co t h e re n di ny 7 s i m p l y z y a s x y d e n o t ea ( x ) = j x 、，一x l e t 甄( g ) = m i n a ( x ) ：lxi = 艮：g x i sc o n n e e t e d ) ：h e r eg x d e n o t e st h ps u b g r a p ho fgi n d u c e db ) x a 入2 一c o n n e c t e dg r a p hg i sc a l l e d 入2 一o p t i m a l ：i f 入2 ( g ) = 2 ( g ) i n t h es e c o n dc h a p t e r ：w em a i n l ys t u d yt h ee x i s t e n c ea n du p p e r b o u n do ft h e 七一r e s t r i c t e de d g ec o n n e c t i v i t y ( 七6 ) o fr e g u l a rg r a p h s a n d2 一c o n n e e t e dg r a p h sa n dg i v et h ef 6 l l o w i n gr e s u l t s ： t h e o r e m 2 1 7l e tgb ear e g u l a rc o n n e c t e dg r 印ho fo r d e ra t l e a s t1 0 t h e ngc o n t a i n s5 r e s t r i c t e de d g ec u t sa n d 入5 ( g )岛( g ) t h e o r e m 2 2 2i fgb ea2 一c o n n e c t e dg r a p hw i t ho r d e ra tl e a s t 8w h i c hi sn o ti na n yg ? t h e ngc o n t a i n s4 - r e s t r i c t e de d g ec u t sa n d 6 山东师范大学硕士学位论文 a 4 ( g ) 矗( g ) 、 h e r egi sd e 矗n e da sf 0 u o w s ：i ffi sac o n n e c te dg r a p hw i t h o r d e ro ff 6 u ra n de d g ea tl e a s tf i v e s u p p o s et h ev e r t e xs e to ffi s 1 【厂( f ) = 口6 c d ) a n dd f ( 口) = d f ( c ) = 3 l e tg 1 ：g 2a r et w o c o n n e c t e dg r 印h sw i t ho r d e ro ft w oo rt h e r e w ea d df 6 u ri n d e p e n d e n t e d g e sb e t w e e n o ：c ) a n dg 1 ：g 2t om a k e o c ) b ea d j a e e n tt og 1 ：g 2 r e s p e c t i v e l ) t h er e s u l t i n gg r a p hi sd e n o t e db yg t h e o r e m 2 3 1l e tgb ear e g u l a rc o i l n e c t e dg r a p ho fo r d e r a tl c a s t1 2 i fgc o n t a i n s6 - r e s t r i c t e de d g ec u t s t h e nk ( g ) 矗( g ) i nt h et h i r dc h a p t e r ：w em a i n l ) s t u d ) t h ee 婚s t e n c eo ft h e 膏 r e s t r i c t e de d g ec o n n e c t i 、7 i t ) o f ( 膏一2 ) 一r e g u l a rg r a p h sa n do b t a i nt h e r e s u l ta sf o l l o w s ： t h e o r e m3 1i fgi sa ( 天一2 ) - r e g u l a rc o n n e c t e dg r a p ho fo r d e r a t1 e a s t2 七t h e ng ( ：o n t a i l l s 天。- r e s t r i c t e de d g ec u t si fa i l do n l ) i fg d o e sn o t b e l o i l gt og ；一2 h e r e ? w ed e n o t et h es e to ft h i sk i n do fg r a p hga sg ；一2 ：gi sa ( 露一2 ) - r e g u l a re o n n e c t e dg r a p ho fo r d e ra tl e a s t2 詹w i t h 后5 a n d gc o n t a i n sac u t v e r t e x i fa n ) w h o s ed e l e t i o nd i s c o n n e c t sga n dt h e o r d e ro fe v e r yr e m a i n i n gc o m p o n e n ti s 惫一1 i nt h ef b u r t hc h a p t e r ? ，em a i n l ) rg i v ea c o r r e s p o n d i n gr e s u l to f t h eo p t i m a lo ft h er e s t r i c t e de d g ec o n n e c t i v i t y ： t h e o r e m4 2l e tgb ea g r a p ho fo r d e rn a n dd ( z ) + d ( y ) 九 7 f 6 re v c r yp a i ro fn o n a d j a c e n tv e r t i c e s 丁a n dy i fg i sn o t 入2 。o p t i m a l t h e ngi si s o m o r p h i c 乞og + l l e r eg + i sd e f i n e da sf 0 u o w s ：s u p p 【) s eg i sac o i m e c t e dg r a p h w i t ho r d e ro f 钉a n dt h ev e r t e xs e to fgc a nb ed i 、r i d e dt w op a r t sa a n db s i g ng 1 = g a g 2 = g b i g l = m ( i = 1 2 ) s = 4 b i f 乱1 l ( g 1 ) u y ( g 2 ) d g ，( u ) = ，1 1 d g 2 ( ) = 钆2 1a n du ua r e b o t hs i n 9 1 es a t u r a t e dv e r t i c e s t h e n “a n dua t en o ta d j a c e n ti ng 1 v v 宅 ，11 1p1、，1 d e n o t et h l sk l n do tg r a p nba su k e y w o r d s ：g r a p h ：r e g u l a rg r a p h ：e d g ec o n n e e t i v i t y ：孟。r e s t r - i c t e de d g ee o n n e c t i v i t y c 1 a s s i c a t i o n ：0 1 5 了5 8 山东师范大学硕士学位论文 第一章预备知识 众所周知，信息时代的到来促使互联网络迅猛发展，网络已与人们的生活以及 各行各业息息相关，网络的可靠性和容错l 生是近年来国内外的研究热点大型互联网 络的拓扑结构通常用某些图模型来刻画，其中一个重要模型是这样的图g = ( ve ) ： 其节点不会失效，但节点间的连线可能相互独立地以等概率p 失效若设g 的边 数为e 令g 表示边数为| 2 的边割的数目，则g 不连通的概率为： p ( g ：p ) = ，c 么p ，( 1 一p ) 。一“ h = 1 称函数尸( g p ) 为g 的不可靠度多项式，则图g 的可靠度为1 p ( g p ) 显然， p ( g p ) 越小，网络越可靠，但尸r d u n 竹和b 口f f f 3 证明了，对一般图，p ( g ：p ) 的 计算是p 一矗口r d 的 本文仅考虑有限无向简单图，所使用的记号和术语约定如下，其中未加说明的 部分将在必要时予以阐述或请参照文献 设g = f i ：e ) 是一个图， g 的顶点的个数称为g 的阶，记为旷( g ) i 或i g | 专用钉表示g 的阶 若u r 17 e = 删e 则说u 和z ? ( 在g 中) 相邻，又说e 与u 相关联，也 说e 饱和u 或说u 为e 所饱和设s 为g 的一个边子集，s ( u ) 表示s 中与“ 相关联的边所成的边子集当1 5 ( 仳j j = 1 f 或2 ) 时，称u 是s 单饱和的( 或双饱和 的) 如果对每一个z 义ci 都有 s ( 丁) 21 则称5 饱和x g 中最短圈的长称为g 的围长，记为g ( g ) g 中最长圈的长称为g 的周长， 记为c ( g ) 用q ( n e ) 表示九个顶点和e 条边的图的集合 我们知道，当p 充分小时，为在q ( 几e ) 中最小化尸( g ? p ) 边连通度a ( g ) 起重 要作用事实上，b 口u e re f 口f f 4 】已经证明，对g 1 g 2 q ( 礼e ) 如果入( g 1 ) a ( g 2 ) 那么当p 充分小时， 尸( g 1 p ) a 2 ( g 2 ) 则当p 充分小时，p ( g 1 ，p ) 七2 + 1 则 入( g ) ( g ) z z a n 9 和，】u n 竹f 2 0 ! 证明了； 定理1 8 设g 是阶至少为2 ( 巧( g ) 1 ) 的连通图若g 不同构于g i = j ( g ) 则对任意的矗s6 ( g ) + 1 入女( g ) 存在，且k ( g ) ( g ) 其中g 麓，是如下构造的图：令g 1 g 2 g 。均为完全图人r 。添加一个新点仉 使得“与y ( g ：) ( 1 i m ) 的每个顶点相邻，所得新图即为g 篇 然而要设计并分析大规模的可靠网络，我们自然首先要确定出使得七一限制边 连通度存在应满足的图结构，这也是一个前提条件进而，为使得网络的可靠性尽 可能的大，即为了最大化入女( g ) 我们需要找到k ( g ) 的上界，并确定出其上界是 否可达，即研究a 菇( g ) 的最优性问题 1 1 山东师范大学硕士学位论文 基于以上研究背景，本文选择“限制边连通度的相关性质，即“限制边联通 度的存在性，上界和最优性作为研究的内容，主要沿着推广已有结论和探索新结果 两个思路进行研究 1 2 山东师范大学硕士学位论文 第二章限制边连通度的存在性和上界 这一章主要研究当叁4 时，图的膏一限制边连通度的存在性和上界问题具 体给出了某些图类的4 ( 5 6 ) 一限制边连通度的存在性与上界的一些结论 5 2 1 正则图4 ( 5 ) 限制边连通度的存在性和上界 引理2 1 1 1 17 】令g 是阶至少为2 膏的连通图，则k ( g ) 存在当且仅当g 中 存在两个阶至少为七的点不交的连通子图 引理2 1 2 1 2 f ；】令g 是阶至少为2 膏的连通图，若周长c ( g ) 七+ 1 则儿( g ) 存在 引理2 1 31 6 令g 是连通的正则图，若a 4 ( g ) 存在，则a 4 ( g ) 4 ( g ) 命题2 1 4 若g 的最小度d f g ) 2 则g 包含长至少为6 ( g ) + 1 的圈 定理2 1 5 令g 是阶至少为8 的连通正则图，则a 4 ( g ) 存在，且a 4 ( g ) 矗f g ) 证明对g 的正则度膏的取值分情况讨论 情形1当膏3 时，因为g 的阶至少为8 且g 至少是3 - 正则的，显然g 不同构于g ；3 所以由定理1 8 推知，入4 ( g ) 存在，且入4 ( g ) 4 ( g ) 情形2 当膏= 2 时，g 是阶至少为8 的圈易知，九( g ) 存在，且入4 ( g ) = 已( g ) = 2 定理2 1 5 证毕 引理2 1 6 1 9 ：令g 是连通的正则图，若a 5 ( g ) 存在，则a 5 ( g ) “g ) 定理2 1 7 令g 是阶至少为1 0 的连通正则图，则入5 ( g ) 存在，且入5 ( g ) 已( g ) 证明对g 的正则度七的取值分情况讨论 情形l当后4 时，由g 的阶至少为1 0 且g 的正则度至少是4 易知， g 不同构于g 麓4 所以由定理1 8 推知，入5 ( g ) 存在，且a 5 ( g ) 毛( g ) 情形2 当矗= 3 时，g 为阶至少为1 0 的3 正则图根据引理1 5 若g 是 2 - 连通的，则a 5 ( g ) 存在，进而由引理2 1 6 知，砖( g ) 已( g ) 1 3 山东l 厢范大学硕士学位论文 以下不妨设g 非2 连通，则g 必含有割点，不妨设川为g 的一个割点因 g 是3 正则的，故g u 恰有3 个分支或恰有2 个分支 1 0 若g u ，恰有3 个分支，不妨设为日1 凰：风因g 是3 一正则的，故 g u 的每个分支的外度均为1 ：且每个分支的阶至少为5 显然矗日 】( 1 is3 ) 为g 的一个吃边割，从而入5 存在根据引理2 1 6 便知，a 5 f g j 6 ( g ) 2 0 若g 一让恰有2 个分支，不妨设为h 1 吼则g u 中必有一个分支的 外度为2 j 不妨设为研从而凰的外度显然为1 同样根据h 的3 正则性，我们 可以得出日1 的阶至少为4 凰的阶至少为5 令x = u ! ) u 日- 则 x 为一 个r 5 边割，从而入5 存在并且根据引理2 1 6 可知，入5 ( g ) 岛( g ) 情形3 膏= 2 时，易知a 5 ( g ) 存在，且a 5 f g ) s 矗( g ) 定理2 1 7 证毕 2 22 连通图4 - 限制边连通度的上界 对于4 限制边连通度的研究， ，p 0 “给出了阶至少是1 1 的图的4 一限制 边连通度的上界 定理2 2 1 设g 是阶至少是1 1 的连通图，若入4 ( g ) 存在，则a 4 ( g ) s 4 ( g ) 本节选取2 连通图作为研究的对象，得到： 定理2 2 2 设g 是阶至少为8 的2 一连通图，若g 不属于g 则入4 ( g ) 存在， 且入4 ( g ) s 善4 ( g ) 其中图类g 定义如下：设f 是边数至少为5 的4 阶连通图，令f 的顶点集为 v ( f ) = n 6 c d ) 且设d f ( 凸) = d f ( c ) = 3 设g 。g i 是阶为2 或3 的连通图，在 f o ，c 与g 1 g 2 之间添加4 条边，使得o c 分别与g 1 g 2 相邻，所得新图构成g 证明根据定理1 5 ：入4 ( g ) 存在，根据定理2 2 1 不妨设g 的阶n 8 9 ：1 0 ) 设f 为g 的4 阶连通导出子图，使得a ( f ) = ( g ) 并记v ( f ) = o 6 c d ) 若g f 只有一个分支，显然a 4 ( g ) 矗( g ) 以下不妨设g f 的分支g l ，g 2 的个数至少为2 下面对竹分情况证明由对称性，不妨设a ( g 1 ) a ( g 2 ) 情形l n = 8 因g 是2 连通的，故g f 恰有两个分支，则i g t l = 2 ( i = 1 ，2 ) 设1 7 ( g 1 ) = e ，厂) 对子图f 中的点z 若z 与g f 的某个分支g i 相邻，则称z 为g ，的 1 4 山东师范大学硕士学位论文 触点 情形1 1e ( f ) = 4 不妨设如f n ) = 如f 6 ) = d f ( c ) = d f ( d ) = 2 ( 对于 d f ( o ) = 如( c ，) = 2 如( c ) = 3 毋( d ) = l 的情形可类似证明) 情形1 1 1 矗( g ) = 4 1 0 若g 1 g 2 在f 中无公共触点， 知，e ( j f l ) 4 这与假设矛盾 2 0 若g 1 g 2 恰有1 个公共触点， 盾 根据g 的2 一连通性及a ( f ) 的极小性 同样由a ( f ) 的极小性知，e ( f j 4 矛 3 0 若g 1 jg 2 恰有2 个公共触点，由对称性，不妨设此两触点为n 6 令 日= g ( g 2 ) u 恤d 因为g 是2 - 连通的，从而易知日及g 一日均为4 阶连 通子图，且a ( 日) = 4 则有a 4 ( g ) 0 ( g ) 情形1 1 2 & ( g ) 5 1 0 若g 1 g 2 在f 中无公共触点，任取f 的两个端点 n 1 ， 令 日= g y ( g 1 ) u n 6 ) 显然日为4 阶连通子图，并且a ( 日) = 2 a ( g 2 ) 4 时，由l n 6 ) ，g 2 ) l 4 可以得到日= g ( g ) u 口：6 】 的外度a ( 日) 8 而此时4 ( g ) = a ( g 1 ) 一a ( g 2 ) 29 所以 同样得到矛盾 1 5 山东师范大学硕士学位论文 5 0 若g 1 g ? 恰有4 个公共触点，则已( g ) 8 若a ( g 1 ) = a ( g 2 ) = 4 则有h = g 1 ( g 1 ) u o 6 ) 的夕卜度d ( 日) = 6 矗( g ) 因此， a ( g 1 ) a ( g 2 ) 4 又知呲n 6 ) ：v ( g 2 州4 ，叭c d ) 1 ，( g 1 ) i 4 ：并且 g 1 与 c d ) 之间或g ：与 n 6 ) 之间每增加一条边，f a 的值也相应增加1 但总 有a ( 日) ( g ) 矛盾 情形1 2e ( f ) = 5 不妨设d 尸( n ) = 如( c ) = 3 如( 6 ) = 如( d ) = 2 ( 对于 如( b ) = d f ( c ) = 3 如( c c ) = d 尸( d ) = 2 的情形可类似证明) 我们设g ，) = e ，) 情形1 2 1 矗( g ) = 4 1 0 若g ，g ：在f 中无公共触点，显然日= g 、( g 1 ) u n 2 ) ) ：为4 阶连 通子图，并且g ( g 2 ) u kd ) ! 亦为4 阶连通子图，从而入a ( g ) 4 ( g ) 2 0 若g 1 g 2 恰有1 个公共触点， 根据对称性，不妨设此触点为6 由 g 的2 连通性易知日= g 1 ( g 1 ) u n 6 ) 及g 一日均为4 阶连通子图，从而 入4 ( g ) 4 ( g ) 3 0 若g 1 g 2 恰有2 个公共触点，根据对称性，有如下3 种情形： 若此两触点为。6 ：则日= g ! e o c d ) 1 及g 一日均连通易看到入4 ( g ) 荨4 ( g ) 若此两触点为n c 则由g 的2 一连通性和4 的极小性知， g 属于g 若此两触点为6 d 则= g f 已a c d ) 为4 阶连通子图，且g 一胃也连通 同样可以得到入4 ( g j 4 ( g ) 情形1 2 2 手4 ( g ) 5 不妨设a ( g 1 ) 2a ( g 2 ) 2 1 0 若g ，g 。无公共触点，由对称性，有如下两种情形： 若g l 的触点为乜6 g 2 的触点为c ：d 则a ( g ) 4 ( i = 1 2 ) 显然， 日= g i7 ( g 1 ) u o 6 ) 及g 一日均为4 阶连通子图，易见入4 ( g ) 4 ( g ) 若g 。的触点为n c ，g 2 的触点为6 d ，令日= g ( g ，) u n 6 ) 】，则日及 g 一月均为4 阶连通子图，并且a ( 日) 4 从而a ( 日) 4 - 此两种情形下，日及g 一日均为4 阶连通子图即 a 4 ( g ) s ( g ) 5 0 若g 1 g 2 恰有4 个公共触点，则已芝8 令日= g 17 ( g 1 ) u n 6 ) 易 见日及g 一日均为4 阶连通子图，从而s = 【l ，( 日) 、( g ) 1 ( ) 3 为一个凰一边 害0 ，又l 【 c 【6 ) 1 ( g 2 ) ；4 1 c d ) 1 ( g 1 ) f 4 故a 4 ( g ) sj s 善4 ( g ) 情形1 3e ( f ) = 6 此时f = 凡4 情形1 3 1