（运筹学与控制论专业论文）互联网络容错性质分析.pdf

互联网络容锋l 生质分析 摘要 网络的拓扑结构足设计和制造集群计算机或超大规模并行计算机 系统的第一步，也足实现各种协议的基础，它对网络的件能，系统n f 靠性和费用都有重大影响 人们通常把互连网络中的处理器抽象成一个点，把处理器之间的 信道抽象成两点之间的连线，那么该网络的拓扑结构就被抽象成一个 网研究网络拓扑结构问题就归结为研究图的结构问题网络的容锖 性研究n f 以转化成对网的参数研究 互连网络主要有以下的评价指标； ( i ) 硬件复杂度；吖以用拓扑同的顶点度来衡量 ( 2 ) 通信丹销：n r 以用网络拓扑冈的直径来，平均距离来衡量 ( 3 ) n f 扩展性：就足一个小网络要扩充为一个大网络，并保留小 网络的结构件质的叮能性，它叮以归结为图的n r 嵌入性口j 题 ( 4 ) 容错能力：叮以用冈的连通度以及边连通度，网络的容错直 径，宽直径，限制连通度和限制边连通度来衡量 目前讨论比较多的网络主要有网状网、树状网超方体状网和星状 网类型网络本文主要考虑这些网络的容锖性质，我们的工作如下： 首先，我们对这些主要的网络拓扑结构的容错件指标，例如通信延 迟，容错直径与宽直径、连通性质进行了系统的总结在此基础 ：， 提出了互连网络拓扑容错性方面一些值得进一步研究的口j 题 然后，本文对超市方体的子网一广义f i b o n a c e i 市方体进行进一 步研究对广义f i b o n a e e i 立方体的研究l 有很多，包括连通度递归 性，n r 嵌入环和格，直径 本文研究广义f i b o n a c e i 移方体的容错直径，宽直径，限制边连通度 和超边连通度，证明了容错直径，宽直径等于它的直径加l ，确定了其 l - 限制边连通度和1 - 趟边连通度 关键词：广义f i b o n a c e i 市方体，容错直径，宽直径，限制边连通 度，i 一赳边连通度 i i 湖南师范大学硕士学位论文 a b s t r a c t t h ef i r s ts t o pi nt h ed e s i g n i n ga n di m p l e m e n t i n gl a r g es c a l ep a r a l l e lc o l - p u t i n gs y s t e mi st oc o n s t r u c ti n t e r c o n n e e t i o nn e t w o r k st o p o l o g i c a l8 t n i c t l l r e i n - t e r c o n n e c t i o nn e t w o r k si sa l s of o u n d a t i o no fi m p l e m e n t i n ga l lk i n d so fp r o t o c o l a n di tp l a y sa ni m p o r t a n tr o l ei nt h ep e r f o r m a n c e 。s y s t e md o p e n d a b i l i t y ，a n d c o s to ft h en e t w o r k s i n t e r c o n n e c t i o nn e t w o r k sa r eo f t e nm o d e l e da sag r a p hw i t h v e r t e xr 印r e n t i l l gp r o c e s s o ra n da ne d g er e p r e s e n t i n gc o m m l m i c a t i o nc h a n n e l b e t v j e e np r o c e s s o r s s ot h es t u d yo ft o p o l o g i c a ls t f u e t l l ：r eo fi n t e r c o n n e e t i o nn e t - w o r k si st u r n e dt ot h es t u d ys t r u c t u r eo fg r a p h a n dt h es t u d yo ff a u l t - t o l e r a n t o fn e t w o r kc a l lt r a n s f o r mt ot h es t u d yt h ep a r a m e t e ro fg r a p h t h ep a r a m e t e r s t oe v a l u a t et h ep e r f o r m a n c eo fi n t e r c o n n e c t i o nn e t w o r k s a l ea sf o l l o w s ： ( 1 ) h a r d w a r ec o m p l e x i t y ：i tc a nb ee v a l u a t e db yt h ed e g r e eo fv e r t e xo f t o p o l o g i c a lg r a p h ( 2 ) c o m m u i c a t i e ne x p e n s e s ：i tc a l lb ee v a l u a t e dt h ed i a m e t e ro ra v e r a g e d i s - t a n c eo ft o p o l o g i c a lg r a p h ( 3 ) e x p a n d a b i l i t y ：i tc a nb ec o m ed o w nt ot h ep r o b l e mo fe m b e d a b i l i t yo f s o m es p e c i a ls t m c t l l r e s ( 4 ) f a n l t t o l e r a n c e ：i tc a n b e e v a l u a t e d 蚵t h e c o n n e c t i v i t y ，e d g e - c o n n e c t i v i t y ， f a u l t - t o l e r a n td i a m e t e r ，w i d t hd i a m e t e r ，r e s t r i c t e dc 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 yo fg r a p h n l ew i d e l ys t u d i e dt o p o l o g i c a ls t m m ea r em e s h - c o n n e c t e dn e t w o r k s 。t r e e n e t w o r k s ，h y p e r c u b en e t w o r k sa n ds t a rn e t w o r k s w em a i n l yc o n s i d e rt h ef a u l t - t o l e r a n tp r o p e r t i e so ft h e s en e t w o r k si nt h i st h e s i s o u rr e s e a r c hc o n c e n t r a t eo n t h ef o l l o w i n g ： f i r s t ，w es u r v e yt h ef a u l tt o l e r a n tp a r a m e t e r so ft o p o l o g i c a ls t n l c t u r eo fi n - t e r c o n n e c t i o nn e t w o r k ss u c h 舶c o m m u n i c a t i o nd e l a y 。f a u l t - t o l a l a n td i a m e t e r ， w i d t hd i a m a t e ra n dc o n n e c t i v i t y b a s e do i l t h i s ，w ep r o p o s es o m ep r o b l e mt h a t w o r t hf u r t h e rs t u d y i n g t h e n s t u d i e dt h es u b g r a p ho fh y p e r c u b e - e x t e n d e d f i b o n a c c ic u b e t h ee x t e n d e df i b o n a c c ic u b ea l ew i d e l ys t u d i e d m a n yp a r a m e t e r sa t ed e - t e r m i n e d ，i n c l u d i n gc o n n e c t i v i t y r e c u r s i o n e m b e dr i n ga n dm e s h d i a m e t e r 互联网络容错性质分析i i nt h i st h e s i s ，w es t u d m dt h ef a u l t - t o l e r a n td i a m e t e r ，w i d t hd i a m e t e r ，r e - s t r i c t e de d g ec 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 yo fe x t e n d e df i b o n a c c ic u b e s a n dp r o v e dt h a tt h ef a u l tt o l e r a n td i a m e t e r w i d t hd i a m e t e ri se q u a lt od i a m e t e r p l u s1 ，d e t e r m i n e d - r e s t r i c t e de d g ec o n n e c t i v i t ya n d1 - e x t r ae d g e n 删i v i 锣o f e x t e n d e df i b o n a c c ic u b e s k e yw o r d s ： e x t e n d e df i b o n a c c ic u b e ，f a n l t - t o l e r a n td i a m e t e r ，w i d t h d i a m e t e r ，瑚t r i c t e de d g ec o n n e c t i v i t y ，1 - e x t r ae d g ec o n n e c t i v i t y 湖南师范大学硕士学位论更 学位沦文原创性声明与版权使压授权书 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果除文中已经注明引用的内容外，本论文 不舍任何其他个人或集体已经发表或撰写过的作品成果对本文的研 究做出重要贡献的个人和集体，均巳在文中以明确方式标明本人完 全意识到奉声明的法律结果由本人承担 学位论文作者棼名；乖 如力吵年岁月3 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允 许论文靛查嶂 和借阋本人授权湖南师范大学可以将本学位论文的垒 部或部分内容编八有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文+ 本学位论文属于 1 、保密0 ，在年解密后适用本授权书 2 、不保密0 ( 请在以上相应方框内打” ，) b 粕：厕年yr ； i ：j 日期：7 祈年月1 日 渤 互联网络容错性质分析 第一章互联网络容错性研究现状 1 1 引言 随着各个领域对高件能计算的要求越来越高，多处理机和多计算机 的规模越来越大，处理机之间或处理单元与存储模块之间的通信要求 和难度越来越突出因此苴连网络足并行处理系统的核心组成部分， 它对整个计算机系统的件能价格比有着决定件的影响互连网络研究 主要集中在如下4 个方面： ( 1 ) 定时方式：有同步和异步两种 ( 2 ) 交换方法；有线路交换( c i r c u i ts w i t c h i n g ) 和分组交换( p a c k e ts w i t c h - i n g ) 两种 ( 3 ) 控制策略：有集中式和分散式两种 ( 4 ) 拓扑结构：有静态和动态两种 本文主要综述静态拓扑结构的容错性研究现状，提出进一步研究 的问题 1 2 网络拓扑容错性衡量标准 网络的拓扑结构是设计和制造集群计算机或超大规模并 f 计算机 系统的第一步，也是实现各种协议的基础，它对网络的性能系统n r 靠 性和费用都有重大影响互连网络的拓扑结构叮以用一个阿g = e ) 来表示，每个处理器用网的一个顶点表示，处理器之间的通信信道用 一条边表示因此网络的容错件研究叮以转化成对隔的参数研究 互连网络主要有以下的评价指标i q ： ( 1 ) 硬件复杂度：将n 个处王! 琏机按一定的拓扑结构连接成网络所 需的开关的个数叮以用拓扑网的顶点度来衡量 ( 2 ) 通信开销：n f 以用网络拓扑图的直径和平均距离来度量【l j ( 3 ) n r 扩展性；简单说就是一个小网络要扩充为一个大网络，并 保留小网络的结构性质，它叮以归结为阿的叮嵌入性口题 2 湖南师范大学硕士学位论文 ( 4 ) 容错能力：对网络容错能力的研究即对网络n r 靠件的研究 传统的网络叮常件和有效性的参数有连通度，边连通度和直径等 由于连通度和边连通度的研究需要假设网络拓扑中某一处理器的 所有相邻处瑚器或与此处理器相关信道同时失效，而在实际的情况中， 此种假设不能准确的反映容错网络的真实情况，因而连通度和边连通 度具有明显的缺点e s f a h a n i a n 和h a k i m i 2 1 推广了连通度和边连通度 的定义，卜：述参数的荩本定义如下： 定义1 1 ：设g 是阿，它叮以足无向阿，也叮以足有向罔设置y y ( g ) ，g 中其最小的( 以y ) 路称为最短路( z ，y ) 路。从z 到y 的距离，记 为d g ( 墨y ) ，定义为最短路( z ，) 路的长度对于有向阿如( f ，z ) 不一定 等于d g ( z ，y ) ，但兀向阿必有d g ( ，z ) = d g ( x ，y ) 约定如( 墨z ) = o 若g 中不存在( z ，y ) 路，则规定如( z ，y ) = + m 定义d ( g ) = i r l a x d g ( z ，) ：以y y ( g ) 为g 的直径 定义1 2 ：设g 足连通阿，g 的平均距离定义为 邸) 2 而1 磊酢川 定义1 3 ：对于f c v ( g ) ，如果f 不包含g 中任何点的邻点集 作为子集，则称f 足限静| 点集如果g f 足不连通的，则称f 为限 制点割如果g 中存在限制点割，则限制连通度一( g ) = r a i n i f i ：f 为 g 的限击4 点割 定义1 4 ：对于s c e ( g ) ，如果s 不包含g 中任何点的邻边集m 作为子集，则称s 足限制边集如果g s 是不连通的，则称s 为限 制边割如果g 中存在限制边割，则限制边连通度a c g ) = r a i n i s i ：s 为g 的限制边割 同样，仅仅对网络的直径进行研究也不能真实的反映网络在具有 互联网络容错性质分析3 失效处理器下的网络延迟，因此出现了度量并行实时系统的有效性参 数宽直径【3 】，度量容错网络的有效件的参数一容错直径 a 1 只林定义 如下： 定义1 5 设g = e ) 足一个无向或者强连通有向网，fcv ， 称为g 的点故障集z 和y 足g f 的两个顶点 从z 到y 的一1 ) 点奔错距离，简称容错距离， 己做珑( z ，y ) ， 定义为： 或( z ，f ) 2 怵m a x 。 d a p ( 毛，) ：fc v ( g ) 一1 ) 弈错直径记做仉( g ) ，定义为 珑( g ) 2 怵m a x 。 d ( g f ) ：fc v ( a ) 定义1 6 设g 足一个k 连通阿，z 和口足g 中的两个顶点，由 m e a g e r 定理知道，g 中存在条内点不交的( z ，y ) 路 g 中七条内点不交的( z ，y ) 路的集合p = r ，马，r 称为g 中 一个宽度为的( z ，) 路系，p 中的最大路长记做d ( p ) g 中所有七一( 毛y ) 路系的集合记做r ( g ；墨f ) g 中从顶点z 到顶 点f 宽度为的距离，记做以( g ；z ，f ) ，定义为 d k ( g ；z ，y ) = m i n d ( p ) ：p p h c a ；，) g 的宽度足k 的直径，记做d k ( g ) 定义为 d ( g ) = m a x d k ( g ；z ，f ) ：，暑，y ( g ) 4 湖南师范大学硕士学位论文 等 下面足关于珑( g ) ，d o ( g ) 的一些基本关系和性质 定理1 1 嘲对于任何连通度为k 的网g 有： ( 1 ) d f ( g ) s 巧( g ) s d h c ) ， ( 2 ) d i ( g ) s0 2 ( c ) sd k ( g ) ， ( 3 ) 对于1 s sk ，d ( g ) s d 0 ( g ) 其他的网络吖靠件及有效性的参数还有托宾数| 3 | 和强扣宾数【q 1 3 各种网络拓扑性能比较 目前所提出的网络拓扑结构主要分成四种类镬；网状，树状、超方 体状和星网状下血我们首先介绍常用的网络拓扑结构，然后用表格 的形式列出目前对卜述参数的研究情况 1 3 1 超方体状网络拓扑结构 超方体网络的拓扑结构足无向冈q 。= e ) 其中v = z - 岛： 以 o ，l ，i = 1 ，2 ，n ，两个顶点z = z l z 2 z 。和y = y l y 2 y n 在q 。中 n 相邻当且仅当i 一y i i = 1 超方体网络町以推广到无向舣环面 i = l ，l 维无向舣环面冈 己做c ( d - ，如，厶) 它的顶点集为v = x l x 2 2 n l x i o ，1 ，d 一1 ，i = 1 ，2 ，n 两个顶点正= z 1 z 。和y = g l 耽鲰在q 。 n 中相邻当且仅当k 一挑l = 1 i = 1 超方体有很多变种，这里我们主要介缁m 维交义超方体，折叠超 方体、n 维市方连通罔机曲方体，分层方体，变种超方体 m 维变种超方体n r 以这样递归地构造：y q 。足一个有两个顶点的 完全阿，y q 。由两个相等的t l 一1 维变种方体y 识一。和y 哦l 组成 互联同络容错性质分析 两个顶点= o u 。_ 1 埘l y ( y q ：一1 ) 和顶点口= i v _ l l y ( y q ：一1 ) 有 边相连当且仅当 i 如果n 3 k ，。l “l = _ 1 一仇或者 2 如果，i = 3 k ，u n - 3 以l = - 3 口l ， ( u n f u n _ 2 ，一1 一2 ) ( 0 0 ，o o ) ，( 0 1 ，0 1 ) ，( 1 0 ，1 1 ) ，( 1 1 ，1 0 ) m 维交义超方体n r 以这样递归地构造：o q 。足一个有两个顶点的 完全图，o q 由两个相等的n 一1 维交艾方体0 q o 一。和c q ：一。组成 两个顶点“= o u _ 2 u o v ( c q o 1 ) 和顶点口= l v 。- 2 v o y ( g 砚一1 ) 有 边相连当且仅当 1 当n 足偶数时，t ，i 一2 = 一2 并且 2 ( u 2 i + l u 2 i ，i ) 2 i + 1 口2 ) 冗，0 i 【孚j ，这里 r = ( 0 0 ，o o ) ，( 1 0 ，1 0 ) ，( 0 1 ，1 1 ) ，( 1 1 ，0 1 ) 折叠超方体，记做f h ( 7 它的顶点集和超方体的顶点集相同 对每个顶点u h f c 我们用n ( u ) 表示顶点“的二元地址i n ( u ) i 表示 n ( u ) 中1 的个数两个顶点“和”相邻，当且仅当i o ( u ) o n ( ”) i = 1 或者n 阿层的超方体网， 己做h n ( d ，2 ) ，它的顶点集合为 6 址2 址3 b o l b ；i o ，1 对所有0 s i s2 d 一2 ，这里d 2 顶点址2 k - 3 b o 与下匝的顶 点相邻： ( 1 ) 一2 6 冰3 b i + l b i _ 1 6 0 其中6 ：足6 t 的补， ( 2 ) b d _ i b - 2 b d b o 在b o = 0 时 n 维立方连通罔， 己做g ( n ) 足一个基于超方体q 。构造出来的无向 图：用n 阶无向罔g 代替q 。的每一个顶点，并将q 。的第k 维边连 接到g 的第k 个顶点 具体地说，c ( n ) 的顶点集合为v = ( z ，k ) ：z 风，1 k sn ，两 个顶点扛，k ) 和( 一，f ) 有边相连 辛满足下列两个条件之一： ( 1 净= 一且k f ! 士l ( m o d n ) ， 湖南师范大学硕士学位论文 ( 2 ) k = z 和一在q 。 分层超市方体；记作h c n ( n ，n ) a 表示n 位比特串，面表示啦的补，= a n - 1 面a o 它由2 n 个 摹本簇组成，每个簇足一个市方体 h c n ( n ，n ) 中的每个点由2 n 位二进制串a l 如表示a l 决定点属 于哪个簇，山决定簇中点的地址簇内点之间的连线规则和超市方体 一样，比如a l 舶和a l a o 相连，0 i s n 一1 这些边称为i 维局部边 , 4 0 a - ，簇之间的连边足连接a t 山和山a - ，对于所有的山，a 。， 这些边称为机边a o = a - 时，a t a o 和瓦石相连，这些边称为补边 互联网络容锋l 质分析7 关于超方体状网络的容锵性研究l 三经有很多结果，我们列出下面 的参数表： 表1 1 ：超方体状网络拓扑结构参数比较 “系 塑立堡茎1 2兰! 竺兰竺 折叠 超方体 2 1 n d 。( f ) 【8 j乩( f h ) 【8 】 塑塑堡 兰! i ! 竺 i ! 竺! 分层 立堡! 兰 ! ! ! 兰 ! ! 12 兰 ! ! ! 交艾 查堡 兰! 芝 型 兰 型 变种 丝立堡 翌 竺2 型! 墓! 【竺 翌 ! 壅! 竺 市方 垄堕堕【兰!i 望坐i 兰坐 广义 f i b o n a c c i 奇：方体 n 一2 【1 q i 1 【5 l n 一1n 一1 珑c f h ，= 。c f 日，= 茎+ 。， q l 1 一 + n 一2 n 一 一 m 一 一【4 ( d 2 1 ) ， k = 3 ( 4 ) 从而得到广义d e b r u f i n 有向网和广义k a u t z 有向阿的限制边连通 度，相关文章有【筠】【筠j 其他的研究结果有有向d e b r u j i n 有向阿的限制边连通度吲， k a u t z 阿的限制边连通度【髂j ，超方体网络的限制连通度i 嚣】，折叠超 方体的限制边连通度删 1 4 结论 目前，国际卜：对网络拓扑结构分析的研究还不断出现新的研究结 果从前向的儿个表中叮以看出，现有的许多网络拓扑的参数还没有 确定 另外，分析网络容错件的参数也随着人们的认识不断提出，研究现 有网络的新参数和提出新的网络拓扑模埋是一个很有意义的工作 在第二章，我们将介绍广义f i b o n a c c i 市方体的拓扑结构，着重研 究其容错直径和宽直径，在第三章，我们研究广义f i b a n a c c i 锣方体的 限制连通度最后一章足进一步研究的问题和展望 互联网络容错性质分析 第二章广义f i b o n a c c i 立方体的容错直径和宽直径 2 1 引言 综述中l 三经列出了一些拓扑结构性能参数各种网络拓扑结构性 能并不相同有的直径和平均距离减少了，有的降低了路由算法的算 法复杂度，有的具有更好的嵌入性质 各种网络结构在有好的性能的同时但足也带来了其它的不利因素 比如折叠超咿方体需要额外的硬件开销，交艾立方体的路由算法复杂 度增加嵌入格的膨胀系数大于1 ，等等 由对超市方体深入的研究我们n r 以看出超市方体网络的处理器的 个数随着n 的增加而增长得太快，因而限制了阿的节点数日的选择 h s u l 3 1 i 提出基于f i b o n a c c i 数序列构造的f i b o n a c c i 立方体，且其为 超市方体的子方体研究显示f i b o n a c c i 奇：方体能有效的模拟许多超市 方体卜的算法 f i b o n a c c i 移方体比同阶的超立方体有较少的边，其总的节点数要 比超市方体增长得缓慢f i b o n a c c i 市方体n r 以视为超市方体网络某些 节点失灵的容错网络，其不但具有任意节点的系统结构，同样拥有超 立方体系统的运行模式具体的结构分析和应用分别见参考文献 3 2 1 和【删 大部分的f i b o n a c c i 市方体非h a m i l t o n 阿c o n g a 1 1 3 4 j 证明只有不 到 的f i b o n a c c i 锣方体足h a m i l t o n 阿 为了构造维持f i b o n a c c i 市方体原有的性质，有更好的h a m i l t o n 性质的网络拓扑，j i e w u 1 5 1 提出和f i b o n a c c i 奇：方体构造方法相同而初 始条件不同的广义f i b o n a c c i 奇：方体拓扑结构其直径和连通度已经给 出，但它的网络容错直径，宽直径甘前还没有给出确定的值 在这章中，我主要研究它的网络容错直径和宽直径，证明了它的网 络容错直径和宽直径值都为n 一1 本章的结构安排如下：第二节主要介绍广义菲波那契方体的定义； 第三节介缁广义f i b o n a c c i 市方体的拓扑性质和性能参数，同时研究其 容错直径和宽直径，第四节足结沦 2 2 广义f i b o n a c c i 立方体 n 维广义斐波那契方体我们用e f c ( n ) 来表示 令e f c ( n ) = ( y ( n ) ，e m j ) ，其中y ( n ) 为点集，e ( n ) 为边集， e f c ( n 一1 ) = ( v ( n 一1 ) ，e ( n 一1 ) ) 和e f c ( n 一2 ) = ( v ( n 一2 ) ，e ( n 一2 ) ) ， v ( 3 ) = o ，1 ) ，v ( 4 ) = 0 0 ，0 1 ，1 0 ，1 1 e f c ( n ) 由e f c ( n 一1 ) 和e f c ( n 一2 ) 递归的构成，v ( n ) = o i i v ( n 一 1 ) ul o i w ( n 一2 ) ，其中i | 为毗连，例如0 1 1 1 0 ，1 = 0 1 0 ，0 1 1 两个点在 e f c ( n ) 中有边相连当仅当他们地址的二进制代表系相差一个比特 位n = 3 ，4 ，5 ，6 由阿2 - 1 给出，每个e f c ( n ) 由一个e f c ( n 一1 ) 和一个 e f c ( n 一2 ) 组成 0 厂 一 0 0 0 1 0 0 1 01 10 1 1 ( b ) 0 1 0 00 1 0 1 0 0 1 1 0 1 ( c j 0 0 1 0 1 0 0 1 0 0 1 11 0 1 0 1 0 1 1 ( d ) 冈2 1 ：( a ) e f c ( 3 ) ，( b ) e f c ( 4 ) ，( c ) e f c ( 5 ) ，( d ) e f c ( 6 ) 互联网络容铮睦质分析1 5 由广义f i b o n a c c i 寺方体的构造我们知道，广义f i b o n a c c i 守方体的 连接方式和超立方体相同，其顶点集是超立方体的一部分，凶此j 义 f i b o n a c c i 市方体足超立方体的子图 2 3 广义f i b o n a c c i 立方体的拓扑性质 2 3 1 度和连通度 定理2 1 【1 5 i ：设为广义f i b o n a c c i 证方体中一点，其度表示为d l ， 则；1sd l n 一2 ，由此n r 知连通度为 正明：由于e f c ( n ) 中每个点有n 一2 个比特位，由 3 2 1 ，f c ( n ) 中 的点的最大度为n 一2 ，因此e f c ( n ) 最大的点度为n 一2 ，设表示 e f c ( n ) 中的最小点度，且y ( ，1 ) = o o y ( n 一1 ) u 0 1 0 v ( n 一3 ) u 1 0 v ( n 一2 ) ， 则有m i n r n 一2 + 1 ，7 i a + l ，r n 一2 十l t nsm i n r n 一2 + 2 ，r n 一3 + 1 ，r n 一2 + 1 ， 由r n 一2 r n - a ，我们有r n = r n 一3 + 1 ，由r 3 = 1 ，r 4 = 2 ，r 5 = 2 ，有r n = 翻 2 3 2 点数和边数 由广义菲波那契方体的构造叮知，e f c ( n ) 内所包含的点数为f ( n ) ， 其中f ( n ) 足以f ( 1 ) = 2 和f ( 2 ) = 4 为前两项的菲波那契数列的第n 项 同样我们町以得到广义菲波那契方体的边数为： i e ( n ) l = i e c n 1 ) i + i e ( n 一2 ) i + i y ( n 一2 ) i 其初始条件为i e ( 3 ) i = 1 , 1 e ( 4 ) i = 4 2 3 3 哈密尔顿性质 定理2 2 【1 5 1 ：当n24 时，e f c ( n ) 足一个哈密尔顿阿 2 3 4 直径 如果任意阿点之间的路的长度等于这阿点之间的h a m m i n g 距离， 则称此路为两点间h a m m i n g 距离路 定理2 3 【1 5 1 ：对于e f c ( n ) 中任意两点存在h a m m i n g 距离路 1 6 湖南师范大学硕士学位论文 推论2 4 【1 q ：e f c ( n ) 的直径为n 一2 2 3 5 f c ( n ) 与e f c ( n ) 定理2 5 1 5 ：当n24 时，f c ( n ) 足e f c ( n ) 的真千图 征明：由于f c ( n ) 与e f c ( n ) 阿点之间的连接规则相同，我们只 需要证明e f c ( n ) 的点集包含f c ( n ) 的点集令v ( n ) 和( n ) 分别 表示f c ( n ) 与e f c ( n ) 的顶点集，用归纳法汪明，显然v ( 4 ) c ( 4 ) ， v ( 5 ) c k ( 5 ) ，假设对于所有的n 6 时， 由v ( n ) = o y ( n 一1 ) u l o f i y ( t i 一2 ) ，我f 仃有y ( k ) = o l l v ( k 一1 ) u l o l l v ( k 一2 ) c o | | ( 一1 ) u 1 0 1 1 h 一2 ) = ( ) 2 3 6 容错直径和宽直径 容错直径与宽直径的定义前面l 二经介绍，这里不在敖述 下豳_ 将定义一些记号：如果p 表示一条路，则i p i 表示此路的长 度，如果p 表示从“到”的路，而“t ”为p 卜一条边，则p 一 u ” 表 示p 减去“1 ”边而剩下的“到“l 的路如果t 表示“- 到”的路，我 们用 u “l u t 表示“经过u t 和t 上点到”的路对于e f c ( n ) 中任意 一点w ，表示为( n 。n 2 ) t b 。b 2 巩，即表示长为n 一2 的二进制串中有1 个 n l d 2 和一个b l b 2 b t ，n i ，6 i o ，1 ) 引理2 6 ：y ( n ) ，女= 胯1 ，有d f ( e f c 即) ) n 一1 ，n 3 征明：假设容错集fc ( ) ，i f i = k 一1 ，则至少有一点gf ，显 然任何由“到”的不经过f 中点的路必须经过u ，当n 为奇数时， 令u = ( 0 1 ) 孚o o l ，“= ( 0 1 ) - 学0 1 1 ，口= ( 1 0 ) 孚1 0 0 ，当n 为偶数时，令 u = ( 0 1 ) 孚0 1 ，t ，= ( 0 1 ) 孚1 1 ， = ( 1 0 ) 孚0 0 由定理1 ，t ，和口中有最短 路，则“到 经过t ，的最短路长为n 一1 ，因此d f ( e f c ( n ) ) n 一1 ，n 3 ， 征毕! 互联网络容铮眭质分析 1 7 引理2 7 ：对于e f c ( n ) 中任意两个不同点“，”，n23 , k = f ；1 ， 则u ， 中至少有k 条路l l ，l 2 “满足i l i isn 一1 ，1 i k 汪明：采用归纳法n 6 时，结果显然成市对于n 27 ，假设 对于任意的l n ，e f c ( 1 ) 中任何两个不同点存在嘲条不交路长度 均小于l 一1 现在我们将“，口用二进制表示为 令= 丁n - 3 我们将对e f c ( n ) 作罔2 - 2 中的划分，在后面的证明 中，我们将用到卜述划分，后血的阿中将不再杯出划分后的子图名称 我们分三种情形讨论，在所有的情形中，对于j 舰 o l o ，o o o ，0 0 1 ，1 0 0 ，l o l ， 如果“e j hf t 在h 内有s 个邻点，则 “i l lstss ，表示u 在 h 内的邻点集合 王尹m e o o oe 瑚 iiii ii ili e o o le l o t 阿2 - 2 ：e f c ( n ) 的划分 湖南师范大学硕士学位论文 世 r “， q ： ： j ： ： r ： ： ! ： ! ： 钉 t ， e ( n 一2 )e ( n 一2 ) 阿2 - 3 ：情形1 2 情形1 ；t ，l 一2 = 一2 = 0 情形1 1 ：“。- 3 = 一3 = 1 由假设在伊m 内部“，”中存在满足条件的f 条不交路，找”，”在 e 咖内的邻点t ，t ，令t 为，t i ，在e 咖中的最短路，则构造另外一条 路l f + l 为“，t ，t ，静，l l w + l isn 一5 + 2 = 几一3 情形1 2 ；“。一3 = 一3 = 0 由假设，在e f c ( n 一1 ) 内，至少有孚1 条不交路中的l l ，l 2 “满 足条件令，t ，分别表示u ，”在e f c ( n 一2 ) 内的邻点，令r 表示t ，t ， 在e f c ( n 一2 ) 内的最短路，则构造另外一条路l f + l 为“，t ，长 度小于n 一2 ，见阿2 - 3 情形1 3 ：u 。一3 = 目五 情形1 3 1 ：t ，l 一= _ 4 互联同络容铮| 主质分析1 9 牡 r t 咖1 0 0 j1 t l l j 妒 ： ： t t 岛 ： ： 伊1 0 v 1 0 0 阿2 - 4 ：情形1 3 1 找u 在俨内的邻点俨，则由假设在e o o o 内t - 咖和口中存在 条路片恳昂，满足长度小于n 一4 由于t 和在e 咖和e o l o 中的 构造完全相同，则对于e 咖中u 咖的任一邻点“妒有伊加中u 的邻点 t 与之对应，即u 叩，u t 中分别有互不相交的边相连 令正= 只一 唧t 掣 ，1 茎i s 令厶为啦，“严口，找 ，u 咖 在e ”内的邻点口枷，u 1 0 0 ，令r 表示u i 0 ，u 瑚在e i o o 内的最短路，则 构造另外一条路l f + l 为t i ，一，t l g 0 - l 口瑚，口，见阿2 - 4 情形1 3 2 ：一4 = 一u n - - 4 令“咖，t ，0 表示口在e 咖中的邻点，则由假设，在e 咖内“咖，v 0 0 0 中有条路p l ，恳昂，1 只i5n 一4 ，由于俨在俨内的邻点n r 能比”在伊吡内的邻点多一个，除此点之外”的邻点和r o o o 的邻点相 互对应且有互相不交的边相连 如果只，b 乓有某条路经过此点，不妨设为昂，如果没有，则 任取一条路为昂令正= 只一 “咖u 严，俨”啪 ，1 t f 一1 ，构造“ 到口的路厶为 ，蛳，“严鸟t p ，地，口，i 厶l n 一2 ，lsi f 一1 ，令 t = p k , 一 u 咖秽，构造乓为刚f ，秽三俨，” 湖南师范大学硕士学位论文 最后构造l f + l ，令u ”，口1 0 1 分别表示“咖， 在e f c ( n 一2 ) 中的邻 点，且l 为l ， 1 0 1 在e f c ( n 一2 ) 中的最短路，则令l f + l 为u ，“0 0 0 ，u l 三 仃1 0 17 口， l l f + 1 l n 一1 见羽2 - 5 l i ，+ 1 “0 0 0 ；， 4 。 z u t 正 工fjt f - 0 毒 i 。 割 i o j 阿各5 ；情形1 3 2 情形2 ：“。一2 = 一2 = 1 同情形1 2 类似n r 证，见阿2 - 6 情形3 ：- 2 = 砝i 情j 侈3 1 j _ 3 “4 q = 1 0 ，- 3 4 = 0 0 令“咖， 咖为u ，口在e o o o 中的邻点，则由假设咖和口咖内有条 不交路尸l ，b 丹满足条件令正= 只一 “咖“? 0 0 ，t 秽”咖 ，构造厶为 “，t i ，“严与母”，口，i 厶ls n - 1 ，1 s i 一1 ，令巧= 助一 l 咖垆 ， 构造“为，f ，“妒二马口咖，n 最后构造幻+ t ，令u 瑚为t 0 在e m 内的邻点，由假设口，“瑚 在e 瑚内至少有条不交路满足长度小于n 一4 ，由于工l ，l 2 “一l 仅占用”在曰瑚内一1 个邻点，则内垒少有一条路丁满足 tn 厶= 巧，1si s 一1 ，i t isn 一4 连接 ，“瑚构造“为 互联网络容锌睦质分析 ，u 0 0 ，u 1 0 0 - ! i ， i l f i ，i 一2 ，见i 习2 - 7 “， ： q ! ： ! ： 扩 ： i ： ； ： t ， 勘 阿2 - 6 ：情形2 情形3 2 ：t t i 一3 u 。一4 = 1 0 ，v n 一3 一4 = 0 1 找“在俨内的邻点“1 1 0 0 ，口在e o o l 内的邻点v o o l 以及t j 0 0 1 在e o o o 内 的邻点i ) 0 0 0 ，由假设u ”，1 3 0 0 0 中有f 条不交路r ，b 斥满足i b l s n - - 4 同情形1 3 2 选择乓，则令乃= 只一 “咖t 0 ，t 尹”唧 ，构造厶为 札，牡，“p 1 0 醒，妒1 ，钆，口，i l , is 仃一1 ，1 i 一1 令珏= 昂一 俨u 垆 ，构造l k , 为u ，“f ，秽卫”0 0 0 ，”唧，” 最后构造l p + i ，找u 咖，口在e l 内的邻点u 1 0 0 ，口”，i 1 令t 为e l o o 内“1 0 8 ，i j l 0 0 之间的最短路，则构造“+ l 为“，俨，“瑚三 蛐，口，见阿2 - 8 湖南师范大学硕士学位论文 趴：”么 ： 。rj 4 斧t ： ， 4 2 9 0 掣严 ： 仇 ： 知i ： 网2 7 ：情形3 1 l 、 ，删 二： | ：“女 + t 一“? 0 0 u 0 0 0 _ 】 0 0 0 0 0 1 。 0 0 1 陶2 - 8 ：情形3 2 互联网络容锌睦质分析 情形3 3 ：- 3 一4 = 0 0 ，一3 一4 = 0 0 口在e o o o 内的邻点为”咖，由假设“，伊。垒少存在1 4 条路p