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

山东师范大学硕士学位论文 k 限制边连通度的存在性及上界 蔡俊青 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 随着社会经济和科技的发展，互联网络与人们的工作、日常生活等方面的关系 越来越密切自然，网络的可靠性和容错性倍受人们的关注研究网络的可靠性和 容错性是社会发展的必然趋势，是近年来国内外研究的热点之一众所周知，边连 通度是反映图的连通性质的一个重要参数而要更精确地刻画图的连通性质，经典 边连通度存在着不足之处：首先，边连通度相同的图的可靠度可能不同其次，不 能区分删掉肛点割或入边割得到的图的不同类型，即未考虑删掉点割或边割对网 络的损害程度第三，默认图的任何子集中所有元素可能潜在地同时失效为克服 以上缺陷，自然要将经典边连通度的概念加以推广自1 9 8 3 年h a r a r y 1 】提出条件 边连通度的概念以来，经过二十多年的发展，条件边连通度所涉及的内容日益丰富 和具体，包括超级边连通度、过边连通度、限制边连通度等 设计和分析大规模网络的可靠性和容错性时，通常涉及某些类型的图模型 针对不同的模型，都有诸多相关理论问题需要研究其中一个重要模型是这样的图 g = ( ke ) ：假设其节点不会失效，但节点间的连线相互独立地以等概率p ( 0 ，1 ) 失效则g 不连通的概率为： e p ( a ，p ) = ：c h p ( 1 一p ) 卜九， h = l 其中e 为g 的边数，瓯表示边数为h 的边割的数目则图g 的可靠度为1 一 p ( g ，p ) 显然p ( g ，p ) 越小，网络的可靠性越好因此，确定p ( g ，p ) 的大小问 题在网络可靠度的研究中倍受关注但p r o v a n 和b a l l n 已经证明，对一般图g ， p ( a ，p ) 的计算是j p 一困难的为此，e s f a h a n i a n 和h a k i m i n 提出了限制边连 通度的概念本文在前人工作的基础上，继续研究限制边连通度的相关性质 本文中k 总表示一个正整数，( g ) 表示图g 的最大团的点数在第一章中， 我们主要介绍了本文的研究背景和已有的一些结果，以及文章中所涉及的一些概念 和术语符号 1 山东师范大学硕士学位论文 定义1 3 【4 】令g = ( ke ) 是礼( 2 k ) 阶连通图，s 是g 的一个边子集， 若g s 不连通且g s 的每个分支至少有k 个顶点，则称s 为g 的k 一限制边 割，记为凡一边割g 的最小讯边割( 叫入七一边割) 所含边数称为g 的k 一限制 边连通度，记为入忌( g ) 或k 若k ( g ) 存在，则称g 是k 连通的 定义1 4 设x ，y 是图g = ( ve ) 的顶点集y 的两个不交的非空子集或g 的两个点不交的子图g 的一端点在x 中且另一端点在y 中的边构成的集合记 作【x ，明当x = z ) 时，用 x ，y 代替 x ，y 】记i ( x ) = 【x ，v 一羽，称0 ( x ) = li ( x ) l 为x 的外度 令k ( a ) = m i n a ( x ) ：ix | - k ，且g x 连通) ，这里a x 】表示x ( cv ) 在 g 中的导出子图令一x = v ( a ) 一x 若 x ，习是图g 的一个九一边割，则x 称为入七一碎片显然，若x 是一个九碎片，则又亦然图g 的含顶点数最少 的入七一碎片称为g 的入南原子，其顶点数记为r k ( c ) 定义1 1 4 设g 是札一连通的，若九( g ) = 靠( g ) ，则称图g 是k 一最优的 在第二章中，我们具体讨论了5 一限制边连通度的上界问题，得到以下结果： 定理2 3 设g 是阶至少为1 8 的连通图若g 含5 一限制边割，则a 5 ( g ) 岛( g ) 当且仅当g 不属于g 5 其中g 5 定义如下：阶至少为1 8 ，恰含一个5 阶完全图蚝，且蚝的每个顶点 上通过恰好一条边连接一个阶至多为3 的连通图得到的图 定理2 5 设g 是阶至少为1 8 的入5 连通且无三角形的图若g 不是入5 - 最 优的，则r s ( a ) m a x 6 ，2 j ( g ) 一4 ) 定理2 6 设g 是久5 一连通的，6 ( g ) 6 ，u 是g 的a 5 原子若g 不是 入5 - 最优的，则对于任意的口u ，有d c v l ( v ) 4 在第三章中，我们研究了正则图k 一限制边连通度的存在性，得到下面的结果： 定理3 1 5 设g 是阶至少为2 七的( k 一3 ) 正则连通图( k 5 ) ，则g 的k - 限制边连通度k ( g ) 存在当且仅当g 不属于g 嚣3ug 2 二；且k = 7 时，g 不同构 于g 7 这里，我们将阶至少为2 k ，( k 一3 ) 一正则连通( k 5 ) ，包含割点b 使得删掉顶 点b 后每个分支的阶为k 一1 或k 一2 的图类记为g 矗3 将阶为3 尼一3 或3 尼一4 的 ( k 一3 ) 一正则连通( 七5 ) ，由在三角形的每个顶点上各粘合一个阶k 一2 的连通 图得到的图类记为g k 乇一- 3 2 将阶为1 7 的垂正则连通，包含一条边e 和三个5 阶连 通图g l ，g 2 ，g 3 ( g t 为5 阶完全图去掉关联同一点的两条边得到，i = 1 ，2 ，3 ) ， 2 山东师范大学硕士学位论文 且e 的每个端点均与g 1 ，g 2 ，g 3 的2 度点恰通过一条边相连得到的图记为g 7 定理3 2 3 设g 是阶至少为2 七的( k 一4 ) 一正则连通图( k 6 ) ，则g 的缸 限制边连通度k ( g ) 存在当且仅当g 不属于g 2 4 u g 七k - 一i 且竞= 8 时，g 不同 构于g 7 这里，我们将阶至少为2 k ，( k 一4 ) 一正则连通( k 6 ) ，包含割点b 使得删掉 顶点b 后每个分支的阶为k 一1 ，k 一2 或k 一3 的图类记为g o 一4 将阶为3 庇一3 ， 3 七一4 ，3 七一5 或3 忌一6 的( 尼一4 ) 一正则连通( 七4 ) ，由三角形的每个顶点上各粘 合一个阶k 一2 的连通图得到的图类记为g 七k - 硝2 在第四章中，我们研究了图是后一限制边连通度最优的充分条件，得到下面的 结果： 定理4 5 设g 是一个礼( 2 k ) 阶连通图假设对g 中任意一对不相邻的顶 点z 和y ，都有d ( x ) + d ( y ) 礼+ 2 k 一4 ，若g 不是g ：图，则g 是h 一最优的 其中图g 是这样的凡( 2 k ) 阶连通图，它的顶点集可剖分成两部分，k ， 使得l l ，1 l 岛且若存在耽k ，使得d ( 戤) = l k l + 忌一2 且瓤是陬，】的 k l 饱和点( 即x i 与陬，k 】的k 一1 条边关联) ，i = 1 ，2 ，则x l ，x 2 不相邻 定理4 9 设g 是扎阶入3 一连通无三角图，度序列为d l d 2 厶= 6 。 若 - r d n _ ；m a x 1 ，鹕j + 3 一熹) ， t ，6 2 去( 自+ 3 一熹) ， 则g 是入3 一最优的 定理4 1 0 设p 3 是一个整数，g 是死阶又3 一连通图且留( g ) p ，度序列 d l d 2 厶= 6 若 一善 i , 5 - 4 “犰球小4 ) 字啪3 + 研南 ， 厶砬仇口z 1 ，j 一4 ) 争峥+ 3 + 不斋蒹 ， 则g 是a 3 一最优的 关键词：图；正则图；k 一限制边连通度；九最优的 分类号： 0 1 5 7 ，5 3 山东师范大学硕士学位论文 t h ee x i s t e n c ea n du p p e rb o u n do fk - r e s t r i c t e d e d g ec o n n e c t i v i t yo fg r a p h s j u n q i n gc a i s h a n d o n gn o r m a lu n i v e r s i t y , 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 w i t ht h ed e v e l o p m e n to fs o c i a le c o n o m y , s c i e n c ea n dt e c h n o l o g y , t h er e l a t i o n - s h i pb e t w e e nm a na n dn e t w o r k sb e c o m e sm o r ea n dm o r ec l o s e l y n a t u r a l l y , t h e r e s e a r c ha b o u tt h er e l i a b i l i t ya n df a u l t t o l e r a b i l i t yo fn e t w o r k si st h ei n e v i t a b l e t r e n do fs o c i a ld e v e l o p m e n t ，a n di t i so n eo ft h em o s ta c t i v er e s 6 a r c h e sa th o m e a n da b r o a dt h e s ey e a r s a sw ek n o w ，e d g e c o n n e c t i v i t yp l a y sa ni m p o r t a n tr o l ei n t h ec o n n e c t i v i t yo fg r a p h s b u tu n f o r t u n a t e ! y , t h ec l a s s i c a lc o n c e p to ft h ee d g e - c o n n e c t i v i t yh a st h r e eo b v i o u sd e f i c i e n c i e s f i r s t ，e v e nt w og r a p h sw i t ht h es a m e e d g e - c o n n e c t i v i t ym a yh a v ed i f f e r e n tr e l i a b i l i t y s e c o n d ，s o m e t i m e sw ec a nn o t i d e n t i f yt h ed i f f e r e n tt y p e so fd i s c o n n e c t e dg r a p h sw h i c hr e s u l tf r o mr e m o v i n g ，扣 v e r t e x - c u t so r 入一e d g e c u t s i no t h e rw o r d s w eh a v e n tc o n s i d e r e dt h ed a m a g eo ft h e v e r t e x - c u t sa n dt h ee d g e - c u t s t h i r d ，t h es h o r t c o m i n go fu s i n gt h e ma sm e a s u r e so f f a u l tt o l e 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 l le l e m e n t si na n ys u b s e to fgc a n p o t e n t i a l l y f a i la tt h es a m et i m e c o n s e q u e n t l y , t oc 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 ts e e m sn a t u r a lt og e n e r a l i z et h en o t i o no fc l a s s i c a le d g e c o n n e c t i v i t y s i n c e h a r a r y 1 1p 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 le d g e - c o n n e c t i v i t yi n1 9 8 3 ，a f t e ra b o u t t w e n t yy e a r sd 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 le d g e - c o n n e c t i v i t yb e c o m e m o r er i c ha n ds p e c i f i c ，i n c l u d i n gs u p e re d g e - c o n n e c t i v i t y , e x t r ae d g e c o n n e c t i v i t y , r e s t r i c t e de d g e - c o n n e c t i v i t y , a n ds oo n t h ed e s i g na n da n a l y s i so fl a r g e - s c a l er e l i a b l en e t w o r k st y p i c a l l yi n v o l v es o m e t y p e so fg r a p hm o d l e s t h e r ea r eav a r i e t yo ft h e o r e t i c a lp r o b l e m sc o r r e s p o n d i n g t od i f f e r e n tm o d l e s o n ei m p o r t a n tm o d l ei san e t w o r ka sf o l l o w s ：ag r a p hg= 4 山东师范大学硕士学位论文 ( ve ) t o g e t h e rw i t hap r o b a b i l i t yo ff a i l u r ep ( 0 ，1 ) a s s o c i a t e dw i t he a c he d g e w ea s s u m et h a tt h ee d g e sf a l li n d e p e n d e n t l yw i t ht h es a m ep r o b a b i l i t y , i ti sa l s o a 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 l i t yt h a tgi sd i s c o n n e c t e d c a nb ee x p r e s s e da s e p ( g ，p ) = h ( 1 一p ) 卜 ， h = 1 w h e r eei st h et 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 h t h e r e f o r e ，t h er e l i a b i l i t yo fg i s1 一p ( g ，p ) c l e a r l y , t h es m a l l e rp ( a ，p ) i s ， t h eb e t t e rt h er e l i a b i l i t yo fgi s t h e r e f o r e ，t h ep r o b l e mo fd e t e r m i n i n gp ( g ，p ) f o rag i v e ng r a p hga n dph a sr 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 nr e s e a r c ho fn e t w o r k s r e l i a b i l i t y h o w e v e r ，p r o v e na n db a l l 2 h a v es h o w nt h a tt h ec a l c u l a t i o no f p ( c ，p ) f o ra na b i t r a r yg r a p hg i s p - h 缸d t os o l v et h i sp r o b l e m ，e s f a h a n i a n a n dh a k i m i s 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 de d g e - c o n n e c t i v 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 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 fr e s t r i c t e de d g e - c o n n e c t i v i t y o nt h eb a s i so fp r e v i o u sw o r k i nt h i sp a p e r ，w eu s ekd e n o t i n gap o s i t i v ei n t e g e r ，u ( g ) d e n o t i n gt h es i z eo fa m a x i n u mc l i q u eo fg r a p hg i nt h ef i r s tc h a p t e r ，w eg i v e ab r i e fi n t r o d u c t i o na b o u t t h eb a s i cc o n c e p t s ，t e r m i n o l o g i 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 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 ds o m ek n o w n r e s u l t s d e f i n i t i o n1 3 1 4 l e tgb eac o n n e c t e dg r a p ho fo r d e r 佗( 2 k ) a ne d g e s e ts ei sak - r e s t r i c t e de d g ec u td e n o t e db yr k e d g ec u tf o rs h o r ti fg s i sd i s c o n n e c t e da n de a c hc o m p o n e n to fg sh a sa tl e a s tkv e r t i c e s t h es i z eo f am i n i m u mr k e d g ec u to fg r a p hgi si t sk - 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 e d b y 入七( g ) ，o rs i m p l ya 南i fg r a p hgc o n t a i n s 月k e d g ec u t s ，t h e ng i sc a l l e d 入七一 c o n n e c t e d d e f i n i t i o n1 4l e tx ，yb et w od i s j o i n ts u b s e t so fvo rt w ov e r t e x - d i s j o i n t s u b g r a p h so fc = ( ve ) t h es e to fe d g e sw i t ho n ee n di nxa n dt h eo t h e r i nyi sd e n o t e db y x ，y 】w es i m p l i f y x ，y 】a s 【z ，y 】i fx = z ) d e n o t e z ( x ) = 【x ，v x 】，a ( x ) = iz ( x ) ii sc a l l e de x t e r n a ld e g r e eo fx l e t ( g ) = 嘶n a ( x ) ：ixl = k ，a n dc x i sc o n n e c t e d ) ，w h e r ec x 】 d e n o t e st h es u b g r a p ho fgi n d u c e db yx l e t 叉= v ( a ) 一x i f 【x ，- 】i sa 5 山东师范大学硕士学位论文 a k c u to fg ，t h e nx i sc a l l e da 入七一f r a g m e n t c l e a r l y , i fx i sa k f r a g m e n t ，s oi sx ak f r a g m e n tw i t hm i n i m u mc a r d i n a l i t yo fgi sc a l l e dak a t o m t h ec a r d i n a l i t y o fak a t o mi sd e n o t e db y ( g ) d e f i n i t i o n1 1 4aa k c o n n e c t e dg r a p hgi sc a l l e da k o p t i m a l ，i fa k ( g ) = 缸( g ) i nt 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 eu p p e rb o u n do ft h e5 - r e s t r i c t e d e d g ec o n n e c t i v i t ya n dh a v et h ef o l l o w i n gr e s u l t s ： t h e o r e m2 3l e tgb eac o n n e c t e dg r a p hw i t ho r d e ra tl e a s t1 8 i fg c o n t a i n s5 - r e s t r i c t e de d g ec u t s ，t h e na s ( g ) 矗( g ) i fa n do n l yi fgd o e s n tb e l o n g t og 5 w h e r eg 5i sd e f i n e da sf o l l o w s ：c o n n e c t e dg r a p h sw i t ho r d e ra tl e a s t1 8 ，c o n - t a i n i n ge x a c t l yac o m p l e t eg r a p hk 5 ，a n de a c hv e r t e xo f 蚝i sj o i n tt oa c o n n e c t e d g r a p hw i t ho r d e ra tm o s t3b ye x a c t l yo n ee d g e t h e o r e m2 5l e tgb ea 久5 一c o n n e c t e dt r i a n g l e - f r e eg r a p hw i t ho r d e ra t l e a s t1 8 i fgi sn o t 九一o p t i m a l ，t h e nr k ( g ) m a x 6 ，2 6 ( g ) 一4 ) t h e o r e m2 6l e tcb eaa 5 一c o n n e c t e dg r a p h ，6 ( g ) 6 ，ui saa s a t o mo f g i fgi sn o t 入知一o p t i m a l ，t h e nf o re a c hu u ，w eh a v ed g t u l ( v ) 4 i nt 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 x i s t e n c eo ft h ek - 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 fr e g u l a rg r a p h sa n do b t a i nt h er e s u l t sa sf o l l o w s ： t h e o r e m3 1 5i fgi sa ( 忌一3 ) 一r e g u l a rc o n n e c t e dg r a p h ( 七5 ) o fo r d e r a tl e a s t2 k t h e ngc o n t a i n s 尼一r e s t r i c t e de d g ec u t si fa n do n l yi fgd o e sn o tb e l o n g t og 矗3u g ：二；a n dgi sn o ti s o m o r p h i ct og 7w h e nk = 7 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 hg a sg 麓3 ：ci sa ( k - 3 ) 一r e g u l a r c o n n e c t e dg r a p ho fo r d e ra tl e a s t2 kw i t h 炙5 ，a n dgc o n t a i n sa c u t v e r t e x ，i fa n y , 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 eo r d e ro fe a c hr e m a i n i n gc o m p o n e n ti sk 1 o r 七一2 d e n o t et h es e to ft h i sk i n do fg r a p hca sg 2 二；：gi sa ( 七一3 ) 一r e g u l a r c o n n e c t e dg r a p ho fo r d e r3 k 一3o r3 k 一4w i t hk 5 ，a n dgc o n t a i n sa t r i a n g l et ， i fa n y , a n de a c hv e r t e xo fti sj o i n tt oac o n n e c t e dg r a p ho fo r d e r 七一2o rk 一3 b ys o m ee d g e s d e n o t et h es e to ft h i sk i n do fg r a p hga sg i 7 ：ci sa & r e g u l a r c o n n e c t e dg r a p ho fo r d e r17 ，a n dcc o n t a i n sa ne d g eea n dt h r e ec o n n e c t e dg r a p h s g l ，g 2 ，g 3a n de a c hw i t ho r d e r5 ( w h e r eg ii sag r a p ho b t a i n e db yd e l e t i n gt w o 6 山东师范大学硕士学位论文 e d g e si n c i d e n tw i t ht h e e a c hv e r t e xo fei sj o i n tt ot h ev e r t e xw h i c h c o m p l e t eg r a p hk s ，i = l ，2 ，3 ) a n d d e g r e ei s2o fg 1 ，g 2a n dg 3 t h e o r e m3 2 3i fgi sa ( k 一4 ) 一r e g u l a rc o n n e c t e dg r a p h ( 七6 ) o fo r d e r a tl e a s t2 k t h e ngc o n t a i n sk - r e s t r i c t e de d g ec u t si fa n do n l yi fgd o e sn o tb e l o n g t og o 一4 u g ：二ia n dgi sn o ti s o m o r p h i ct og 7w h e nk = 8 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 hg a sg o 一4 ：gi sa ( 庇- 4 ) - r e g u l a r c o n n e c t e dg r a p ho fo r d e ra tl e a s t2 kw i t h 七6 ，a n dgc o n t a i n sac u t v e r t e x ，i f a n y , w h o s ed e l e t i o nd i s c o n n e c t sg a n dt h eo r d e ro fe a c hr e m a i n i n gc o m p o n e n ti s k l ，k 一2o rk 一3 w ed e n o t et h es e to ft h i sk i n do fg r a p hg a sg ：二：gi sa ( k 一4 ) 一r e g u l a rc o n n e c t e dg r a p ho f o r d e r3 k 一3 ，3 七一4 ，3 七一5o r3 k 一6w i t h 南6 ， a n dgc o n t a i n sat r i a n g l et ，i fa n y , a n de a c hv e r t e xo fti sj o i n tt oac o n n e c t e d g r a p ho fo r d e rk 一2 惫一3o r 七一4b ys o m ee d g e s i nt h ef o u r t hc h a p t e r ，w em a i n l yg i v es o m es u f f i c i e n tc o n d i t i o n sf o rag r a p ht o b ea 七一o p t i m a l w eh a v et h ef o l l o w i n gr e s u l t s ： t h e o r e m4 5l e tgb eag r a p ho fo r d e r 死( e k ) ，a n dd ( u ) + d ( u ) n + 2 k - 4 f o re v e r yp a i ro fn o n a d j a c e n tv e r t i c e sua n dui nv i fgi sn o ti s o m o r p h i ct og ， t h e ng i s 入七一o p t i m a l w h e r eg 套i sd e f i n e da sf o l l o w s ：ac o n n e c t e dg r a p ho fo r d e r 礼( 2 k ) a n di t s v e r t e xs e tc a nb ed i v i d e di n t ot w op a r t s a n d ，w i t hf l ，i k l k i ft h e r e e x i s t sz i k ，s u c ht h a t d ( x ) = l k l - b 庇一2 ，a n dz ti sak 一1 一s a t u r a t e dv e r t e x 0 f 【， ( t h a ti st os a y ：雹i si n c i d e n tw i t hk 一1e d g e so f 【，v 2 】) ，i = 1 ，2 ， t h e nx la n dx 2a r en o ta d j a c e n t t h e o r e m4 9l e tgb eaa 3 一c o n n e c t e dt r i a n g l e - f r e eg r a p ho fo r d e r 扎w i t h d e g r e es e q u e n c ed l d 2 d n = 6 i f 撇t 1 ，6 - 2 ) 厶一i m a x 1 ， i - - 1 t h e ngi sa s - o p t i m a l 6 2 啦争+ 3 一再2 ) ， t h e o r e m4 1 0l e tp 3b ea ni n t e g e r ，a n dl e tgb eaa 3 一c o n n e c t e dg r a p h o f o r d e rnw i t hc l i q u en u m b e ru ( g ) pa n dd e g r e es e q u e n c ed l d 2 “= 山东师范大学硕士学位论文 6 ( g ) i f r “狮印小4 ) p 了- 1 啪3 + 两】， 厶一t m 口z 1 ，j 一4 ) 了旧+ 3 + 币可罴暑下丽】， t h e ng i s 又3 一o p t i m a l 一 k e y w o r d s ：g r a p h ；r e g u l a rg r a p h ；k - r e s t r i c t e de d g ec o n n e c t i v i t y ；k o p t i m a l c l a s s i f i c a t i o n ：0 1 5 7 5 8 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得 ( 注：如没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或 证书使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意 学位论文作者签名：蔡彳缔 导师签字： 高妒溉面貌 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅本人授权学校可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：蔡促惫 签字日期：2 0 0 9 年厶月1 日 一字：高撤玩 签字口期：2 0 0 9 年4 月2 ，日 山东师范大学硕士学位论文 第一章预备知识 众所周知，信息时代的到来促使互联网络迅猛发展，网络已与人们的生活以及 各行各业息息相关自然，研究网络的可靠性和容错性成为社会发展的必然趋势 近几十年来，网络的可靠性和容错性成为国内外的研究热点之一大型互联网络的 拓扑结构通常用某些图模型来刻画，其中一个重要模型是这样的图g = ( ve ) ：其 节点不会失效，但节点间的连线可能相互独立地以等概率p 失效若设g 的边数 为e ，令g 表示边数为h 的边割的数目，则g 不连通的概率为： e p ( a ，p ) = ：c h p ( 1 一p ) 卜h h = l 称函数p ( a ，p ) 为g 的不可靠度多项式，则图g 的可靠度为1 - p ( g ，p ) 显然， p ( a ，p ) 越小，网络越可靠但p r o v a n 和b a l l 2 】证明了，对一般图，p ( g ，p ) 的 计算是p 一困难的 本文仅考虑有限无向简单图，所使用的记号和术语约定如下，其中未加说明的 部分将在必要时予以阐述或请参照文献3 2 设g = ( ve ) 是一个图，g 的顶点的个数称为g 的阶，记为l y ( g ) l 或f g l 专用t , 表示g 的阶 设s 为g 的一个边子集，s ( u ) 表示s 中与顶点u 相关联的边的集合当 i s ( 乱) i = 1 ( 或尼( 2 ) ) 时，称u 是s 单饱和的( 或忌( 2 ) 饱和的) 如果对每个点 x xcv ，都有l s ( z ) l 1 ，则称s 饱和x q ( 他，e ) 表示住个顶点和e 条边的图的集合u ( g ) 表示图g 的最大团的顶 点数，c ( g ) 表示g 的连通分支的个数 我们知道，当p 充分小时，为在q ( 佗，e ) 中最小化p ( g ，p ) ，边连通度入( g ) 起重 要作用事实上，b a u e re ta l n 已经证明，对g 1 ，g 2 q ( n ，e ) ，如果入( g 1 ) a ( g 2 ) ， 那么当p 充分小时，p ( g l ，p ) 入2 ( g 2 ) ，则当p 充分小时，p ( g 1 ，p ) k 2 + 1 ， 则a 七( g ) 靠( g ) 张昭等【16 】证明了： 定理1 1 2 设g 是阶至少为2 ( 6 ( g ) + 1 ) 的连通图若g 不同构于g t ，t = 6 ( g ) ，则对任意的k 6 ( a ) + 1 ，k ( g ) 存在，且久豇( g ) 缸( g ) 其中嚷。是如下构造的图：令g l ，g 2 ，g 仉均为完全图甄，添加一个 1 1 山东师范大学硕士学位论文 新点“，使得u 与y ( g t ) ( 1 i m ) 的每个顶点相邻，所得新图即为瓯 高敬振和张淑芹 1 7 1 给出了： 定理1 1 3 设g 是连通，阶至少为2 七的( k 一2 ) 正则图，则g 的k 一限制边 连通度入七( g ) 存在当且仅当g 不属于g ；一2 这里，我们将阶至少为2 k ，( k 一2 ) 正则( k 5 ) ，包含割点b 使得删掉b 点后 每个分支的阶为k 一1 的图类记为g ：一2 然而要设计并分析大规模的可靠网络，我们自然首先要确定出使得k 一限制边 连通度存在应满足的图结构，这也是一个前提条件进而，为使得网络的可靠性尽 可能的大，即为了最大化九( g ) ，我们需要找到入七( g ) 的上界，并确定出其上界是 否可达，即研究儿( g ) 的最优性问题 张昭等【1 8 】给出了图g 是儿一最优的一个o r e 型充分条件： 定义1 1 4 设g 是入七连通的，若九( g ) = 靠( g ) ，则称图g 是入南一最优的 定理1 1 5 设k 是一个正整数，g 是一个佗( 2 k ) 阶连通图假设对g 中任 意一对不相邻的顶点x ，y ，都有d ( x ) + d ( y ) n + 2 七一3 ，则g 是沁一最优的 王世英等【1 9 】给出了图g 是k 一最优的另一个充分条件： 定理1 1 6 设g 是一个凡( 2 k ) 阶连通图假设对g 中任意一对不相邻的顶 点z ，y ，都有i n ( x ) n ( y ) i 2 k 一1 ，则g 是k 一最优的 基于以上研究背景，本文选择k 一限制边连通度的相关性质，即舡限制边连通 度的存在性、上界和最优性作为研究的内容，主要沿着推广已有结论和探索新结果 两个思路进行研究 1 2 山东师范大学硕士学位论文 第二章5 限制边连通度的上界 据定理1 2 ，1 5 ，1 6 ，我们有： 定理2 1 对图g ，设a 七( g ) 存在，则k 3 或k = 4 且i g i 1 1 时， k ( g ) 缸( g ) 这一章主要研究阶至少为1