（系统分析与集成专业论文）几类特殊图的可靠性研究.pdf

南京信息工程大学硕士毕业论文 中文摘要 网络的可靠性作为衡量网络性能的一个重要指标，一直是各国的研究者研究 的热点问题。近年，网络的可靠性理论已经在现实世界中得到了充分的应用， 如计算机系统、通信系统、电力传输系统、交通运输系统等。因此，网络的可 靠性理论在我们现代社会中扮演着举足轻重的作用。 包括上述诸多现实系统都可以用网络( 图) 作为模型进行研究。所谓网络( 图) 是由节点和边组成，其中节点和边是广义的，节点表示系统中的元素，两节点 间的边表示元素之间的相互作用关系。尽管定义看似简单，但是网络( 图) 能 够呈现高度的复杂性。 目前对网络( 图) 的可靠性的研究主要有两种方法。一种方法基于确定性理 论，其基本思想是利用某些被认为合理的参数来衡量网络( 图) 的可靠性。另 一种方法基于概率性理论。本文所采用的是第一种方法。 早期使用确定性理论对网络( 图) 的可靠性的研究主要是针对( 点) 连通 度和边连通度，但随着研究的不断深入，人们发现这两个参数仅考虑了网络( 图) 遭到破坏的难易程度，却没有考虑被破坏的程度。基于此，人们又引入了其它 的一些可靠性参数，其中( 点) 坚韧度和( 点) 粘连度被普遍认为是刻画可靠 性较好的参数。 显然，网络( 图) 的拓扑结构对其可靠性具有至关重要的影响，同时绝大 部分网络可靠性问题都是n p - 难的，在一定程度上不亚于许多标准的组合优化问 题，因此计算出具体特殊图的可靠性参数具有重要的价值。本文在总结现有前 人结论的基础上，计算并证明了几类特殊图的( 点) 坚韧度和( 点) 粘连度。 关键词：网络，图，可靠性，坚韧度，粘连度 南京信息工程大学硕士毕业论文 a b s t r a c t n e t w o r kr e l i a b i l i t y , ak e yf a c t o rt om e a s u r en e t w o r k sp e r f o r m a n c e ，h a sa l w a y s b e e nar i c ht o p i cf o rt h er e s e a r c h e r sa r o u n dt h ew o r l d ，a n di nr e c e n ty e a r s ，i t st h e o r y h a sb e e na p p l i e de x t e n s i v e l yi nm a n yr e a l w o r l ds y s t e m ss u c ha s c o m p u t e ra n d c o n u m m i c a t i o ns y s t e m s ，p o w e rt r a n s m i s s i o na n dd i s t r i b u t i o ns y s t e m s ，t r a f f i ca n d t r a n s p o r t a t i o ns y s t e m se t e t h u s ，n e t w o r kr e l i a b i l i t yp l a y si m p o r t a n tr o l e si no u r m o d e ms o c i e t y m o s tr e a l - w o r l ds y s t e m si n c l u d i n gd e s c r i b e da b o v ec a l lb em o d e l e db yn e t w o r k s o rg r a p h sw h i c ha l ec o m p o s e do fg e n e r a l i z e dn o d e sa n de d g e s ，w h e r en o d e sd e n o t e t h ee l e m e n t sa n de d g e sr e p r e s e n tt h er e l a t i o n sb e t w e e nt w oe l e m e n t s a l t h o u g ht h e d e f i n i t i o no fn e t w o r k so rg r a p h si s s i m p l e ，t h e yc a ns h o wu pe x t r a o r d i n a r y c o m p l e x i t i e s c u r r e n t l y , t h e r ea r et w op r i m a r ym e t h o d so nt h er e s e a r c ha b o u tn e t w o r k r e l i a b i l i t y , o n eo fw h i c hb a s e do nt h ed e t e r m i n a c yt h e o r y 喇也s o n l er e a s o n n b l e i n v a r i a n t sw a sa d o p t e di nt h i sp a p e r , t h eo t h e rg r o u n d e do nt h ep r o b a b i l i t yt h e o r y a tf i r s t ，n e t w o r kr e l i a b i l i t yr e s e a r c h e sw i t hd e t e r m i n a c yt h e o r ym a i n l yf o c l l s e d o nt h ev e r t e x - c o n n e c t i v i t ya n de d g e c o n n e c t i v i t y , b u ta st h er e s e a r c h e sp r o g r e s s i n g a n da d v a n c i n g , p e o p l ef o u n dt h a tt h e s et w op a r a m e t e r so n t yt a k e ni n t oa c c o u n tt h e h a r d n e s st od e s t r o yt h en e t w o r k s0 rg r a p h s ，b u tn o tt h ee x t e n tt ow h i c ht h e yw e r e d a m a g e d t h e r e f o r e , 5 0 m en e wp a r a m e t e r sa n dt h e i rv a r i a n t sw e r ei n t r o d u c e d ，o f w h i c hv e r t e x t o u g h n e s sa n d v e r t e x - t e n a c i t yb e i n gt h o u g h th i g h j y t w ob e t t e r p a r a m e t e r st oe v a l u a t en e t w o r kr e l i a b i l i t y i n d e e d , t h et o p o l o g i c a ls t i l l c t l - l r eo fn e t w o r kd o m i n a t e di t sr e l i a b i l i t y , a n di nt h e w o r s tc a s e ，m o s tn e t w o r kr e l i a b i l i t yp r o b l e m sa l en p h a r d , t os o m ee x t e n tm o r e d i f f i c u l tt h a nm a n ys t a n d a r dc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s ，h e n c ei t s v a l u a b l et od i s c u s sa n dc o m p u t et h er e l i a b i l i t yo fs p e c i a l 伊印h s i nt h i sp a p e r , t h e v e r t e x t o u g h n e s sa n dv e r t o x - t e n a c i t yo f s o m es p e c i a lg r a p h sa r eg i v e na n dp r o v e d k e y w o r d s ：n e t w o r k s ，g r a p h s ，r e l i a b i l i t y , t o u g h n e s s ，t e n a c i t y 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示 了谢意 作者签名：壶玉t 芷 日 期： 1 2 ：兰 学位论文使用授权声明 本人完全了解南京信息工程大学有关保留、使用学位论文的规 定，学校有权保留学位论文并向国家主管部门或其指定机构送交论 文的电子版和纸质版；有权将学位论文用于非赢利目的的少量复制 并允许论文进入学校图书馆被查阅；有权将学位论文的内容编入有 关数据库进行检索；有权将学位论文的标题和摘要汇编出版。保密 的学位论文在解密后适用本规定 作者签名：乞垂生蒸 日期；! 厶：兰f 第一章绪论 1 1 前言 第一章绪论 当今已进入信息时代，随着通信先进技术和设备的不断发展和更新，通信网结构和规 模也日趋庞大和复杂，如若出现传输链路或交换节点的失效将对通信网产生巨大的影响。 因此，有必要对通信网的可靠性进行分析和研究，进而也可以推广到其它各种现实网络系 统中。衡量通信网可靠性的一个重要标准就是网络链路或节点出现故障时是否仍能保证其 继续通信，近年有人研究以通信网断开的难度或程度作为衡量其可靠性的判据，在计算时 将节点和链路的故障分开，并根据其不同的情况进行考虑。通过对系统结构的整体可靠性 进行分析，估计出其中比较脆弱或容易遭到攻击破坏的部位，提前采取一定的技术措施加 强保护：同时需要研究当系统中的元素出现错误或被攻击后出现瘫痪，什么样的系统结构 可以迅速的进行重构，进一步设计出可靠性更高的系统。 由于通信网和其它各系统结构的复杂性，对它们研究第一步需进行抽象并建立精确的 模型，目前常用且直观的方法是采用图来模拟。其中节点和边可以看作是广义的，节点表 示系统中的元素，两节点问的边表示元素之间的相互作用关系。几何图形在欧几里得 ( e u c l i d ) 时代就是数学研究的对象之一，但图作为一门科学，目前公认的是从欧拉( e u l e r ) 所开创的图论学科算起，进入2 0 世纪中叶，s o l o m o n o f f , r a p o p o r t 和e r d 6 s 和r 6 n y i 又引 入了随机图论( 网络) 的概念。伴随着其它各门学科的不断发展，图论的内容和应用也益 发广泛，在计算机科学、社会科学、经济领域、网络理论及控制、交通运输领域等都取得 了广泛的应用，为相关领域的专家技术人员提供了一个强有力的工具。 针对图的可靠性研究，本文主要使用基于确定性理论的方法。人们的早期研究工作主 要是围绕着( 点) 连通度和边连通度，它们仅使用( 点) 割集或边割集的阶作为变量来考 察网络( 图) 的可靠性，目前已在诸多领域中取得了广泛的应用。以分布式网络为例，在 设计时通常采用冗余法来保证其可靠性，通过增加设备的冗余来达到消除链路或节点的故 障。一般情况下，可以采用双连通的方法保证链路或节点故障时使得网络具有改变路由的 能力，也就是保证了当至少存在两条或两条以上的链路( 或节点) 发生故障时网络才中断 工作。由此我们也可以看出网络的拓扑结构对其可靠性是有影响的。 但是，使用( 点) 连通度和边连通度两个参数只能反映出网络( 图) 遭到破坏的难易 程度，却忽略了网络( 图) 遭受破坏的程度。这样就促使人们逐渐引入其它一些可靠性参 数，主要包括离散数、( 点) 坚韧度和边坚韧度、( 点) 完整度和边完整度、( 点) 粘连度和 边粘连度等。由于( 点) 坚韧度是将割集的阶、剩余的分支数综合起来考察图的可靠性， 而( 点) 粘连度参数的定义又增加了剩余最大分支的阶，因此，普遍认为它们是刻画网络 ( 图) 的可靠性较好的参数。研究计算一般图的坚韧度及粘连度是十分困难的，其算法是 n p 难问题，因而现在有人对特殊图类的坚韧度及粘连度进行研究，希望得到这些i 虱在坚韧 度或粘连度下的可靠性度量。 本文首先介绍了上述网络( 图) 的各种可靠性参数，并总结了现有的一些主要研究结 论；然后主要了讨论几类特殊图的可靠性，在前人结论和研究方法的基础上做了进一步的 第一章绪论 研究，计算并证明了它们的( 点) 坚韧度和( 点) 粘连度；最后根据我们的体会，针对这 些可靠性参数可继续研究的问题提出了几点展望。 1 2 文中主要符号 本文所用到的图论概念和术语参照文献 1 ， 的主要记号和符号列举如下： g 、h 等 v ( g ) e ( g ) g i x l ( g ) m ( g ) l ( n e n j ( g ) ( g ) t r c n a u n 2 】，为了清楚与方便，在此将文中所使用 无向，无环，无重边的简单图 图g 的顶点集 图g 的边集 图g 的补图 集合x 的元素个数( 阶) 图g 所含连通分支的个数 图g 最大连通分支的阶数 n 阶完全图 n 阶空图 图g 的最小度数 图g 的最大度数 树 n 阶路 n 阶圈 空集 并运算 交运算 图g 的连通度 图g 的边连通度 图g 的坚韧度 图g 的边坚韧度 图g 的离散数 图g 的完整度 图g 的边完整度 图g 的粘连度 图g 的边坚韧度 不小于x 的最小整数 不大于x 的最大整数 图g 的点色数 图g 的边色数 图g 的独立数 图g 的覆盖数 回回q回回回回回回q州回q回回“h“叫吖，0“吖烈 第一章绪论 1 3 图的可靠性参数的研究现状 1 3 i 图的连通度与边连通度 定义i i 对于连通图g ，定义其点连通度为r ( g ) = h i s i ：s e c ( g ) ，其中c ( g ) 指由图g 的全体点割所组成集合。图的点连通度一般简称为连通度。 定义1 2 对于连通图g ，定义其边连通度为2 ( g ) = r a i n i s i ：s 。e c ( g ) ，其中c ( g ) 指由图 g 的全体边割所组成集合。 在对图的可靠性研究方面，早期主要是围绕着图的连通度和边连通度这两个参数。相 对于其它的脆弱性参数来说，目前对它们研究的较为成熟，并且已经证明，一个图的连通 度和边连通度具有多项式算法。这里简单介绍关于它们的一些主要结论。 引理i i ”1 ( w h i m e y , 1 9 3 2 ) 对于一个图g ，有r ( g ) 2 ( g ) s 8 ( g ) 。 引理1 2 “目一个阶大于等于3 的图g 是2 一连通的，当且仅当g 的任意两个顶点至少由两 条内部不相交的路所连。 引理1 3 阻”( m e a g e r 定理) 一个阶大于等于k + 1 的图g 是k 连通的，当且仅当g 的任意 两个相异顶点至少被k 条内部不相交的路所连。 引理1 4 “( h 硝y ，1 9 6 2 ) 对于所有包含p 个顶点q 条边的图g ，有 f0 0 q 3 时，轮图w n 不是完全图，因此s 不是轮 图w 。的一个割集，这与坚韧度的定义相矛盾，故假设不成立。一 性质2 3 设点集s 是轮图w 。( n 3 ) 的一个f 一集，则s 中不含有c 。中的相邻节点。 证明：若s 是轮图w 。的一个t 一集，假设s 中包含c n 中的相邻节点。 ( 1 ) 若 v i ，v i + l ) c s ，现在重新构造点集s 。= s 一 v i + l j ，则有 s 。1 = i s l - 1 ，( 、n s ) ( w n s ) ，所以有r ( s 卜二i s 莉i s i - ic ；i 丽i s f = r ( s ) ，这与坚韧度的定义相矛盾； ( 2 ) 若f v ，v i + l ，v i + 2 ，) c s ，现在重新构造点集s j - s f v i 一- ! ) ，则有i s = i s | - 1 ， ( w r s ) ( w 。一s ) ，所以有r ( s 。) = 面丽i s l磊i 丽s l - t 面i i i s j l 两= r ( s ) ，这与坚韧度的定 义相矛盾。 因此，假设不成立。故点集s 中不含有c n 中的相邻节点。 性质2 4 设点集s 是轮图w 。( n 3 ) 的一个t 一集，那么w 。一s 的分支中不含长度大于2 的路。 证明：若点集s 是轮图w 。的一个f 一集，由性质2 2 知，、n s 的所有分支都是圈c n 的子图，因此以下的讨论可限于圈上。假设w 。一s 的分支中含有k 条“1 ) 长度大于2 的 路，不妨分别记为p 1 ，1 , 2 ，p k ，其中p i ：v i v i + 1 v ，c c 。，n = o ( i j ) 。现 - l o - 第二章轮图的可靠性研究 在重新构造点集s = s uf v ”1 ，v 2 - 1 ，v ”1 ，则有i s 卜s f 咄，( w 。一s ) = ( w 。一s ) + k ， 所以有r ( s 。) = 面丽i s l= 面丽 s 丽l + k 5 面面i s 两l = r ( s ) ，( 根据引理2 1 ) 这与坚韧度的定义 相矛盾故假设不成立，因而w 。一s 的分支中不含长度大于2 的路。一 性质2 5 设点集s 是轮图w 。( n 3 ) 的一个t 一集，那么w 。一s 的连通分支中最多有一个含有 两个顶点。 证明：若s 是轮图、n 的一个t 一集，假设w 。一s 中有两个连通分支含有两个顶点，不 妨分别记为琏= v m 。砑= q v ，“，不失一般性，设j i + 3 。设在睢l 与峙之间的顶点有r 个在w 。一s 中，由性质2 4 知它们都是w 。一s 中的只有一个顶点的连通分支k l ，记为 x = 似，t ，喝。由于在c 。中从i 到v j 构成一段路，因而在v + l 与、j 之间至少有什1 个 顶点r ； v ；，巧，“ 属于s 。现在重新构造点集s = s u ( i ，v i + 3 ，v ，岣- 2 ，、3 卜 v 眈， v i + 4 ，v j i ，显然1 s i i s l + 1 ，( w 。一s ) ( w n - s ) + l ，所以有 r ( s ) = 面毋丽d w i s + 母z l5 面鬟：荀= r ( s ) ，( 根据引理2 1 ) 这与坚韧度的定义相矛盾，故 假设不成立。一 若w 。一s 中有两个以上的连通分支含有两个顶点。则可两两按照上述方法推出矛盾。 所以，如果w j s 中含有奇数个k 2 ，则最终w 。一s 中含有一个k 2 ，其余分支均是k l 若 w 。一s 中含有偶数个k 2 ，则最终w 。一s 中仅包含分支k i 。 i 型兰，沩偶数时 定理2 2 对于任意轮图w 。( 1 l 3 ) ，f ( ) - - t ? ， 1 兰兰，l 为奇数时 l 一一1 证明：对于任意轮图w 。( n 3 ) ，继续采用性质2 1 中顶点表示方法进行描述。 ( 1 ) 确定轮图w 。( n 3 ) 的坚韧度的上界 当1 1 为偶数时，取点割集s = v o t j 、| ：【= l i n ，i 为奇数 。容易得出l sr = i + 导， 烈形心户三， 当n 为奇数时。取点割集s = f v o uf v i ：l i n ，i 为偶数 。容易得出蚓= l + n f - 1 咝。 生； 蝌丽 第二章轮图的可靠性研究 口( 孵焉产婴， 所以哪s 丽7 s l = 等= 岩 一l 故有“呒) 5 n 为偶数时 n 为奇数时 ( 2 ) 确定轮图w o ( n 3 ) 的坚韧度的下界 由性质2 4 2 5 可知，对于轮图w 。的任一坚韧集s ，w 。一s 只有两种类型的分支k l 与 k 2 ，要么每个分支中只有一个顶点，要么在所有分支中只有一个是k 2 ，其余的只有一个顶 点。但当r l 为偶数时。若w - s 含有一个k 2 分支，则点集s 中必然至少含有一对相邻的节 点，由性质2 3 知这种情形是不存在的，因此当n 为偶数时w 。一s 中仅含有k l 。下面分别 讨论： 当n 为偶数时，轮图w n 的任一p 集s 必满足罔2 l + i i n l ，“形固s l 引，此时有 f ( s ) = 忐2 疗+ 2 刀 当n 为奇数时。w 弗中最多只有一个k 2 ，任一t 一集s 必满足闷l + 陧 ， d 形固s l ? j + - ，此时有r ( s ) = i 高兰面 故有“呒) 由( 1 ) ( 2 ) 定理得证。一 曲偶数时 ，沩奇数时 疗+ 1 月一1 2 2 剖分轮图的坚韧度 定义2 1 一次剖分轮图w n 指的是对轮的缘边一次剖分所得的图，二次剖分轮图w 啦是在 一次剖分轮图上再对缘边剖分所得的图。 定理2 3 对于任意的一次剖分轮图w 4 “f 1 。但由上述知“呒1 ) 的上界为 生，比此时所得的旦旦要优的多，因此中心顶点v 0 不属于集合s 。 现在已知v o w s ，下面证明坚韧集s v o ，v 0 ：一，v = 。 情形h 若向s 中添加一个点v ( 1 i n ) 时，有s = q ，v ：0 ，v = ，v i ，易得i s i = ) s i + i 。 ( w 。- 一s 。) ；( w 珥- 一s ) 一l ，所以有r ( s = 鼎= 云i i i s i + 丽i 二高詈丽= r ( s ) ； 情形2 。 若从s 中减去一个点v o ( 1 i n ) 时，有s v 吁0 k 0 。，啦i ，v 。0 ，易得 旧i = 一1 ，( w 。一s ) = ( w q ，一s ) - 2 ，所以有f ( 印= 二热= i 筇i s ：t 丽q 忐= r ( s ) ， ( 因为( w 。l s ) 面器f ( s ) ： ( 2 厢妣有( 眦i - s ) 铷( ，3 放s ) = ：高b = 丽i s l 二接两= f ( s ) ： - 1 3 第二章轮圈的可靠性研究 总之，无论何种情况，总有r ( s i ) r ( s ) ， 由坚韧度的定义知 识。) - f ( s ) = 鼎一n + l 。一 r 、v f 圈2 - 2 一次羽分轮圈w “田2 - 3 二厌翻分稻田w t a 定理2 4 对于任意的二次剖分轮图w 啦，f ( ，z ) = i 备。 证明：设v ( 睨：) - n 讳v ：，v = ，v ：，畦一，t ，曰，吒t ，订，嵋，t ，其中v o 表示中心顶点，v ? ( 1 i n ) 表示原轮图上的顶点，v ( 1 j n ) 表示进行一次剖分产生的 顶点，q 及t ( 1 i n ) 表示进行二次剖分而新产生的顶点。 我们可以简单构造一个点割集s = 订，v o 一，v 。0 ) ，则有 s i = n ，c o ( w 啦- s ) - - n + i ，所以 f ( ，2 ) 鲁。假设中心顶点v o e s ，则w 面- v o 为一个4 n 阶的圈，此时可参照轮图w n 珂+ i 坚韧度的讨论，易得出“d = 三笔n 兰 l 。但由上述知“睨，。) 的上界为r 南l ，比此时所得 z 十l 的罢出要优的多，因此v 。岳s 。 下面证明坚韧集s - v o ，v o 一，v ：) 。 情形i ； 若向s 中添加一个点v ：或v i 或订( 1 i n ) 构造出s ，有i s t l = i s i + 1 ， ( 1 ) 著s kst j( v 1 ) ，易得m ( w 啦一s i ) = ( w 啦一s ) + l ，所以 f ( s ) = 袋鬲= 煮薪，忐叫s ) ，( 因删- s ) 郴h 1 4 - 第二章轮图的可靠性研究 ( 2 ) 若s suf 或s ksu ，易得( w j s ) 铷( w 啦一s ) ，所以有 f ( s ) = 忐= 糟忐_ f ( s ) ； 情形2 ； 若从s 中减去一个点v o ( 1 i n ) 构造出s 。，易得f s | = i s | 1 ， ( w 如一s ) 铷( 断s ) - 2 ，所以有r ( s ) = 葫丽i s l= 石鬲 s ：l - i i 汪 二丽i s l = r ( s ) ，( 因为 ( w n s ) 3 ) 的一个t 一集，则必有v o s 。 证明：若s 是轮图w 。的一个t 一集，假设仨s 。由轮图的定义可知，w 。一s 是一个 连通子图。重新构造点集s = s u v o ，则i s i ：s i 十1 ，m ( w 。一s ) m ( w 。一s ) - l ，( w 。一s ) ( w r s ) ，所以有s c ( s = i s l 丽+ 瓦k i w ：i r - s d s + t + 丽m i ( w ：i 厂- s ) - i = 号：；：挈= s c ( s ) 。这与粘连 数的定义相矛盾，故假设不成立。 1 5 第二章轮图的可靠性研究 性质2 7 设s 是轮图w 。( n 3 ) 的一个1 。集，那么w 。一s 的分支中不含长度大于2 的路。 证明：若s 是轮图w 。的一个t 一集，即s c ( s ) = t ( w n ) ，由性质2 6 知，w 。一s 的所有分 支都是圈c n 的子图，因此以下的讨论可限于圈上。假设w 。一s 的分支中含有k 条( k 1 ) 长 度大于2 的路，不妨分别记为p 1 ，p 2 ，p k ，其中p = v l ，1 矿2 ，p 1 c 。重新构造 点集s i su v 1 “，p 1 ，1 ，则有s h s l 收，m ( w n s ) m ( 砜一s ) 一2 ， 抵- s f 煳( w - s ) + k ，故瓯s ) = 哚警 3 ) 的一个t - 集，那么w 。一s 的连通分支中最多有一个含有两个 顶点。 证明：若s 是轮图w 。的一个1 。集，假设w 。一s 中有两个连通分支含有两个顶点，不 妨分别记为琏= v v f 。霹= b v ，“，不失一般性，设j i + 3 。设在v h l 与v j 之间的顶点有r 个在w 。一s 中，由性质2 7 知它们都是w 。一s 中的只有一个顶点的连通分支k i ，记为 x = v ：，k 2 ， 。由于在c 。中从l 到、j 构成一段路，因而在i 与v j 之间至少有什1 个顶点y = v ：，口，v ，+ i 属于s 。重新构造点集s = s uf l ，v i * 3 ，v i e s ，叼- 2 ，、3 ) 一 v i - 2 ， v i + 4 ，m 1 ) ，显然i s | 1 s l + 1 ，( w 。一s 。) ( w n s ) + l ，m ( w 。一s ) m ( w 。- s ) ，所以 有s c ( g ) ：l 堕：；受导s 盥尘! q 翌受 3 ) ，烈职) 。 n + 4 为偶数 n 堂劝奇数 刀一l 证明：对于任意轮图w 。，继续采用性质2 1 的顶点表示方法进行描述。 ( 1 ) 确定轮图w 。的粘连度的上界 当n 为偶数时，构造点割集s = f v 0 u v i ：l i n ，i 为奇数 容易得出蚓2 l + ；， 耐忡矿n c w n s h ，所以哪s s c ：等：半：警 - 1 6 - 第二章轮图的可靠性研究 当n 为奇数时，构造点割集为s = v 0 u ( v i ：l i n ，i 为偶数 。容易得出同= l + 了n - 1 以形 产孚毗宅，所以唧啦：嗡紫：訾n - 1 ：等； 故有烈呒) 5 n + 4 ，沩偶数 月 盟砌奇数 n i ( 2 ) 确定轮图w 。的粘连度的下界 由性质2 6 2 8 可知，对于轮图w 。( n 3 ) 的任一粘连集s ，w 。一s 只有两种类型的分支 k l 与k 2 ，要么每个分支中只有一个顶点，要么在所有分支中只有一个是k 2 ，其余的只有 一个顶点，下面分别讨论。 当m ( w r s ) = l 时，轮图w 。的任一t - 集s 必满足蚓l + 陪1 ，烈呢- s ) s 【刊，此时 孰( s ) = 糟 n + 4 n 为偶数 刀 n + 5 月为奇数 ”- 1 当m ( w n s ) = 2 时，w 丑- s 中f t 有- - + k 2 ，任- - t - 集s 必满足罔1 + 陧 ， 嘶哪吲“此怖c ( s ) = 等2 故有烈形) 2 n + 4 h 为偶数 一 堕础奇数 一一l 由( 1 ) ( 2 ) 定理得证。 2 4 剖分轮图的粘连度 定理2 6 对于任意的一次剖分轮图w 。1 ，“呒- ) = 1 。 证明；继续采用定理2 3 中顶点表示方法。 ( 1 ) 确定一次剖分轮图w 。1 粘连度的上界 可构造一个点割集为弘 v o ，e 一- ，v 。0 ，容易得出i s l = n ，m ( w 。a s ) = l ， - 1 7 - 砌偶数 砌奇数 坐。堕“ ，。【 第二章轮图的可靠性研究 ( 吣s m ，所以矾1 ) 1 3 ) 的一个t 一集，则必有v 0 s 。 证明：若s 是扇图f 丑的一个t 一集，假 殳v 。g s 。由扇图的定义可知，f 且一s 仍是一个 连通子图，即r ( s ) 2 ；苦葛。斟。又因为当n 3 时，扇图f n 不是完全图，因此s 不是扇 图r 的一个割集。这与坚韧度的定义相矛盾，放假设不成立。一 性质3 j 设点集s 是扇图f n ( n 3 ) 的一个t 一集，则s 中不含有p n 中的相邻节点。 证明：若s 是扇图f 。的一个t 一集，假设s 中包含p n 中的相邻节点。 ( 1 ) 若( v i ，v i ，l c s ，重新构造点集s = s 一 v i - 1 ) ，则有s l = l s i - 1 ，( f u - s ) ( f 。- s ) ， 所以有r ( s ，= 五；i s i l 酉5 二i 刁s 两i - 1c ：趸i j s ：l 酉= r ( s ) ，这与坚韧度的定义相矛盾； ( 2 ) 若 v i ，v i + l ，v i + 2 ，) cs ，重新构造点集s t - s 一 1 ) ，则有l s 1 = i s 卜l 。 ( f n s ) ( f 一s ) ，所以有r ( s ) = 倒旺i s l s ，；i 西s l ：- ：两 ( 石五j s 孓l 爵= r ( s ) ，这与坚韧度的定义 相矛盾。 因此，假设不成立，故点集s 中不含有p o 中的相邻节点。一 性质3 4 设点集s 是扇图f 。( n 3 ) 的一个t 一集，那么f o - s 的分支中不含长度大于2 的路。 证明；若点集s 是扇图f n 的一个t 一集，由性质3 2 知，f u - s 的所有分支都是路 的 子图，因此以下的讨论可限于路上。假设f 。一s 的分支中含有k 条( k 1 ) 长度大于2 的路， 不妨分别记为p 1 。p 2 ，p k ，其中p i = v v + 1 v ”，p 。c - 只，一n = a ( i j ) 。现在重 - 1 9 - 第三章扇图的可靠性研究 新构造点集s = s 1 3 v ，v ，v “ 。则有l s l = i s + k ，( r s ) = ( f n - s ) + k ，所以有 r ( s ) = 面掣两= 及而i s t + k5 莉i s l = r ( s ) 。( 根据引理2 1 ) 。这与坚韧度的定义相矛盾， 故假设不成立，因而r s 的分支中不含长度大于2 的路。一 性质3 5 设点集s 是扇图f m ( n 3 ) 的一个t 一集，那么f - s 的连通分支中最多有一个含有 两个顶点。 证明：若s 是扇图f n 的一个t 一集，假设f n s 中有两个连通分支含有两个顶点，不妨 分别记为琏= u 坼+ l ，砭= v j v j “，不失一般性，设j 1 i + 3 。设在l 与m 之间的顶点有r 个在f 。一s 中，由性质3 4 知它们都是f - s 中的只有一个顶点的连通分支k l ，记为 z = 似，v ： 。由于在p n 中从l 到m 构成一段路，因而在l 与m 之间至少有什1 个顶点y = 哆，谚，“ 属于s 。现在重新构造点集s = s u ( l ，v ，h ”，、j 。，峙卜 v ， v i - , 4 ，m 1 。显然l s i i s i + i ，( f n s ) c o ( f , - s ) + l ，所以有 r ( s = 云桀两玉丽s l + t5 面晕爵= r ( s ) ，( 根据引理2 1 ) 。这与坚韧度的定义相矛盾，故假 设不成立。 若f - s 中有两个以上的连通分支含有两个顶点，则可两两按照上述方法推出矛盾。所 以。如果f n s 中含有奇数个k 2 ，则最终f - s 中含有一个k 2 ，其余分支均是k t ；若f n - s 中含有偶数个k 2 ，则最终f , - s 中仅包含分支k l 。 定理3 1 对于任意扇图f 。( n 3 ) ，“e ) = 1 。 证明：对于任意扇图f 。( n 3 ) ，继续采用性质3 1 的顶点表示方法进行描述。 ( 1 ) 确定扇图r ( n 3 ) 的坚韧度的上界 当n 为偶数时，取割集s = l v o ) u v i ：1 i 3 ) 的一个t 一集，那么f n s 的分支中不舍长度大于2 的路。 证明：若s 是扇图f 。的一个t - 集，由性质3 6 知，f n - s 的所有分支都是路p n 的子图， 因此以下的讨论可限于路上。假醍f n s 的分支中含有k 条( k 1 ) 长度大于2 的路，不妨分 别记为p 1 ，p 2 ，p ，其中p i = v i v “v 心，p ，只现在重新构造点集s k su v “1 ， v 2 + l ，v 。则有i s | ：1 s 【+ k ，m ( f n - s ) m ( r s ) - 2 ，m ( f n s ) 硇( f n - s ) + k ，所以有 第三章扇图的可靠性研究 郇) = 甓篡擎s 甏骞罟t 絮喾c 甓等刮她与粘连数的舣衍盾，砥固珉命k 哦- s 肚珉固一。”一 个项点】，= b ，哆，1 属于s 。现在重新构造点集s = s u w i ，v ，v i + 矿，m ，m 卜 v ， s c ( s ) ：i ；署挈s 型；：；! 蓦墅c 埋! ! 坠翌：s c ( s ) 。这与粘连数的定义相矛盾，故假设不o 、7 孵。o 习砥固十1 k t n - s )一r r 7 一峨腻“，。 啦弦攥：蔫= ； 2 3 第三章扇图的可靠性研究 当n 为偶数时，构造点割集为s ： v o ) u 1 i l l ，i 为偶数 。容易得出= 1 + 了n - 2 ， 峨 产j n 川耻。心所以呻妇( s ) ；筹：丁i + - n 2 - 2 - + 2 ：i n + 4 ； 当n 为奇数时，构造点割集为s = v o uf v i ：l i n ，i 为偶数 。容易得出斟= 1 + n 2 - j 删产了w l - i m ( 瞬- ，所以删蛾( s ) = 糍乎= 等1 = 鲁； n 一 故有烈e ) 由( 1 ) ( 2 ) 定理得证。一 n 为偶数 硇奇数 3 4 剖分扇图的粘连厦 定理3 5 对于任意的一次剖分扇图f 曲烈e 。t ) = 专 。 证明：继续采用定理3 2 中顶点表示方法。 ( 1 ) 确定一次剖分扇图f 。l 粘连度的上界 可取点割集s ； v o ，v 0 ：，v 0 。) ，容易得出 s ：n ，m ( k l - s ) = 1 ，( f q i s ) = 旷1 + l = n ， 所以吲蛾( s ) = 错= 等； ( 2 ) 确定一次剖分扇图f 皿l 粘连度的下界 可以找到一次剖分扇图氏i 的一条h a m i l t o n 路匕q 。v ? v t v ：v v k v ：，又因为图g 的 支撑子图的粘连度必小于或等于它本身的粘连度，故有烈c 1 ) 烈如) 。结合引理1 2 4 得 ( 矗。) 1 2 n f + 2 = 了n + l 。 由( 1 ) ( 2 ) 定理得证。一 定理3 6 对于任意的= 次剖分扇图f 啦，烈2 ) = 丽2 n - 2 4 - 甘l 。盟川，tlllll 第三章扇图的可靠性研究 证明：继续采用定理3 3 中顶点表示方法。 ( 1 ) 确定二次剖分扇图f 吐枯连度的上界 可取点割集扣 v 口，v o ，v ：，v ：，t ，0 ，容易得出：s i = 2 n - l ，m ( f l - s ) = 1 ， 岷r s ) 2 ( n 1 ) 悄n 所岍删妇( s ) = 智= 掣= 盎； ( 2 ) 确定二次剖分扇图f 吐粘连度的下界 可以找到二次剖分扇图f 啦的一条h a m i l t o n 路只窜v o m 0 v 。2 v 1 1 q e v o - i i 吐t l v ：，又 因为图g 的支撑子图的粘连度必小于或等于它本身的粘连度，故有r ( 疋2 ) 烈只。- 2 ) ，再 由引理l 以得“疋，。) ( 4 石n - 丁2 ) + 2 = 丢备。 由( 1 ) ( 2 ) 定理得证。 推论3 2 对于k 次割分