（应用数学专业论文）高阶限制边连通度的最优性和超级性.pdf

山东师范大学硕士学位论文 高阶限制边连通度的最优性和超级性 陈亮 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 目前，互联网络已经与人们的工作、日常生活等方面息息相关网络的可靠性 和容错性是近年来国内外研究的热点之一我们知道，边连通度是反映图的连通性 质的一个重要参数而要精确地刻画图的连通性质，它存在着不足之处：首先，边 连通度相同的图可靠度可能不同；其次，不能区分删掉k 个割断点或a 条割断边 得到的图的不同类型，即未考虑对网络的伤害程度；第三，默认图的任何子集中所 有元素可能潜在地同时失效为克服以上缺陷，自然要将其加以推广自1 9 8 3 年 h a r a r y 1 1 提出条件连通度的概念以来，经过二十多年的发展，条件连通度所涉及的 内容日益丰富和具体，包括超级连通度、过边连通度、限制边连通度等 设计和分析大规模网络的可靠性和容错性时，通常包括某些类型的图模型，其 中个重要模型是这样的网络【2 】： 设图g = ( ke ) ，其节点不会失效，每一条边是独立失效的，失效概率为p 用 川( g ) 表示边数为i 的边割的数目，则g 连通的概率r ( g ，p ) 为。 e r ( g ，p ) = 1 一 ：m ( g ) p l ( 1 一p ) 卜。， l = ( g ) 其中是g 的边数，a ( g ) 为边连通度对于一般图，确定m ( g ) 是p - 困难的 【3 】b a u e re t4 4 】提出了最优性的概念，称g 是* 最优的，如果a ( g ) = 占( g ) 进 一步，若g 的每个最小边割孤立一个点，称g 是超级一a 的 为了更好地刻画图的连通性，e s f a h a n i a n 和h a k i m i 8 】提出了限制边连通度的 概念 g 的一个边割u e 称为限制边割，如果g u 的每个分支不包含孤立 点如果这样的边割存在，限制边连通度a 7 ( g ) 为限制边割中最小的阶，并且称g 为a 7 连通的他们证明了阶至少是4 的除星k 1 竹一1 外的连通图是a 7 连通的，并 且满足a 7 ( g ) ( g ) ，这里( g ) = m i n d c ( u ) + d g ( 口) 一2 ：u e ( g ) ) 是g 的最小边 度如果a 7 ( g ) = ( g ) ，称g 是n 最优的进一步，若g 的每个最小限制边割孤 立一条边，称g 是超级a 7 的 山东师范大学硕士学位论文 令k 是正整数对于连通图g = ( ke ) ，个边割u e 称为舡限制边割，如 果g u 的每个分支至少有k 个点如果这样的边割存在，k 限制边连通度札( g ) 为k 限制边割中最小的阶，并且称g 为k 连通的弘限制边连通度在容错性研 究中是一个非常重要的参数令靠( g ) = m i n o ( f ) ：f 是g 的k 阶连通子图) ，这里 o ( f ) 表示恰好有一个端点在f 中的边的集合在多数图中a k ( g ) 缸( g ) 【2 8 】如果 札( g ) = 缸( g ) ，称g 是札最优的进一步，若g 的每个最小肛限制边割孤立一 个k 阶连通子图，称g 是超级a 奄的 在本文中，我们在前人的基础上继续讨论舡限制边连通度的相关性质 在第一章中，我们主要介绍本文中的相关概念，定理和符号同时，我们给出 了相关的研究背景和前人的结果 在第二章中，我们用直径和围长来刻画图的k 最优性和超级性的充分条件， 得到如下的结果： 定理2 2 令启3 是正整数对图g ，如果i g l 2 k ，d 9 一( k + 1 ) 且后6 + 1 ， 这里d ，g ，6 分别表示g 的直径、围长和最小度，则g 是a 七一最优的 。 定义设g l ，g 2 是两个阶至少是k 的图含g 1ug 2 ，且对于每个点z v ( g 1 ) ， 陋，g 2 】l = 1 的图所组成类记作g x 定理2 4 令k 4 是正整数对图g ，如果j g i 2 k ，d 夕一( k + 2 ) 且k 6 + 1 ， 这里d ，g ，6 分别表示g 的直径、围长和最小度，则g 是超级一k 的，除非g g x 在第三章中，我们用局部结构来刻画图的k 最优性和超级性的充分条件，得 到下面的结果： 定理3 8 设g 是n 阶a 3 一连通图，最小度6 【鸶j 一2 ，且 ( a ) 每个导出四圈中至少有一个点z ，满足d ( x ) 【詈j ； ( b ) 每个k 4 一e 中至少有一个点耖，满足d ( 可) 【考j + 2 ， 则g 是a 3 一最优的 2 定理3 9 设g 是一个他阶a 七连通图，k ( g ) & ( g ) ，对g 的任意一 山东师范大学硕士学位论文 个k 阶连通子图风及恰好在最中有s ( 1 s k ) 个邻点的y ( g ) y ( 最) ， d ( ) 【引一k + 2 s l ，则g 是a 七一最优的 定理3 1 1 设g 是一个n 阶入k 连通图，x k ( g ) 缸( g ) ，对g 的任意一 个k 阶连通子图兄及恰好在风中有s ( 1 s 七) 个邻点的t y ( g ) y ( 最) ， d ( u ) 【刭一k + 2 s 一1 ，则g 是超级一札的 在第四章中，我们用邻域结构来刻画图的a 詹一连通性，上界以及图的沁最优 性和超级性，得到下面的结果： 定理4 2 设g 是阶至少是2 k 的图，每对不相邻的点，口满足i n ( u ) n ( 口) l 尼+ 1 ，则g 是a 七一连通的且k ( g ) 缸( g ) 定义设日1 是【署j + i 阶连通图，也是【警j t 阶连通图，其中0 i 七一1 把 含皿u 日2 ，满足l 【h l ，日2 】l 【号j + 一1 ，且每个让y ( 皿) 满足i n ( u ) n v ( h 2 ) i 1 ， 每个口y ( 耽) 满足i ( 口) n v ( h i ) i 1 的图类记作g 1 定理4 3 设g 是n 阶( n 2 k ) 图且g 譬g x 每一对不相邻的点t ，秒满足 ( ) n ( ) l k + 1 ，且缸( g ) 【号j + k ，则g 是沁一最优的 定理4 4 设g 是n 阶2 k ) 图且最是g 的任意一个七阶连通子图，每一 对不相邻的点u ，口满足i ( t ) n ( ) l k + 1 ，恰好在最中有s ( 2 8 k ) 个邻点 的点z y ( g ) y ( 最) 满足d ( z ) 【到一k + 2 s 一1 ，则g 是a 一最优的 在第五章中，我们用一定距离的两点的度和来刻画图的k 最优性和超级性， 得到以下如下的结果： 定理5 1 设g 是他阶k 6 + 1 的儿一连通图，满足如下两个条件，则g 是 a 一最优的： ( a ) 对于每对距离为惫一s + 1 ，( k 一1 8 1 ) 的点z ，y ，有 d ( z ) + d ( 毫，) 2 【三j + 2 s 一5 ； 3 山东师范大学硕士学位论文 ( b ) 对于每个k 阶连通子图最，若z 是f k 的k 个点的公共邻点，则 d ( z ) 目+ 后1 定理5 3 设g 是n 阶k 6 + 1 的k - 连通图，满足如。f 两个条件，则g 是 超级a 七的： ( a ) 对于每对距离为k s + 1 ，( k 一1 s 1 ) 的点z ，y ，有 d ( z ) + d ( 耖) 2 【罢j + 2 s 一3 ； ( b ) 对于每个k 阶连通子图最，若z 是兄的k 个点的公共邻点，则 d ( 名) 纠昙j + 七 在第六章中，我们主要研究图的札最优性和超级性的关系，证明了下面的结 定理6 1 设k 是正整数若g 是一个占2 k 一1 的a 七一最优图，则对于 i = 1 ，2 ，k 一1 ，g 是超级一a 七一 的 关键词； 错性 分类号： 4 图；边连通度；k 限制边连通度；a 七最优的；超级一沁的；容 0 1 5 7 5 山东师范大学硕士学位论文 o p t i m a l i t ya n ds u p e r - c o n n e c t e d n e s so f h i g h e r - o r d e rr e s t r i c t e de d g ec o n n e c t i v i t yi ng r a p h s l i a n gc h e n 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 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 h a 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 a r c ha b o u tt h er e l i a b i l i t ya n dt o l e r a b i l i t yo f n e t w o r k si sv e r ya c t i v e w ek n o wt h a te d g ec 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 nt h e c o n n e c t i v i t yo fg r a p h b u tt h ec l a s s i c a lc 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 eo b v i o u s d e f i 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 d t oh 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 l y , t h e yd on o td i f f e r e n t i a t eb e t w e e nt h ed i f f e r e n t t 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 d i s c o n n e c t i n gv e r t i c e s o r 入d i s c o n n e c t i n ge d g e s t h i r d l y , 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 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 l le 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 n y f a i la tt h 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 o g e n e r l i z et h en o t i o no fc l a s s i c a le d g ec o n n e c t i v i t y s i n c eh a r 哪 1 】p r o p o s e dt h ec o n c e p t o fc o n d i t i o n a lc o n n e c t i v i t yi n1 9 8 3 ，a f t e ra b o u tt 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 s i nc o n d i t i o n a lc 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 ，i n c l u d i n gs u p e rc o n n e c t i v i t y , e x t r ae d g ec o n n e c t i v i t y , r e s t r i c t e de d g ec o n n e c t i v i t y , a n ds oo n t 1 1 ed e s i g na 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 k st y p i c a l l yi n v o l v es o m et y p e s o 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 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 ed e p e n d i n g o nt h ee x a c tn e t w o r kr e l i a b i l i t ym o d l et h a ti su s e d o n ei m p o r t a n tm o d l ei san e t w o r k o fs u c h2 l s 2 】： a s s u m et h a ta l lv e r t i c e s o fg = ( ue ) a r ep e r f e c t l yr e l i a b l ea n da l le d g e sf a i l e d i n d e p e n d e n t l y , w i t ht h es a m ep r o b a b i l i t yp ，d e n o t eb ym ( g ) t h en u m b e ro fe d g ec u t so f 5 山东师范大学硕士学位论文 s i z e t h e nt h ep r o b a b i l i t yr ( g ，p ) o fg b e i n gc o n n e c t e d n e s si sg a v eb y e r ( c ，p ) = 1 m ( g ) p ( 1 - p ) 卜， = a ( g ) h e r e i st h en u m b e ro fe d g e so fg ，t h ee d g ec o n n e c t i v i t yo fg ，d e n o t e db y 入( g ) ，i s d e f i n e da st h ec a r d i n a l i t yo fam i n i m u me d g ec u t i ng e n e r a l ，i ti sd i f f i c u l tt od e t e r m i n e m ( g ) o f ag r a p h 3 b a u e re ta 1 4 】d e f i n e dt h a tag r a p hgi sa - o p t i m a li fa ( c ) = 6 ( g ) ， a n dgi ss u p e r - ai fe v e r ym i n i m u me d g ec u to fgi s o l a t e so n ev e r t e x t h er e s t r i c t e de d g ec o n n e c t i v i t yw a sp r o p o s e db ye s f a h a n i a na n dh a k i m i 8 】t 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 yp r o v i d e sam o r ea c c u r a t em e a s u r eo ff a u l t - t o l e r a n c eo fn e t - w o r k st h a nt h ec l a s s i c a le d g ec o n n e c t i v i t y a ne d g es e tuo fgi sc a l l e dar e s t r i c t e d e d g ec u ti fg ui sd i s c o n n e c t e da n de v e r yc o m p o n e n to fg uc o n t a i n sn oi s o - l a t e dv e r t e x i fs u c ha ne d g ec u te x i s t s ，t h e nt h er e s t r i c t e de d g ec o n n e c t i v i t yo fg ， d e n o t e db ya 7 ( g ) ，i sd e f i n e da st h ec a r d i n a l i t yo fam i n i m u mr e s t r i c t e de d g ec u t ，a n d gi sc a l l e da - c o n n e c t e d e s f a h a n i a na n dh a k i m is h o w e dt h a te a c hc o n n e c t e dg r a p hg o fo r d e rn 4e x c e p tas t a rk i , n - 1i sa - c o n n e c t e da n ds a t i s f i e sa ( g ) ( g ) ，w h e r e ( g ) = m i n d g ( 札) + d e ( 移) 一2 ：伽e ( g ) ) i st h em i n i m u me d g ed e g r e eo fg gi s a - o p t i m a li f 入7 ( g ) = ( g ) m o r e o v e rgi ss u p e r - a i fe v e r ym i n i m u mr e s t r i c t e de d g ec u t 0 f gi s o l a t e sa ne d g e l e tkb eap o s i t i v ei n t e g e r f o rac o n n e c t e dg r a p hg = ( k e ) ，a ne d g e 舱t 矿ei s ak - r e s t r i c t e de d g ec u ti fg ui sd i s c o n n e c t e da n de v e r yc o m p o n e n to fg uh a sa tl e a s t 后v e r t i c e s t h ek - r e s t r i c t e de d g ec o n n e c t i v i t yo fg ，d e n o t e db yk ( g ) ，i sd e f i n e da st h e e a r d i n a l i t yo fam i n i m u mk - r e s t r i c t e de d g ec u t a n dg i sc a l l e da k c o n n e c t e d k - r e s t r i c t e d e d g ec o n n e c t i v i t yi sa ni m p o r t a n tp a r a m e t e ri nm e a s u r i n gt h er e l i a b i l i t ya n df a u l tt o l - e r a n c eo fn e t w o r k s l e t & ( g ) = m i n c g ( f ) ：fi sac o n n e c t e ds u b g r a p ho fg ，l f i = 耐， w h e r eo ( f ) d e n o t e st h en u m b e ro fe d g e sw i t ho n ee n di nf e x a c t l y i th a sb e e ns h o w n t h a ta k ( g ) 靠( g ) h o l d sf o rm a n yg r a p h s 2 s gi s 札- o p t i m a li fa k ( g ) = 缸( g ) m o r e - o v e rgi ss u p e r - a ki fe v e r ym i n i m u mk - r e s t r i c t e de d g ec u to fgi s o l a t e so n ec o n n e c t e d s u b g r a p hfo fo r d e r 七 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 fk - r e s t r i c t e d c o n n e c t i v i t yo nt h eb a s i so fp r e v i o u sw o r k i nt h ef i 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 一 6 山东师范大学硕士学位论文 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 nt h em e a n t i m e ，w ea l s og i v e s 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 nr e s u l t s i nt h es e c o n dc h a p t e r ，w ew i l ls h o ws o m es u f f i c i e n tc o n d i t i o n sf o rg r a p h st ob ea k o p t i m a lb yu s i n gt h ed i a m e t e rda n dt h eg i r t hgo fg ： t h e o r e m2 2 l e tk 3b ea ni n t e g e r ，gb eag r a p hw i t hi g i 2 k ，d g 一( k + 1 ) a n d 惫6 + 1 ，w h e r ed ，g ，6d e n o t et h ed i a m e t e r ，t h eg i r t ha n dt h em i n i m u md e g r e eo f g ，r e s p e c t i v e l y , t h e ngi sa k - o p t i m a l d e f i n i t e l e tg 1 ，g 2b et w og r a p h sw i t ho r d e ra tl e a s t 七，r e s p e c t i v e l y w ed e f i n ea g r a p hf a m i l yg xc o n t a i n i n gg 1ug 2a n ds a t i s f i n gl 陋，g 2 i = 1f o re a c hv e r t e xz v ( c 1 ) t h e o r e m2 4 l e tk 4b ea ni n t e g e r ，gb eag r a p hw i t hi g i 2 k ，d g - ( k + 2 ) a n d 后占+ 1 ，w h e r ed ，g ，6d e n o t et h ed i a m e t e r ，t h eg i r t ha n dt h em i n i m u md e g r e eo f g ，r e s p e c t i v e l y , t h e ngi ss u p e r - a ke x c e p tg g x i nt h et h i r dc h a p t e r ，w ew i l ls h o ws o m es u f f i c i e n tc o n d i t i o n sf o rg r a p h st ob e 入七一 o p t i m a lb yu s i n gs u b g r a p h ： t h e o r e m3 8 l e tgb ea 抛一c o n n e c t e dg r a p hw i t ho r d e rna n d6 【詈j 一2 ，a n d gs a t i s f i e st h ef o l l o w i n gt h r e ec o n d i t i o n s ，t h e ng i s 入七一o p t i m a l ： ( a ) f o re a c hi n d u c e d4c y c l e 戗，t h e r ee x i s ta tl e a s tav e r t e xz q ，d ( z ) 【量j ； ( b ) f o re a c h 甄一e ，t h e r ee x i s ta tl e a s tav e r t e xy k 4 ，k 4 一e ，d ( ) 【利+ 2 ， t h e ngi sa 3 一o p t i m a l t h e o r e m3 9 l e tgb ea 丸一c o n n e c t e dg r a p h ，a k ( g ) 缸( g ) ，最b ea l la r b i t r a r y c o n n e c t e ds u b g r a p hw i t ho r d e re x a c t l yko fga n duh a se x a c t l ys ( 1 8 k ) n e i g h b o r s i n 最i fd ( u ) 【号j k + 2 s 一1 ，t h e ngi sa 七一o p t i m a l t h e o r e m3 1 1 l e tgb eak c o n n e c t e dg r a p h ，a k ( g ) & ( g ) ，最b ea na r b i t r a r y c o n n e c t e ds u b g r a p hw i t ho r d e re x a c t l yko fga n duh a se x a c t l ys ( 1 8 k ) n e i g h b o r s 7 山东师范大学硕士学位论文 i n 最i fd ( u ) 【刭一k + 2 s 一1 ，t h e ngi ss u p e r - a k i nt h ef o u r t hc h a p t e r ，w ew i l ls h o ws o m es u f f i c i e n tc o n d i t i o n sf o rg r a p h st ob ea 七一 o p t i m a lb yu s i n gn e i g h b o r h o o do ft w ov e r t i c e s ： t h e o r e m4 2 l e tgb eag r a p hw i t ho r d e ra tl e a s t2 k i fi n ( u ) n ( u ) i k + 1 f o re a c hp a i rt ，t ，o fn o n a d j a c e n tv e r t i c e s ，t h e ngi sa 七一c o n n e c t e da n da k ( g ) 缸( g ) d e f i n i t e l e th 1b eag r a p hw i t ho r d e r 【詈j + ia n d - 2b eag r a p hw i t ho r d e r 【詈j if o r0 i k 一1 w ed e f i n eag r a p hf a m i l yg tc o n t a i n i n gi n ( u ) n v ( h 2 ) l 1 a n ds a t i s f m gi h 1 ，日2 】i 【号j + 七一1 ，i n o , ) n v ( h 2 ) i 1f o re a c hv e x t e xu y ( 吼) a n di n ( v ) ny ( h 1 ) i 1f o re a c hv e x t e xt ，y ( 凰) t h e o r e m 4 3 l e t g b e a g r a p h w i t h o r d e r n ( n 2 k ) a n d g 隹g 1 i f i n ( u ) n ( 口) l k + lf o re a c hp a i ru ，口o fn o n a d j a c e n tv e r t i c e sa n d 矗( g ) 【量j + 七，t h e ngi s “一o p t i m a l t h e o r e m4 4 l e tgb eag r a p hw i t ho r d e r 礼2 k ) a n d 最b ea na r b i t r a r y c o n n e c t e ds u b g r a p ho fo r d e rk i fl 0 ) n ) i 七+ 1f o re a c hp a i r 札， o fn o n a d j a - c e n tv e r t i c e s ，a n di fd ( x ) 【刭一七+ 2 s 一1f o re a c hz y ( g ) y ( 凡) h a i n ge x a c t l y 8 ( 2ss k ) n e i g h b o ri nf k ，t h e ng i sk - o p t i m a l i nt h ef i f t hc h a p t e r ，w ew i l ls h o ws o m es u f f i c i e n tc o n d i t i o n sf o rg r a p h st ob ea 七一 o p t i m a lb yu s i n gd e g r e es u mo ft w ov e r t i c e s ： t h e o r e m5 1 l e tgb eaa 七一c o n n e c t e dg r a p ho fo r d e r 礼w i t hk 6 + 1 i fg s a t i s f i e st h ef o l l o w i n gt w oc o n d i t i o n s ，t h e ngi s 札一o p t i m a l ： ( a ) d ( z ) + d ( y ) 2 【号j + 2 s 一5f o re a c hp a i rz ，y v ( a ) w i t hd ( x ，y ) = k 一8 + 1 ， w h e r e 七一1 8 1 ； ( b ) i ft h e r ee x i s t sac o n n e c t e ds u b g r a p hf kw i t ho r d e rks u c ht h a tzi sa d j a c e n tt o e v e r yv e r t e xi nf k ，t h e nd ( z ) 【号j + k 一1 8 一一坐查堕薹盔堂堡主堂垡堡塞 一一 _ _ - _ _ _ _ - _ - _ - _ - _ _ - - _ - - _ 一 t h e o r e m5 3 l e tgb eaa k - c o n n e c t e dg r a p ho fo r d e rnw i t hk 6 + 1 i fg s a t i s f i e st h ef o l l o w i n gt w oc o n d i t i o n s t h e ngi ss u p e r - a k ： ( a ) d ( z ) + d ( 可) 2 鸶j + 2 , - 3 f o r e a c hp a i rz ，y y ( g ) w i t hd ( x ，) = 七一s + l 2 ， w h e r es 之1 ； ( b ) i ft h e r ee x i s t sac o n n e c t e ds u b g r a p hf kw i t ho r d e rks u c ht h a tz i sa d j a c e n tt o e v e r yv e r t e xi nf k ，t h e nd ( z ) 【鸶j + 后 i nt h es i x t hc h a p t e r ，w ew i l ls h o wr e l a t i o n s h i pb e t w e e na 七一o p t i m a l i t ya n ds u p e r - a k t - c o n n e c t e d n e s s t h e o r e m6 1 l e tkb eap o s i t i v ei n t e g e r i fgi saa k - o p t i m a lg r a p hw i t h 622 k 一1 ，t h e ng i ss u p e r - a k tf o ri = 1 ，2 ，k 一1 k e yw o r d s ：g r a p h ；e d g ec o n n e c t i v i t y ；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 ；a k 。 o p t i m a l i t y ；入k - o p t i m a l ；s u p e r - a s ；f a u l tt o l e r a n c e c ：l a s s i f i c a t i o n ：0 1 5 7 5 9 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得 ( 注：如没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或 证书使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意 学位论文作者签名： 芯勃 导师签字：洳，导师签字。孑黼 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅本人授权学校可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 签字日期：2 0 0 9 f 璐勃 年毕月调 - 一字：南砀 签字日期；2 0 0 9 年和2 日 山东师范大学硕士学位论文 第一章引言 目前，互联网络已经与人们的工作、日常生活等方面息息相关网络的可靠性 和容错性是近年来国内外研究的热点之一我们知道，边连通度是反映图的连通性 质的个重要参数而要精确地刻画图的连通性质，它存在着不足之处：首先，边连 通度相同的图可靠度可能不同；其次，不能区分删掉尤个割断点或a 条割断边得到 的图的不同类型，即未考虑对网络的伤害程度；第三，默认图的任何子集中所有元 素能潜在地同时失效为克服以上缺陷，自然要将其加以推广自1 9 8 3 年h a r a r y 1 】 提出条件连通度的概念以来，经过二十多年的发展，条件连通度所涉及的内容日益 丰富和具体，包括超级连通度、过边连通度、限制边连通度等 本文仅考虑有限无向简单图，所使用的记号和术语约定如下，其中未加说明的 部分将在必要时予以阐述或请参照文献【4 2 ，4 3 】设g = ( ke ) 是个图，其中g 的 顶点的个数称为g 的阶，记为i y ( g ) i 或i g i ( 常用n 表示g 的阶) 由s y 导出的 g 的子图记为g s 1 对于每个点 y ( g ) ，u 的所有邻点组成的集合称为口的( 开) 邻域，记为( t ，) 1 v ( v ) u 称为v 的闭邻域，记为t ，的度g ( v ) = i n ( v ) l ，图的 最小度6 = 6 ( c ) = m i n i n c v ) i v y ( g ) ) 对于任意两点t ，缸y ( g ) ，v ，u 之间的距 离记为g ( u ，口) 对于两个点集x ，y y ( g ) ，一点在x 上，另一点在y 上的边的集 合记为，y 】删去后使g 不连通的边集称为边割边连通度a ( g ) 是边割中最小的 阶对于s y 和正整数r ，以n s ( s ) 来表示i v v ：d g ( u ，s ) = r ) ；进一步，占( s ) 简化记为( s ) ， 荡( z ) ) 简化记为( z ) 对于a ，b v ，婀) 三n 7 ( b ) n a 设 f e 和日y ，以h ( f ) 来表示与f 中的边关联的日的点集 设计和分析大规模网络的可靠性和容错性时，通常包括某些类型的图模型，其 中一个重要模型是这样的网络 2 】： 设图g = ( ve ) ，其节点不会失效，每一条边是独立失效的，其失效概率为p 用批( g ) 表示边数为i 的边割的数目，则g 连通的概率r ( g ，p ) 为： e r ( g ，p ) = 1 一fn i ( g ) p ( 1 一p ) 州， 忙a ( g ) 其中是g 的边数，a ( g ) 为边连通度对于一般图确定m ( g ) 是p - 困难的【3 】 b a u e re t 址 4 】提出了最优性的概念，称g 是k 最优的，如果入( g ) = 6 ( g ) ；进一步 1 0 山东师范大学硕士学位论文 如果g 的每个最小边割孤立一个点，g 是超级a 的已经有很多关于a 最优性 和超级性的研究，见文献睁7 】 为了更好地刻画图的连通性，e s f a h a n i a n 和h a k i m i 8 1 提出了限制边连通度的 概念个边割矿e 称为限制边割，如果g u 的每个分支不包含孤立点如果 这样得边割存在，限制边连通度入( g ) 为限制边割中最小的阶，并且称g 为a 7 连通 的，或称g 为入7 连通图他们证明了阶至少是4 的除星尬。一l 外的连通图是a 7 连 通的，并且满足a ( g ) a ( g ) ( g ) ，这里f ( g ) = m i n d g ( u ) + d g ( v ) 一2 ：t 秽e ( g ) ) 是g 的最小边度如果a 7 ( g ) = ( g ) ，称g 是n 最优的若g 的每个最小限制边 割孤立一条边，称g 是超级a 7 的已经有很多关于a 最优性和超级性的研究， 见文献 9 - 2 7 ，叫 令k 是正整数对于连通图g = ( ke ) ，个边割u e 称为b 限制边割，如 果g u 的每个分支至少有七个点如果这样的边割存在，缸限制边连通度a 七( g ) 为舡限制边割中最小的阶，并且称g 为a 后连通的，或称