（应用数学专业论文）图的容错直径与宽直径及超立方体的（dk）独立数的研究.pdf

中国科学技术大学硕士毕业论文 中文内容摘要 计算机互连网络的拓扑结构是图，图论是设计和分析计算机网络的一个基本 而又重要的数学工具容错直径d 。、宽直径d 。都是度量互连网络可靠性和有效 性的重要参数对于一般的图g ，确定它的容错直径d 。困难很大，而确定它的宽 直径d 。却是个n p c 问题，因此讨论它们之间的关系显得很重要对任何k 连通 图，它的容错直径d 。不超过宽直径d 。到目前为止，关于容错直径与宽直径关 系的结果很少本论文证明了： 当g 为2 连通图时，d 2 4 ) 或者d = k - 1q 6 ) ：以及岱d * ，( g ) = g g d , k ( g ) ，其中。董f k 一2 ， i d t t 1 。 关键词：计算机互连网络，图，连通度，容错直径，宽直径，超立方体网络 ( d , k ) 独立数 中国科学技术大学硕士毕业论文 s t u d y o nf a u l t t o l e r a n td i a m e t e ra n d w i d ed i a m e t e ro f g r a p h s a n d ( d ，后) - i n d e p e n d e n c en u m b e r so f h y p e r c u b e a b s t r a c t g r a p ht h e o r yi sa f u n d a m e n t a la n dp o w e r f u lm a t h e m a t i c a lt o o lf o rd e s i g n i n ga n d a n a l y z i n g i n t e r c o n n e c t i o nn e t w o r k s ，s i n c e t h e t o p o l o g i c a l s t r u c t u r eo fa n i n t e r c o n n e c t i o nn e t w o r k sc a nb em o d e l e db yag r a p h t h ef a u l t - t o l e r a n td i a m e t e r d i a n dt h ew i d ed i a m e t e rd a r et w oi m p o r t a n tp a r a m e t e r sf o rm e a s u r i n gr e l i a b i l i t ya n d e f f i c i e n c y o fa ni n t e r c o n n e c t i o nn e t w o r k i ti sv e r y d i f f i c u l tt od e t e r m i n et h e f a u l t - t o l e r a n td i a m e t e r 坟f o ra n yg r a p h ，a n di ti sa nn p cp r o b l e m t od e t e r m i n et h e w i d ed i a m e t e r d i f o ri t s o ，i tb e c o m e sv e r yi m p o r t a n tt od i s c u s sp r o p e r t i e sb e t w e e n t h e m i ti sw e l lk n o w e nt h a tf a u l t t o l e r a n t d i a m e t e r d i d o e sn o te x c e e dw i d e d i a m e t e r d f o ra n y k - c o n n e c t e dg r a p h ，b u tw eh a v ek n o w nv e r yf e w r e s u l t sa b o u t f a u i t - t o l e r a n td i a m e t e ra n dw i d ed i a m e t e r t h i sp a p e rs h o w st h ef o l l o w i n g r e s u l t s i fgi sa2 - c o n n e c t e dg r a p ht h e n d ： m a x ( d 1 ) ( 。：一兰一1 ) + l ，d ：+ 1 ) a n das u f f i c i e n ta n dn e c e s s a r yc o n d i t i o ni sa l s og i v e nf o rd 2 = d 2 + l ：d 2 = 3 o r4a n d t w ov e r t i e sw h o s ew i d ed i s t a n c eb e t w e e nt h e mr e a c h e sd 2 m u s tb ea d j a c e n tt oe a c h o t h e r i f d = 2 ， i fgi sa3 - c o n n e c t e dg r a # ，t h e n 以s m a x ( d 2 一1 ) ( d 3 一互1d 2 一1 ) + l ，3 b 一5 ，d 3 + l f o r d = 2 ；以 l ，则称 ，为g 的独立集( i n d e p e n d e n c es e t ) g 中独立集的全体记为，( g ) 定义参数 口( g ) = m a x 1 1 1 ：，( g ) ) 为g 的独立数( i n d e p e n d e n c en u m b e r ) 顶点数目为口( g 的独立集称为最大 的独立集( m a x i m u mi n d e p e n d e n c es e t ) 无向图称为二部分i t ( b i p a r t i t e g r a p h ) ，如果g 的顶点集有二部划分z 和y 使 得石中任何两顶点之间无边相邻且y 中任何两顶点之间也无边相邻， 肖，r ) 称为 二部划分( b i p a r t a t i o n ) 设g = ( v ，e ) 是无向图，在v ( g ) 上定义一个二元关系尺：对x 、_ y 矿( g ) ， x r y 铮存在o e a u t ( g ) 使得y = 口( 砷若x r y ，则称x 和y 是相似的 3 巾国科学技术大学硕士毕业论文 ( v e r t e x - s i m i l a r ) 若图中任何顶点之间都是相似的，则称该图是点可迁的 ( v e r t e x - t r a n s i t i v e ) 笛卡尔乘积图是重要的图论运算，也是构造互连网络的重要方法若 g 。= ( k ，e ，) 和g ：= ( k ，e ：) 是两个无向图，g 。、g ：的笛卡尔乘积是一个无向图， 称为笛卡尔乘积图( c a r t e s i a np r o d u c t g r a p h s ) ，记作g 1 g 2 ，其中 v ( g 。g ：) = _ 吃；两个不同的顶点x i x ：和y t y ：在g 。g ：中相邻咎或者 一= y ，且x ：和y ：在g ：中相邻，或者x 2 = y 2 且x i 和“在g 。中相邻笛卡尔乘积 图的许多重要性质能在文献【2 】的第二章中找到，这里不一一罗列 设x 和y 是图g 的两个不同顶点若g 中两条路只、p 2 除了它们端点以外， 没有相同的顶点，则称p l 和最是内点不交的( i n t e r n a l l yv e r t e x - d i s j o i n t ) g 中内 点不交的( x ，y ) 路的最大条数记为先( x ，y ) ：类似的可阻定义边不交的( i n t e r n a l l y e d g e - d i s j o i n t ) ，g 中边不交的( x ，力路的最大条数记为q g ( x ，y ) 若存在一个非空子集s v ( a ) ( x ，y 使得g s 中不存在0 ，y ) 路，则称s 为g 中( x ，y ) 分离集( s e p a r a t i n gs e 0 具有最少顶点数的( x ，y ) 分离集称为最小 ( x ，y ) 分离集最小( x ，力分离集的顶点数记为k - 。( x ，y ) 若存在一个非空子集 b e ( g ) 使得g b 中不存在( x ，y ) 路，则称曰为g 中( x ，y ) 截集( c u ts e 0 具有最 少边数的( z ，y ) 截集称为最小( x ，y ) 截集最小截集的边数记为砧( 墨y ) 设g 是连通的无向图，若存在非空集s c v ( g ) 使得g s 不是连通的，则称 s 为g 的分离集具有最小顶点数的分离集称为最小分离集，简记为r 分离集最 小分离集中的顶点数记为k ( g ) ，它定义为g 的连通度( c o n n e c t i v i t y ) 若存在非 空集b e ( a ) 使得g b 不是连通的，则称b 为g 的截集具有最小边数的截集 称为最小截集，简记为 截集最小截集中的顶点数记为 ( g ) ，它定义为g 的 边连通度( e d g e c o n n e c t i v i t y ) r ( g ) k ，则称g 是t 连通图：若 ( g ) k ， 则称g 是t 边连通图显然若g 是女连通图，则对任何正整数，( 1 ，后) ，g 是 f 连通的 中国科学技术大学硕士毕业论文 若g 中以x 为端点的边集记为e 。( z ) ，d o ( x ) = i e 。( x ) i 称y , jx 的项点度 ( v e r t e xd e g r e e ) 顶点度为d 的顶点称为d 度点每个顶点都是d 度点的图称为 d 正则( r e g u l a r ) 图 a ( g ) = m a x d g ( x ) ：x 矿( g ) ) 和 6 ( g ) = m i n d g ( x ) ：x 矿( g ) 分别称为g 的最大顶点度和最小顶点度 三、主要引理 关于图的连通性有下面三个最著名的基本定理，它们的证明在任何一本图 论教科书中，例如在文献【1 的第三章中能够找到这三个定理也是本论文主要结 果论证的基础我们在这里把它们叙述为引理 引理l _ 1m e n g e r 定理 设z 和y 是g 中不相同的两个顶点，则 ( 1 ) r o ( x ，y ) = 九( x ，y ) ； ( 2 ) 先( x ，y ) = 茁g ( x ，y ) ，如果( x ，y ) e ( 6 ) 判定一个给定的图是否是k 连通的或者k 边连通的，有下面著名的m e n g e r w h i t n e y 判定定理 引理1 2 对任何连通图g ，如果阶数大于k ，那么 ( i ) g 是t 边连通的静r g ( x ，y ) = 砧o ，y ) 对g 中任何两顶点x 和y 成立； ( 2 ) g 是k 边连通的( z ，y ) = ( x ，y ) 对g 中任何两顶点x 和y 成立 m e n g e r 定理和m e n g e r w h i t n e y 判定定理是互连网络拓扑结构设计和可靠 性、容错性分析的基础，同时也是图论中用得最多的基本结果，它深刻揭示了图 的结构特征，是图论中关于连通度理论的核心，特别是在并行互连网络的设计、 研究和分析中越来越发挥它的重要作用它们在互连网络设计和分析中的应用请 参见文献【2 】的第四章 关于连通图的连通度、边连通度和最小度之间有如下关系( w h i t n e y 不等式) ， 它是证明有关连通度结论的基础： 引理1 3 对任何连通图g ，有l 蔓r ( g ) 五( g ) 占( g ) 本文用到的其它有关图论术语、记号和结论，请参看文献【l 】有关互连网 络方面的概念和结论，请参加文献【2 】这里不一一列出 中国科学技术大学硕士毕业论文 第二章连通图的容错直径与宽直径 第一节引言 一、容错直径和宽直径及其定义 若图的连通度为k ，则表明对应的互连网络可以容许k 一1 个结点同时发生故 障而不会导致剩余子网络中各结点之间的通信，它表明网络能容忍同时失灵处理 器的最大数目因此，连通度是图论中最基本而又最广泛的概念，是度量互联网 络传输延迟和可靠性的重要参数 网络的容错性( f a u l t t o l e r a n c e ) 是指在网络结点和( 或) 连线可能发生故障的 情况下的数据传输可靠性在这种意义下，对于一个给定的互连网络，最多能容忍 多少个结点和( 或) 连线同时发生故障而剩余的子网络中各结点之间还仍能继续 保持通信互连网络的容错性是评估网络性能的重要概念，高容错性的互连网络 一直是网络设计者追求的重要目标之一网络的容错性与图的连通度也有密切关 系 g 的连通度符( g ) 是分离g 所需的最小顶点数目若g 是k 连通的，则由著名 的m e n g e r 定理知，对于g 中任何两个不同的顶点z 和y ，g 中存在至少k 条内部 点不交的( x ，y ) 路图的这一性质表明，当网络的传输带宽有限时为加快数据传 输人们可以首先将需要传输的数据包拆成k 个小包然后沿k 条内部点不交路 分别同时传输 在容错网络中，结点或连线的失灵会导致数据传输延迟的增加，因此还采用 拓扑结构图的直径来度量传输延迟显然是不准确的而且在容错网络中，哪些结 点或连线的失灵是随机的，事先是不知道的为了准确地度量容错网络中的数据 传输延迟，k r i s h n a m o o r t h y 和k r i s h n a m u r t h y 3 1 提出了重要的图论概念容错 直径( f a u l t t o l e r a n td i a m e t e r ) 定义2 1 设g 是一个k 连通图则对任何子集f c v ( a ) ，如果i f i k ，那么 g f 是连通的，即g f 的直径a c g f ) 是确定的g 的k l 容错直径d 。( g ) 定义为 b ( g ) = m a x d ( g f ) i v f c 矿( g ) ，i f l k ) 由容错直径的定义知，使得d k ( g ) = o o 的点故障f 的元素个数l f i 最小值等 中国科学技术大学硕士毕业论文 于ge p n , a x 和y 的连通度r ( g ) 由m e n g e r 定理和w h i t n e y 判定准则知，嘎( g ) 有一个有限值当且仅当g 是k 连通的当故障集f 时，d ，( g ) = d ( g ) 因此 容错直径的概念是经典直径和连通度概念的结合和推广容易看出，d 。( g ) 是有 限值，则 d i ( g ) = m a x d ( g f ) i v f v ( g ) ，i f k i ) 由定义，易知 d ( g ) = d ，( g ) 兰d 2 ( g ) s d 女一l ( g ) d ( g ) 毫无疑问，用容错直径来度量容错网络中数据传输延迟是恰当的网络的容 错直径与直径的差距可能是很大的，也可能是相等的对于容错直径与直径相等 的网络，结点或连线的失灵不影响数据传输延迟，它当然是比较理想的网络但 般的网络，容错直径总是比直径大，甚至大得多数据在容错直径和直径相差 比较大的网络中不能有效地传输，理想地容错网络是希望它们之差很小，实时网 络系统尤其是这样因此，容错直径为设计和评估网络性能提供了一个重要度量 参数，近几年来己引起人们的广泛研究兴趣 关于容错直径的结果很多，早期研究结果可参见b e r m o n d 、b o n d 、p a o l i 和 p e y r a t 4 的一篇综述文献这些结果的太部分已经被收录在文献【2 的第4 2 节中， 有些结论有详细证明 另外，在并行计算系统的网络中，信息是通过若干条内点不交的路径平行地 进行传输于是，对于这样的网络，仅孤立地考虑连通度和直径也是不够的，因 为网络虽然有大连通度和小直径，但通过该网络中若干条内点不交的路并行传输 信息时，其中某些路径可能很长因而传输延迟大，信息达到时间间隔很大，影 响整个网络的的有效性。因此在并行计算系统( 特别是在实时系统) 的网络中，只 用连通度和直径或容错直径作为网络可靠性和有效性的度量显然是不合适的，而 将连通度和直径结合起来考虑是很有必要的基于这种考虑，h s u 、l y u u s 和 f l a n d r i n 、l i 6 独立提出了度量并行计算系统网络的容错性和传输延迟的重要参 数宽直径( w i d ed i a m e t e r ) 定义2 2 设g 是k 连通的，x 和y 是g 中两个不同的顶点由m e n g e r 定理 知，g 中存在k 条内点不交的( 石，y ) g 中k 条内点不交的( x ，y ) 路集 p = 只，只，只) 称为g 中一个宽度为女的( x ，) ，) 路系( ( 曩_ y ) 一p a t h s w i t hw i d t h t ) ，简称七一力路系，亦称一c o n t a i n e r g 中所有k 一“y ) 路系的集合记为 只( g ；x y ) g 中从顶点x 至i n a y 的宽度为k 的距离( d i s t 卸c e w i t h w i d t hk ) 矾( g ；x ，y ) 是最小正整数d 使得g 中存在k 条内点不交且长度都不超过d 的( 暑y ) 路，即 中国科学技术大学硕士毕业论文 以( g t y ) = m i n w ( e ) ：p 只( g ；x ，j ，) g 的k 宽直径( d i a m e t e r w i t h w i d t hk ) d 女( g ) 定义为最小正整数l 使得对于 g 中任何两顶点u 、v ，g 中存在k 条内部点不交且长度都不超过，的( ”，v ) 路，即 d ( g ) = m a x 矾( g ；x ，) ，) ：v x ，y 矿( g ) 由定义。易知 d ( g ) = d l ( g ) d ：( g ) - d 一i ( g ) 以( g ) 宽直径把图的连通度和直径结合起来考虑在一个性能好的并行计算系统的 互连网络中，显然是要求连通度大，而宽直径小，因此，宽直径能度量网络的容 错度和传输效率 容错直径与宽直径这两个参数给出了容错网络和平行处理系统网络的传输 延迟的准确度量，已引起许多研究者的兴趣，并已确定了许多著名网络的容错直 径和宽直径的值 5 ，7 例如，超立方体网络，d e b r u u n 网络，k a u t z 网络等等详 细的，请参加文献【2 的第4 4 节 在本文中，如果没有特别指明，记号以d 。、d 。分别表示图g 的直径d ( g ) 、 宽直径以( g ) 和容错直径d 。( g ) 二、主要引理 对于k 连通图g ，由容错直径d 。的定义知：g 中存在两顶点u 、v 和子集 f v c g ) 似v ) ，i f i k ，使得“和v 在g f 中的距离为d 。由宽直径的定义 知，g 中存在k 条内点不交的( “，v ) 路使得每条路的长度不超过d 。由于l f i k ， 所以这k 条路中至少有一条不含f 中地点这样得到容错直径和宽直径之间有如 下的关系： 引理2 1 对任何k 连通图g ，有d ；以 其中的等号对许多著名的图是成立的【2 】例如，超立方体网络，d e b r u i j n 网络，k a u t z 网络等等 对于给定的图，由于故障集是随机的，因此求图的容错直径困难很大h s u ( 1 9 9 4 ) 【8 】已证明确定给定的图的宽直径问题是个n p c 问题一些著名的网 络或图的宽直径已被确定，其基本方法是构造方法为了确定d 。= d 常用的 方法是根据m e n g e r - w h i t n e y 关于七连通图的判定定理( 即本文引理1 2 ) 对 于g 中任何两个顶点x 和y ，通过图g 的具体特征构造出k 条内点不交的路使 中国科学技术大学硕士毕业论文 其每条路的长度不超过d ，其中至少有一条路的长度为d ，这就需要对图的结 构特征有深刻的了解 正因为这样，讨论d 。和d 。之间的进步关系显然是重要的，人们关心的是 若引理中的严格不等式成立，那么它们之间到底相差多少但很可惜知道的结 果却很少据作者所知，目前仅有一个关于直径d ( d 2 ) 的2 连通图的一个结 果，属于f l a n d r i n 和l i 6 1 ，我们将这个结果叙述为下述引理： 引理2 2 设g 是2 连通图则 ( 1 ) 当d = 2 时，d 2 d 2 + 1 ； ( 2 ) 当d 3 时，d 2 蔓( d 1 ) ( j | ) 2 1 ) 容易构造出例子说明这两个上界不是最好的我们的目的是想改进这两个 上界 三、主要结果 因为问题的困难性，人们目前还无法给出一般k 连通图的容错直径d 。与宽 直径d 。之间更紧密的关系本章只讨论2 或3 连通图第二、三节分别讨论了： 当g 为2 或3 连通图时，容错直径巩与宽直径d 。之间的关系，进一步刻画了 2 或3 连通图的性质，同时也改进了引理2 2 中的结果本章证明了： 当g 为2 连通图时， d 2 m a x ( d 1 ) ( d l 一三一1 ) + l ，d 2 + 1 ； 并且，d = 2 时d ：= d ：+ 1 的一个充分必要条件是：即d ：= 3 或4 且达到以值的任 何两顶点必相邻 设g 为3 连通图： 若d = 2 ，则如m a x ( d 2 1 ) ( 岛一去d 2 1 ) + 1 ，3 d 3 5 ，b + 1 ) ； 若d 2 = 2 ，贝0 d 3 m a x f d 3 + l ，2 b 一2 ； 若d 2 ，且0 l 3 ，贝以( 矗一1 ) 【2 ( 幺一1 ) ( 色一1 ) 一d 一2 】+ l 中国科学技术大学硕士毕业论文 第二节2 连通图的容错直径与宽直径 一、引理 我们首先证明一个引理，它在本节中主要定理的证明中起了重要的关键作 用 引理2 3 设g 是2 连通图，“和v 是g 中距离为1 7 1 + 1 的两项点若1 ， 则g 中存在两条内点不交的( 1 1 , v ) 路只和p 2 使得 嘲) s ( p o m a x 伽( 。：一i 1m 一；) “d 2 ) 证明设p = u x l x m v 是一条最短的( “，v ) 路，则1 m d 1 d 2 1 由 m e n g e r 定理，令q 是g x ，中最短( “，v ) 路，则对任何i i m 有e ( 9 ) d ：令 h = p u qu u 绒 任取x v ( h ) “，v ) 若x = x ，则q ，是h x 中( “，v ) 路；若x 矿( q j ) 且 x g v ( p ) ，则p 是h z 中( “，v ) 路这说明在h 分离“和v 至少需要2 个顶点由 m e n g e r 定理知：h 中必存在两条内点不交的( “，v ) 路 若p 、q 1 、q 。中存在两条路内点不交，则这两条( ”，v ) 路的最大长度至多 为m a x m + 1 ，d ： = d 2 下面，假定p 、q l 、q 。中任何两条路内部相交，则 m 2 下面，我们根据p 、q l 、q 卅的交点数，分别两种情形来讨论 若，、岛，、q 卅的交点数 三埘+ 1 ) 那么容易验证肌3 ，b f l d 2 4 在 这种情况下，p 、q i 、q ，中必存在3 条路内部相交于一点由于在h 中分离 “和v 至少需要2 个顶点，所以必存在第4 条路，它不经过前3 条路的公共交点于 是，通过对这4 条路中某几段( 每段长至多为d a 2 ；若4 条路中某条路被分成 3 段，则至多有一段长为d 2 4 ) 的拼接，得到打中两条内点不交的( v ) 路， 其中每条路的长度至多为3 d ：一8 因为函数 ，( 脚) = 伪( 。：一j 1m 一；) + 1 甲国科学技术大学硕士毕业论文 一 在区间 3 ，d 2 2 上单调递增，j 1 f ( d 2 1 ) ，( 3 ) ，所以1 兰d l 协一1 时， 有 3 d ：一8 2 ( 3 ) ( 脚) = 册( d j 一喜一刍+ 1 若p 、q 1 、q ，的交点数去m 十1 ) ，则h 的顶点数目 “柳( 晰+ 2 ) + ( b - 0 一去聊( 聊+ i ) = 册( d 2 一昙m i 1 ) + 2 设鼻雨f 只是日中两条内点不交的( “，v ) 路，则m 十1 s ( e ) s ( 最) 于是， 8 ( 鼻) s g ( p 2 ) v ( h ) 一一1 - m ( d 2 一m 一：3 ) + 1 引理得证 。注： 我们举两个例子来说明当研= 1 和m = 2 时，引理2 3 中给出的界可以 达到 。 由引理2 3 知，当州= 1 时，g 中存在两条内点不交的( “，嵋路置和只使得 5 ( 只) 8 ( 只) b 考虑圈q 0 4 ) 中距离为2 的两顶点“和v ，c 。中存在两条 内点不交的 ，v ) 路只和最使得s ) = 2 ，且s ( p j = i - - 2 ：d z 由引理2 3 知，当聊= 2 时，g 中存在两条内点不交的( “，v ) 路鼻和b 使得 8 ( 鼻) 蔓8 ( p 2 ) s 2 d 2 4 ( 设d 2 苫4 ) 设p = x o x i x 2 x 3 是长为3 的路，q = y 】儿y 。 是长为8 的路令 g = p u q u 缸。y l ，屯) ，9 u uu ( x ij ，j ) t - l4 ( t 一1 ) + i 显然g 是2 连通的，而且和z ，的距离为3 容易验证b = d ( g x ：) ：7 取 q 1 = x o y i y 2 y 8 y 9 坞 则s ( q 2 ) = 1 0 容易验证p 和q 1 是g 中两条内点不交的( x 0 ，x 3 ) 路易得 e ( p ) s ( q 1 ) = 2 d = 一4 二、主要结果的证明 中国科学技术大学硬士毕业论文 我们给出本节的主要结果和它们的证明 定理2 4 直径为d 的2 连通图有 d 2 m a x ( d 1 ) ( d 2 一d 一1 ) 十1 ，d 2 + 1 证明设g 是直径为d 的2 连通图若d = 1 ，则g 是一个完全图，有d ，= 2 ， d ，= 1 ，因此定理成立以下假定d 2 并设“和v 是g 中任意两顶点只需证 明g 中存在两条内点不交且长度都不超过 d 2 m a x ( d 1 ) ( d 2 一妄d 一1 ) + 1 ，d 2 + 1 的( “，v ) 路为此令p = 船x 。v 是一条最短的( “，v ) 路 若m = 0 ，则“和v 在g 中相邻令q 是g 一“v 中最短( “，v ) 路，1 9 z , q 一“是 g 一“中一条最短路，因而e ( q ) 蔓d ：+ 1 若m 1 ，则由引理2 3 知g 中存在两条内点不交的( “，v ) 路只和b 使得 粥) 纠p 2 ) 仰( d 2 - i 1m 一争“d 2 ) ( 2 1 ) 注意到1 m 蔓d 一1 由于函数 ，( 所) = m ( 。：一j 1 一i 3 ) + l 在区间 1 ，d - 2 lp 单调增加，且厂( d 一1 ) 厂( d 一2 ) ， f ( d 1 ) = ( d 一1 ) ( d 2 一去d 1 ) + 1 所以，由( 2 1 ) 式，定理得证 注：给定在定理2 4 中的上界d ：+ l 是可以达到的例如圈c 。( n 3 ) 另外，当d = 2 时，由定理2 4 有 d 2 m a x d 2 1 ，d 2 + 1 = d 2 + 1 当d 3 时， 以m a x l ( d _ 1 ) ( d ：一吉d _ 1 ) + 1 d ：+ 1 ) ( ( d 柚( d z _ 1 ) 因此，定理2 4 改进了在引理2 。2 中提到的f l a n d r i n 和l i 的结果 定理2 5 设g 是直径为2 的2 k g n i l t ，则d ：= d ：+ 1 的充要条件是d ：= 3 或 中国科学技术太学硕士毕业论文 d ：= 4 ，且达到d ：值的任何两顶点必相邻 证明( 必要性) 假定d z = d 2 + 1 因为d 2 日= d = 2 ，所以d ：3 由宽 直径的定义知：g 中存在两顶点“和v 使得其宽距离达到d ：值于是，g 中任何 两条内点不交的( ，v ) 路中至少有一条长度不小于d ：设p = “z 。v 是一条最 短( “，v ) 路，由于g 的直径为2 ，所以1 若m = 1 ，则由引理2 3 知，g 中存 在两条内点不交的( “，v ) 路只和岛使得 s ( 只) s ( p 2 ) m a x d 2 一l ，d 2 ) 因此，我们有 d 2 + l = d 2 占( 只) d 2 ， 矛盾因此m = 0 ，即“v e ( g ) i 殳q = u y 。n v 是g 一洲中一条最短的( “，v ) 路， 则d 2 = ”+ 1 假定d 2 5 ，即”4 ，n z , y 2 和v 在g 中的距离为3 ，即g 的直 径至少为3 矛盾所以，3 茎d 2 4 ( 充分性) 设虮v 、z v ( o ) 使得“和v 在g z 中的距离为d 2 d = 2 ，并 设p 是g 一= 中最短的( “，v ) 路则s ( p ) = d ：因为g 的直径为2 ，所以存在 y v ( o ) 使得u y 、e ( o ) 不妨设y = = ，并令a = 于是p 和q 是g 中两条内点不交的( 虬v ) 路，r e ( q ) s ( p ) 因为“和v 在g 中不相邻所以，由相邻性假定应有d 2 = g ( 尸) d 2 1 ，即d 2 d 2 + 1 另一方 面。当d = 2 时，由引理2 2 有d 2 d 2 + 1 所以，d 2 = d 2 + 1 定理2 6 设g 是直径为2 的2 连通图，若d 2 = 2 或d 2 5 ，则d 2 = d 2 证明由引理2 1 、2 2 d z d 2 d 2 + l ，再由定理2 5 ，易得d 2 = d 2 中国科学技术大学硕士毕业论文 一、引理 第三节3 连通图的容错直径与宽直径 我们首先证明一个引理 引理2 7 设g 是3 连通图，u v e e ( g ) 则g 一“v 中存在2 条内部点不交且 长度不超过m a x d 3 + 1 ，d 2 ( d 3 2 ) + 2 ) 的( “，v ) 路 证明设p 是g 一“v 中一条最短的( “，v ) 路由于f ( p ) 一i 蔓d ( g v ) d ：所 以，s ( ，) d 2 + l d 3 + 1 我们分别考虑s ( 尸) = 2 和g ( p ) 3 两种情形 设g ( p ) = 2 ，并设p = 瓣v 因为g 是3 连通的，所以8 ( g ) 3 设y 是v 在 g 一“v 中的异于x 的邻点，q 是g 一v ) 中一条最短( “，y ) 路则q + 是g l i v 中一条与p 内部点不交的( “，v ) 路，而且 f ( q + p ，) = ( 囝+ 1 d ( g f 葺v ) ) + 1 d 3 + 1 。 因此，p 和q + y v 是g 一“v 中2 条内部点不交且长度都不超过乜+ 1 的( “，v ) 路 设8 ( e ) 3 ，并设 p = 般l x ，v ( 2 m 墨d 2 ) ， y 是v 在g u v 中异于靠的一个邻点，鼻是g - x 。，订中一条最短的( “，力路则 对每个f = 1 , 2 ，肼。有5 ( 只) d ( g 一，y ) ) d 3 若p 与只、- - 、己中某条只内部点不交，则p 和只+ y v 是g 一“v 中2 条内部 点不交且长度都不超过d ，+ 1 的( 地v ) 路下面，假定p 与鼻、- 、己中任何一条内 部点相交n p 经过置u up m 的内部点至少m 次令 日= e u u 只u 中国科学技术太学硕士毕业论文 用 表示日的顶点数目于是。 h 2 + ，疗+ ，卵( d 3 1 ) + 1 1 7 , l = m ( d 3 1 ) - 4 - 3 任取x y ( h ) “，v 若x = z ，则p + y v 是g z ，中( ”，v ) 路：若x 不为任何 一，则p 是h x 中( “，y ) 路这说明在h 中分离“和v 至少需要2 个顶点，由 m e n g e r 定理知，h 中必存在两条内部点不交的( “，v ) 路设q 。和q ：是这样的两 条路，并不妨设s ( q j ) s e ( 9 2 ) 由于聊+ l = s ( p ) 兰e ( q 。) 和s d z ，所以， 5 ( q 2 ) h - e ( q 1 ) - 1 - 1 ，”( d 3 1 ) + 3 一m 一1 d 2 ( d 3 2 ) + 2 因此，q 1 和q ：是g 一“v 中两条内部点不交且长度都不超过d ：( d ，一2 ) 4 - 2 的 ，v ) 路引理得证 二、主要结果的证明 我们给出本小节的主要结果和它们的证明 定理2 8 直径为2 的3 连通图有 1 d 3 m a x ( d 2 一1 ) ( d 3 一d 2 一1 ) + 1 ，3 d 3 5 ，d 3 + l 证明设是g 直径为2 的3 连通图任取g 中两个不同的顶点”和v ，只需 证明g 中存在3 条内点不交的且长度都不超过 1 d 3 蔓m a x ( d 2 一1 ) ( d 3 一d 2 一1 ) + 1 ，3 d 3 5 ，d 3 + 1 ) 的( “，v ) 路下面，我们分顶点”和v 粗邻和不相邻两种情形来讨论： t l , - 形“v e e ( o ) 因为d ( g ) = 2 ，所以存在z v ( g ) 使得船、川e e ( g ) 令p = 1 1 x 1 x ，v 是g 一= 中最短的( 以v ) 路，则s ( p ) ；柳+ 1 兰d 2 ，m 1 由引理 2 3 知g 一= 中存在两条内点不交的( 地v ) 路只和p 2 使得 s ) s ( p 2 ) m a x m ( d ：( g z ) 一圭m 一三) + l ，见( g 一拼 ( 2 ，2 ) 注意到d ：( g z ) s d ，( g ) = d 3 ，由( 2 2 ) 式有 中国科学技术大学硕士毕业论文 s ( p o s ( 只) m a x ( o s - j l m i 3 ) + 1 ，。， ( 2 3 ) 令 g ( 卅) = ( d ，一； t 一；) + l ， 则g ( 蜥) 在区间【l ，d 2 2 】上单调递增，且g ( 玻一1 ) g ( d ：一2 ) ， g ( 0 2 1 ) = ( j d 2 1 ) ( d 3 1 d 2 1 ) + 1 由式( 2 3 ) 知：只和p 是g z 中2 条内点不交的长度不超过 m a x ( d ：一1 ) ( d 3 一d 2 l t i 手y 9 2 “v e ( g ) 我们将证明g 一 一1 ) 十1 ，d 3 ) 的( “，v ) 路 ”v 中存在2 条内点不交的且长度不超过 m a x 3 d 3 5 ，d 34 - 1 的( 1 4 ，l ，) 路令j p = w l x m p 是g 一“v 中最短的 ，p ) 路因 为d ( o ) = 2 ，所以i m 3 ，而且6 ( e ) = m + 1 d 2 + 1 于是，由引理2 3 知g 一“v 中存在两条内点不交的( “，v ) 路p l 和p 2 ，使褥 s ( 只) s 5 ( p 0 m a x 伽( d ：( g 一“v ) 一j 1 ，”一三) + 1 ，。：( g 一“v ) ( 2 4 ) 注意到d 2 ( g - u v ) d 3 + 1 ，由式( 2 4 ) 有 粥) 纠p 2 ) m a x 劬( d 3 一丢m 一“n + 1 ) ( 2 5 ) 所以当埘= 1 时，由式( 2 5 ) 有 占( 鼻) 占( 最) m a x d 3