（应用数学专业论文）容错网络中若干问题研究.pdf

摘要 摘要 本文考虑互连网络中的容错性和容错网络的路嵌入问题习知，互连网络的 拓扑结构可以用图g = ( ke ) 来作为数学模型，图g 中的点表示互连网络中的 元件，g 中的边表示元件之间的通信连线那么，图g 的点连通度圪( g ) 和边连通 度入( g ) 则是该互连网络可靠性的重要度量参数它们表明对应的互连网络可以 容许仡( g ) 一1 个元件或者入( g ) 一1 条连线同时发生故障的情况下，剩余网络的 元件之间仍能保持通信所以，图的点连通度或者边连通度越大，它所模拟的互连 网络的可靠性越高目前，互连网络最广泛采用的拓扑结构是n 维超立方体q n ， 它的点连通度和边连通度都是n 为了更准确地度量网络的容错性，人们根据网络应用的实际推广图的连通度 概念到超连通度图g 的超点连通度k 。( g ) ( 或者超边连通度九( g ) ) 是最小点数 ( 或者边数) ，这个数目的点集( 或者边集) 从g 中移走会导致剩下的图不连通并且 不含孤立点 e s f a h a n i a n ( 1 9 8 9 ) 已经证明：佗维超立方体q n 的超点连通度和超边连通度 都是2 礼一2 这意味着，即使q n 中有2 n 一3 条边同时发生故障，只要确保每个 点关联至少一条非故障边，那么q n 中任何两个非故障点之间仍然存在由非故 障边组成的路徐俊明等人( 2 0 0 3 ) 证明了：当q nm 4 ) 至多有2 钆一3 条故 障边，而且每个点关联至少一条非故障边时，对于q n 中任何两点u 和u ，如果它 们之间的距离d 满足2 dsn 一2 且n 4 ，那么乱和u 之间存在长不超过 d + 4 且不含故障边的路另一方面，c h a n 和l e e ( 1 9 9 1 ) 证明了：q nm 3 ) 存在 2 佗一4 条故障边，而且每个点关联至少两条非故障边，但q n 中不存在不含故障边 的h a m i l t o n 圈这个事实说明：如果q n ( n 3 ) 有2 n 一4 条故障边，而且每个点 关联至少两条非故障边，那么，对于一条非故障边u 口，q 竹中有可能不存在不含故 障边且长为2 n 一1 的钆可路 本文证明了：如果q n ( 佗3 ) 至多有2 礼一5 条故障边，而且每个点关联 至少两条非故障边，那么对q n 中任何不同两点钆和钉，其距离为d 和满足 d + 4 粤2 n 一1 和z d 三0 ( r o o d2 ) 的整数z ，q n 中存在一条不含故障边且长 为它的g v 路这个结果改进了许多有关超立方体网络边容错泛圈性和泛连通性 的已知结果，也为超立方体网络的高容错性提供更有力的理论证据 本文的另一部分是研究超立方体的变形网络v q 住和超立方体的推广置换 图( g o ，g t ；m ) 的超点连通度和超边连通度证明了v q n 的点连通度和边连通度 都是仡，超点连通度和超边连通度都是2 n 一2 对于两个k 正则k 连通图g 0 和 摘要 g 1 的置换图g = a ( a o ，g l ；m ) ，我们给出厂k 。( g ) 圪( g ) 和a 。( g ) a ( a ) 的 充分和必要条件，圪。( g ) = 2 k 和入。( g ) = 2 k 的充分条件作为应用，超立方体网 络q n ，纽立方体网络t q n ，交叉立方体网络c q n ，m 6 b i u s 立方体网络m q n ，局 部纽立方体网络l q 他和变形超立方体网络v q n 的超点连通度，超边连通度，限 制点连通度和限制边连通度都等于2 礼一2 这些结果为这些网络的可靠性和容错 性提供更精确的度量 关键词：连通度泛圈泛连通超立方体变形超立方体 i v a b s t r a ( 了 a b s t r a c t t h i sd i s s e r t a t i o nc o n s i d e r st h ef a u l tt o l e r 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 sa n dt h e p r o b l e me m b e d d i n gp a t h si n t of a u l t t o l e r a n tn e t w o r k s i ti sw e l l - k n o w n t h a tw h e nt h e u n d e r l y i n gt o p o l o g yo fa ni n t e r c o n n e c t i o nn e t w o r ki sm o d e l e db yac o n n e c t e dg r a p h g = ( ke ) ，w h e r ev i st h es e to fe l e m e n t sa n dei st h es e to fc o m m u n i c a t i o nl i n k s i nt h en e t w o r k ，t h ev e r t e x c o n n e c t i v i t y 仡( g ) a n de d g e c o n n e c t i v i t ya ( g ) a r ei m p o r t a n t m e a s u r e m e n t sf o rf a u l tt o l e r a n c eo ft h en e t w o r k t h i si m p l i e st h a tt h en e t w o r kc a l l t o l e r a t e 厅( g ) 一1e l e m e n tf a i l u r e so ra ( g ) 一1l i n kf a i l u r e st or e m a i nc o n n e c t e d t h u s ， t h eh i g h e rt h ev e r t e x c o n n e c t i v i t yo rt h ee d g e c o n n e c t i v i t yi s ，t h em o r er e l i a b l et h e n e t w o r ki s a tt h ep r e s e n tt i m e ，t h e 仡- d i m e n s i o n a lc u b eo rt h eh y p e r c u b e ，d e n o t e db yq n ，i s o n eo ft h em o s t p o p u l a r , v e r s a t i l ea n d e f f i c i e n tt o p o l o g i c a ls t r u c t u r e so fi n t e r c o n n e c t i o n n e t w o r k s t h eh y p e r c u b eh a sm a n ye x c e l l e n tf e a t u r e s ，a n d ，t h u sb e c o m e st h ef i r s t c h o i c ef o rt h et o p o l o g i c a ls t r u c t u r eo fp a r a l l e lp r o c e s s i n ga n dc o m p u t i n gs y s t e m s i t h a sb e e np r o v e dt h a tt h ev e r t e x - c o n n e c t i v i t ya n dt h ee d g e c o n n e c t i y i t yo fq 付a r eb o t h 礼 t om e a s u r ef a u l tt o l e r a n c eo fn e t w o r k sw e l la n dt r u l y , m o r er e f i n e di n d i c e st h a n v 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 , s u p e rv e r t e x c o n n e c t i v i t ya n ds u p e re d g e c o n n e c t i v i t yw e r ep r o p o s e d t h es u p e rv e r t e x c o n n e c t i v i t y ( g ) ( r e s p s u p e re d g e - c o n n e c t i v i t y 入s ( g ) ) o fa c o n n e c t e dg r a p hgi st h em i n i m u mn u m b e ro fv e r t i c e s ( r e s p e d g e s ) w h o s er e m o v a lr e s u l t si na d i s c o n n e c t e dg r a p ha n dc o n t a i n sn oi s o l a t e dv e r t i c e s i n1 9 8 9 ，e s f a h a n i a ns h o w e d ( q n ) = 入s ( q n ) = 2 n 一2f o rt h en d i m e n s i o n a l c u b eq n ，w h i c hi m p l i e st h a ti f2 n 一3v e r t i c e so re d g e sf a i la tt h es a m et i m ei nq 佗a n d e a c hv e r t e xi si n c i d e n tw i t ha tl e a s to n ef a u l t f r e ee d g e ，t h e nt h e r ee x i s t saf a u l t f r e e 乱u p a t hi nq nf o ra n yt w od i s t i n c tf a u l t f r e ev e r t i c e s 乱a n d ui nq n o nt h eo n eh a n d ， i n2 0 0 3 ，x ue ta ls h o w e dt h a tw h e nq nh a sa tm o s t2 n 一3f a u l t ye d g e sa n de a c hv e r t e x i si n c i d e n tw i t ha tl e a s to n ef a u l t f r e ee d g e ，t h e r ee x i s t saf a u l t - f r e e 乱u p a t ho fl e n g t h a tm o s td + 4i nq nf o ra n yt w od i s t i n c tv e r t i c e s 让a n d ”i nq n ，w h e r edi st h ed i s t a n c e b e t w e e nua n d i nq n ，2 冬ds 钆一2a n d 钆4 o nt h eo t h e rh a n d ，i n1 9 9 1 ，c h a n a n dl e es h o w e dt h a tt h e r ei saq t lw i t h2 n 一4f a u l t ye d g e sa n de a c hv e r t e xi si n c i d e n t w i t ha tl e a s tt w of a u l t f r e ee d g e s ，a n di tc o n t a i n sn of a u l t f r e eh a m i l t o nc y c l e s ，w h i c h s h o w st h a tf o raf a u l t - f r e ee d g eu ，q nc o n t a i n sn of a u l t f r e e 钍u p a t ho fl e n g t h2 n 1 v a b s t ra c t i nt h i sd i s s e r t a t i o n ，w es h o wt h a tf o ra n yt w od i s t i n c tv e r t i c e sua n dvw i t hd i s t a n c e di nt h eh y p e r c u b eq n ( 钆3 ) w i t ha tm o s t2 n 一5f a u l t ye d g e sa n de a c hv e r t e xi s i n c i d e n tw i t ha tl e a s tt w of a u l t f r e ee d g e s ，t h e r ee x i s t saf a u l t f r e eu u p a t ho fl e n g t h 它 i nq nf o re v e r yzw i t hd + 4 粤2 n 一1a n dz d 三0 ( m o d2 ) t h i sr e s u l ti m p r o v e s s o m ek n o w nr e s u l t so ne d g e - f a u l tp a n c y c l i t ya n dp a n c o n n e c t i v i t yo fh y p e r c u b e s t h eo t h e rp a r to ft h i sd i s s e r t a t i o nc o n s i d e r st h ef a u l tt o l e r a n c eo ft h en d i m e n s i o n a l v a r i e t a lh y p e r c u b ev q na n dt h ep e r m u t a t i o ng r a p h ( g o ，g x ；m ) ，w h i c ha r eav a r i a t i o n a n dag e n e r a t i o no ft h eh y p e r c u b en e t w o r k ，r e s p e c t i v e l y w es h o wt h a t ，c ( y q n ) = a ( v q n ) = na n d ( v o n ) = 入。( v q n ) = 2 n 一2 f o rt h ep e r m u t a t i o ng r a p h g = a ( g o ，g x ；m ) o ft w ok - r e g u l a rk - c o n n e c t e dg r a p h sg oa n dg 1 ，w eg i v eas 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 nf o r 心8 ( g ) 圪( g ) a n d 入s ( g ) 入( g ) ，a n das u f f i c i e n t c o n d i t i o nf o r ，c s ( g ) = 2 ka n d 入8 ( g ) = 2 尼a sa p p l i c a t i o n s ，w es h o wt h a tt h es u p e r v e r t e x c o n n e c t i v i t ya n dt h es u p e re d g e - - c o n n e c t i v i t yo fs o m ew e l l - k n o w ni n t e r c o n n e c - t i o nn e t w o r k ss u c ha s 亿一d i m e n s i o n a lh y p e r c u b e s ，t w i s t e dc u b e s ，c r o s sc u b e s ，m 6 b i u s c u b e s 1 0 c a l l yt w i s t e dc u b e sa n dv a r i e t a lh y p e r c u b e sa r eb o t l l2 n 一2 t h e s er e s u l t sc a l l p r o v i d em o r ea c c u r a t em e a s u r e m e n t sf o rr e l i a b i l i t ya n df a u l tt o l e r a n c eo ft h es y s t e m w h e n m e ya r eu s e dt om o d e lt h et o p o l o g i c a ls t r u c t u r eo fal a r g e s c a l ep a r a l l e lp r o c e s s - i n gs y s t e m k e y w o r d s ：c o n n e c t i v i t y , p a n c y c l c ，p a n c o n n e c t e d ，h y p e r c u b e ，v a r i e t a lh y p e r c u b e v i 一般数学符号 s ：= v s ，scv 蚓：集s 中元素数目 ：笛卡尔乘积 卜1 ：不小于7 的最小整数 p j ：不大于r 的最大整数 u ：两集之并 n ：两集之交 ：子集 c ：真子集 记号索引 图运算 g 1ug 2 ：两个子图g 1 和g 2 的并 g l g 2 ：两个图g 1 和g 2 的笛卡尔乘积 g z ：从图g 的删去顶点z 及其关联的边集 g e ：从图g 的删去边e ( 不包含两端点) g s ：从图g 的删去顶点集s 及其关联的边集 g + e ：添加新边e 到图g g + b ：添加边集b 到图g 日g ：图日是图g 的子图 日cg ：图日是图g 的真子图 记号索引 用英文字母表示的图论符号 d a ( x ，y ) ：图g 的点z 与点y 之间的距离 d ( g ) ：图g 的直径 d a ( z ) ：图g 的点z 的度 d a ( x ) = l e a ( x ) l ：图g 的点集x 与点集叉之间的边数 e ( g ) ：图g 的边集 髓( x ) ：图g 的点集x 与点集叉之间的边集 夕( g ) ：图g 的围长，即g 的最短圈的长 g f 翻：图g 的由点子集s 导出的子图 ：n 阶完全图 k m n ：m + n 阶完全2 部分图 k 1 n ：他+ 1 阶星 m q n ：n 维m b b i u s 超立方体 g c ( z ) ：图g 中点z 的邻点集 n c ( s ) ：图g 中点子集s 的邻点集 q n ：死维超立方体网络 y ( g ) ：图g 的点集 x y e ( g ) ：图g 中端点为z 和y 的边 z 可路：连接z 和y 的路 用希腊文字母表示的图论符号 6 ( g ) ：图g 的最小度 ( g ) ：图g 的最大度 e ( g ) ：图g 的边数 7 2 记号索弓 托( g ) ：图g 的点连通度 协( g ) ：图g 的限制点连通度 n s ( g ) ：图g 的超点连通度 a ( g ) ：图g 的边连通度 ( g ) ：图g 的限制边连通度 入。( g ) ：图g 的超边连通度 ( g ) ：图g 的最小边度 话( e ) ：图g 中边e 的度 7 3 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对 本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密后也遵守此规定。 殳叫v 作者签名： 乙八d 年6 第1 章图论的概念和网络背景 大规模超级计算机系统是由若干台计算机或者若干个处理器等其他元件通 过通信线路按照一定规则互相连接起来构成的系统这个系统使得信息的收集、 存储、加工和传播不再是互相分离的几个部分，而是一个有机的整体系统中元 件之间的连接方式称为该系统网络的拓扑结构在分析网络拓扑结构时，人们通 常以图作为数学模型，图中的点代表系统中的元件，而一对元件之间的直接通信 联系则用连接这对点的边来表示研究网络的拓扑结构问题就归结为图的结构问 题因此，图是网络拓扑结构的数学模型，我们可以通过图论方法来研究网络的拓 扑结构，网络拓扑的性能可以通过图的性质和参数来度量( 参见t 6 3 j ) 系统的网络拓扑可以用图来模拟，因此网络与图论有着密切的关系事实证 明，图是网络拓扑结构设计和分析的最有用的数学工具，并已被计算机和信息科 学家广泛接受和采用( 参见【2 2 ，3 5 3 7 ，6 3 1 ) 本章将简单介绍图和网络的基本概念以及 在以后讨论中要用到的图论记号、概念和将要用到的基本结果本文用到而没有 定义的有关图和网络术语和记号可参见徐俊明的图论及其应用【6 2 】和组合 网络理论【6 3 1 1 1图与网络 本文所考虑的图为无向图设g = ( k e ) 是图( g r a p h ) ，其中y 非空称为点 集( v e r t e x s e t ) ，e 称为边集( e d g e - s e t ) ，v 中元素的个数l y l 和e 中元素的个数i e l 分别称为该图的点数( n u m b e ro fv e r t i c e s ) 或阶( o r d e r ) 和边数( n u m b e ro fe d g e s ) 事实上，e 是v v 中的子集对于边e = z 可e ，z ，妙称为边e 的端点，边的两 端点称为相邻的( a d j a c e n t ) ，也叫e 为与点z 或者可关联的边( i n c i d e n te d g e ) 任何两个点之间都有边相连的图称为完全图( c o m p l e t eg r a p h ) 7 , 阶完全图记 为 若图的点集能划分为两个非空子集x 和y 使得x 中任何两点之间无边相 连并且y 中任何两点之间也无边相连，则称该图为2 部图( b i p a r t i t eg r a p h ) ， x ， y 】- 称为2 部划分( b i p a r t i t i o n ) 2 部划分为 x ，y ) 的2 部图记为( xuke ) 2 部 图( xuke ) 称为完全2 部图( c o m p l e t eb i p a r t i t eg r a p h ) ，如果x 中每个点与y 中 每个点之间均有边相连如果l x i = m ，l y l = n ，那么2 部划分为 称为与z 关联的边集显然，i n o ( x ) i = i e c ( x ) i 对任何z v ( c ) 成立d c ( x ) = i ) l 称为z 的度( d e g r e e o fav e r t e xz ) 度为d 的点称为d 度点( v e r t e xo fd e g r e e d ) ，0 度点称为孤立点( i s o l a t e dv e r t e x ) g 称为d 正则的( r e g u l a r ) ，如果g 中每个 点都是d 度点 图g 的点度和边数之间有下列关系( 参见【6 2 】中定理1 i 及其推论) 定理1 3 设g = ( ke ) 是任意的图那么 2 i e i = d v ( x ) ， 茁v 并且奇度点的数目是偶数 对于e = x y e 哆) ， 缸( e ) = d g ( z ) + d g ( y ) 一2 称为边e 的度( d e g r e eo fa l le d g ee ) ； ( g ) = m i n 毒g ( e ) ：e e ( g ) ) 称为图g 的边度( e d g e d e g r e e ) a ( c ) = m a x d e ( 。) ：z y ( g ) ，和 6 ( g ) = m i n d v ( x ) ：z y ( g ) 】 分别称为g 的最大度( m a x i m u md e g r e e ) 和最小度( m i n i m u md e g r e e ) 图日称为g 的子图( s u b g r a p h ) ，记为日冬g ，如果v ( h ) v ( c ) 且e ( h ) e ( g ) g 的子图日称为支撑子图( s p a n n i n gs u b g r a p h ) 如果v ( h ) = y ( g ) 设s 是v ( c ) 的非空子集g 中由s 导出子图( i n d u c e ds u b g r a p h ) 记为g 【s 】， 它的点集为s ，边集为g 中其两端点都在s 中所有边记号g s 表示导出子 图g v 翻 设b 是e ( c 1 中的非空子集g 中由b 导出的子图( e d g e i n d u c e ds u b g r a p h ) ， 记为g b 】，它的点集为b 中边端点集，它的边集为b 4 第一章图论的概念和网络背景 g 一日表示g 的支撑子图c e b 】同样地，g + f 表示在g 中添加边集f 后得到的图 子图被用来表示子网络如果g 是互连网络的拓扑结构，那么，g + f 表示为 了改进网络的性能而添加连线集f 而得到的网络；g s 和g b 分别表示网络 包含一个故障点集s 和故障连线集b 设g 1 和g 2 是g 的两个子图g 1 和g 2 是不交的( d i s j o i n t ) ，如果它们没 有公共的点；g 1 和g 2 是边不交的( e d g e d i s j o i n t ) ，如果它们没有公共的边g 1 和g 2 的并( u n i o n ) ，记为g 1ug 2 ，是g 的子图，它的点集为y ( g 1 ) uv ( c 2 ) ，且 边集为e ( g 1 ) ue ( g 2 ) 如果g l 和g 2 是不交的，有时记g 1ug 2 为g l + g 2 如果v ( c 1 ) nv ( c 2 ) 是非空，同样地可以定义g 1 和g 2 的交( i n t e r s e c t i o n ) ，记 为g 1ng 2 设scv ( g ) ， 称为s 的邻集； n c ( s ) = 秒v ( c s ) ：x y e ( g ) ，z s ) e g ( s ) = x y e ( g ) ：z s ，y v ( c s ) ) 设z 和y 是图g 的两个点g 中长为k 的z 可链( w a l k 或者c h a i n ) 是点序 列w = ( z o ，z 1 ，x k ) ，其中对每个t = 1 ，2 ，k ，一l x i 是g 的边，( ) = k 称为链长( 1 e n g t h ) 点不同的链称为路( p a t h ) 令p = ( 缸，t ，z ，y ，z ，钉) 是一条长至少为2 的u u 路p 中的一个内点 z 划分p 为两段我们用记号p ( u ，z ) 表示尸中从u 到z 的一段( 7 2 ，t ，z ) ；用 记号p ( y ，可) 表示p 中从y 到可的一段( y ，z ，口) 利用这些记号，我们能将伽 路表示成尸= p ( 乱，z ) + x y + 尸( 可，u ) ，其中叫是p 中一条边 起点和终点相同的路称为圈( c y c l e ) 长为奇数的圈称为奇圈( o d dc y c l e ) ，长 为偶数的圈称为偶圈( e v e nc y c l e ) 长为k 的圈称为k 圈( k - c y c l e ) 如果g 含圈， 那么g 中最短圈长称为围长，记为g ( c ) ( g i r t h ) 路是总线网络( b u sn e t w o r k ) 或者线形阵列网络( 1 i n e a ra r r a yn e t w o r k ) 的拓扑 结构圈是环网( 1 0 0 pn e t w o r k ) 的拓扑结构；总线网和环网和单环网络是最通用 的，最简单的，而且是最有用的互连网络之一 现在叙述一个通过圈的奇偶性来判断图是否是2 部分图的准则，( 参见 6 2 】中 定理1 4 及其推论) 定理1 2 图g 是2 部分图当且仅当g 不含奇圈 i 5 第一章图论的概念和网络背景 度量互连网络性能最有用的参数或许是通过该网络将信息从它的源送到目 的地的传输延迟( 或者时间延迟) 在存储转发型互连网络中，信息从它的源到达 目的地往往需要经过若干个中间点的存储和转发才能到达它的目的地信息的传 输延迟或者信号减弱常常与它经过的点数是成比例的显然，信息传输所经过的 点数越小，网络的通信效率就越高。而且，处理器之间的互连费用是随着网络处理 器之间的物理连线的增加而增大图的距离和直径概念在分析互连网络有效性中 起了重要作用，为度量网络的传输延迟提供了度量参数 在连接两点z 和可之间的所有路中，长度最短的路称为最短z 可路( s h o r t e s t p a t h ) 最短路的长称为点z 与点y 之间的距离( d i s t a n c e ) ，记为d v ( x ，可) 参数 d ( g ) = m a x d v ( x ，y ) ：v z ，y y ( g ) 称为g 的直径( d i a m e t e r ) 如果图g 表示存储转发型互连网络的拓扑结构，信息在每个顶点的存储转 发的时间都是一样的，那么图的距离和直径直接刻划了该网络的传输延迟为了 改进或者提高网络传输的有效性就必须使对应的图有最小的直径正是由于这个 原因，图的直径在文献中己引起了相当多的研究兴趣 设m 是e ( a ) 的非空子集若m 中任何两条边在g 中均不相邻，则称m 为g 的一个匹配( m a t c h i n g ) g 中与m 中边关联的顶点称为m 饱和点( s a t u r a t e d v e r t e x ) 若m 饱和g 中所有点，则称m 为g 的完备匹配( p e r f e c tm a t c h i n g ) 两个图g 和日称为是同构的( i s o m o r p h i c ) ，记为g 垡日，如果存在双射 p ：v ( a ) _ v ( h ) 满足相邻性条件： ( z ，y ) e ( g ) ( p ( z ) ，p ( 可) ) e ( 日) 这样的的双射口称为图g 与日之间的同构( i s o m o r p h i s m ) 图g 的自同构( a u t o m o r p h i s m ) 是g 到自身的同构，即v ( a ) 上保相邻性条 件的置换 如果对图g 中任何两个项点z 和y ，存在一个自同构p 使得y = p ( z ) ，那么 称图g 是点可迁的( v e r t e x t r a n s i t i v e ) 显然，点可迁图一定是正则的点可迁是一个非常有用而且很强的图论概念 如果互连网络的拓扑结构是点可迁图，那么该网络中任何点发生故障不影响剩余 网络的结构换句话说，该网络具有高度的对称性，从任何点来看该网络都是一样 的同时，网络的这种性质有利于算法的设计和模拟，也有利于各种性能度量参数 的计算因此，人们希望设计出来的网络拓扑具有点可迁性 同样的可以定义图的边可迁性如果对图g 中任何两条边z 可和伽，存在一 个自同构p 使得 u ， ) = p ( z ) ，口( 可) ，那么称图g 是边可迁的( e d g e t r a n s i t i v e ) 6 第一章图论的概念和网络背景 1 3 图的连通度与网络的容错性 设z 和y 是图g 中两个不同的点若g 中存在连接z 和可的路，则称z 和 可是连通的( c o n n e c t e d ) 若g 中每对点都是连通的，则称g 为连通图( c o n n e c t e d g r a p h ) 反之为非连通图( d i s c o n n e c t e dg r a p h ) 互连网络的可靠性( r e l i a b i l i t y ) 是评估网络性能的重要概念高可靠性的互连 网络一直是网络设计者追求的重要目标之一 影响可靠性的因素很多我们只从网络的拓扑结构上考虑硬件故障对网络可 靠性的影响，即在网络结点和( 或) 连线发生故障时，对数据传输可靠性的影响也 就是说当部分处理机或连线发生故障时，剩余的子网络中各结点之间仍能正常工 作，这种可靠性，计算机和信息类文献上习惯称为容错性( f a u l tt o l e r a n c e ) 网络容错性的实质是当故障发生时，剩余网络的重组能力 任何高性能网络，个别组件和( 或) 连线在运行过程中失灵是难免的我们所 说的网络容错性是指该网络能容忍多少组件和( 或) 连线同时失灵，剩余的子网 络中各结点之间仍能继续保持通信或者保持某些特有的性质 度量网络容错性的一个重要参数就是该网络模拟图的连通度 设z 和y 是连通度图g 中两个不同的点，9 是g 中z 与可之间的路集 若于中任何两条路只和b 均有y ( 只) ny ( 弓) = z ，可 ，则称于是g 中内 点不交的( i n t e r n a l l yv e r t e x d i s j o i n t ) x y 路集；著9 中任何两条路只和只均有 e ( 最) ne ( p j ) = d ，则称于是g 中边不交的( e d g e d i s j o i n t ) x y 路集我们用 白( z ，y ) 和r l v ( x ，y ) 分别表示g 中内点不交和边不交的z 可路的最大条数 若存在一个非空真子集scv ( g ) z ，y ) 使得g s 中不存在z 秒路，则称 s 为g 中z y 分离集( s e p a r a t i n gs e t ) 具有最少点数的z 秒分离集称为最小( z ，y ) 分离集用k g ( z ，y ) 表示g 中最小z 可分离集中的点数若存在一个非空子集 bce ( g ) 使得g b 中不存在z 可路，则称j e 7 为g 中z 可截边集( c u t e d g e s e t ) 具有最少边数的x y 截边集称为最小( z ，y ) 截边集用入g ( z ，y ) 表示g 中最小 ( z ，y ) 截边集中的边数 由定义，我们立即有 知2 7 ，可) n a ( x ，可) ； r a ( x ，y ) a g ( z ，) 事实上，上面两个不等式的等号都是成立的这就是图论中著名的m e n g e r 定 理，它阐述了上述四个参数之间的关系，是互连网络拓扑结构设计和可靠性、容 错性分析的基础，叙述如下( 参见【6 2 1 中的定理4 2 和4 3 ) ： 定理1 3 ( m e n g e r 定理) 设z 和y 是d 中不同的两个点，则 7 第一章图论的概念和网络背景 f j ) r c ( x ，y ) = i g ( x ，可) ； f 2 j 幻( z ，y ) = n a ( x ，可) ，如果x y 譬e ( g ) 设g = ( ke ) 是连通图若y 的子集s 使得g s 不连通，则s 称为g 的 点割( v e r t e x c u t ) 若g 不是完全图，则g 必有点割定义 k ( g ) = m i n i s i ：s 是g 的点割) 为g 的连通度( c o n n e c t i v i t y ) 若圪( g ) 惫，则称g 为k 连通的 若e 的子集b 使得g b 不连通，则b 称为g 的边割( e d g e c u t ) 易知，任 何连通度图都有边割，定义 入( g ) = m i n i b l ：b 是g 的边割 为g 的边连通度( e d g e c o n n e c t i v i t y ) 若入( g ) k ，则称g 为尼边连通的 w h i t n e y 于1 9 3 2 年首次发现了图g 的连通度圪( g ) ，边连通度a ( g ) 和最小 度5 ( g ) 之间有的关系，这就是著名的w h i t n e y 不等式( 参见【6 2 1 中的定理4 4 ) 定理1 4 ( w h i t n e y 不等式)对任何连通图g ，k ( g ) a ( g ) 6 ( g ) w h i t n e y 还给出了图是七连通或尼边连通的充分必要条件，有时称它为 w h i m e yk 连通判别准则( 参见【6 2 】定理4 5 ) 定理1 5 设k 1 ，并且设g 是( k + 1 ) 阶连通图则 ( ，j ) k ( g ) 忌当且仅当( z ，可) 忌，对任意的，可y ( g ) f 2 ) 入( g ) 尼当且仅当r l g ( x ，y ) 对任意的z ，y y ( g ) i 使得圪( g ) = 8 ( g ) 的图g 称为最大点连通图；使得入( g ) = 6 ( g ) 的图g 称 为最大边连通图文献中已经发现了许多充分条件能确保这个图是最大点连通的 或者最大边连通的例如，对于点可迁图和边可迁图的连通度有下述著名结果 定理1 6 f 耽搬，z s ，刚j 设g 是连通图则 似) 入( g ) = 6 ( g ) 如果g 是点可迁的； f 纠k ( g ) = 6 ( c ) 如果g 是边可迁的 _ 2 0 0 8 年，h e l l w i g 和v o l k m a n n l 3 2 1 对目前己知的能确保图是最大点连通的或 者最大边连通的充分条件做了一个综述 连通度的网络意义是很明显的若图的连通度为尼，则表明对应的互连网络 可以容许_ i c 一1 个结点同时发生故障而不会导致剩余子网络中各结点之间的通 信失败同样的，若图的边连通度为k ，则表明对应的互连网络可以容许k 一1 条 r 第一章图论的概念和网络背景 信息传输信道同时发生故障而不会导致剩余子网络中各结点之间的通信失败因 此，连通度常被视为互连网络可靠性和容错性的重要度量连通度越大，网络的容 错性越好 连通度不仅是度量网络性能的重要参数之一，也是互连网络拓扑结构分析的 基础许多更精确度量网络性能的概念都是建立在连通度概念的基础上所以连 通度是图论中最基本又是应用最广泛的概念，引起众多学者的广泛深入研究，并 获得许多很好的结果8 0 年代以前的研究主要是着重图论本身，m a d e r 给出了有 关这一方面早期研究结果的综述洲8 0 年代以后的研究结果可参见h e l l w i g 和 v o l k m a n n 的综述文章【3 2 1 m e n g e r 定理和连通度概念在计算机和信息科学中得到 了广泛应用，特别是在网络拓扑结构方面，有关这方面的研究结果、进展和应用 可参见徐俊明的组合网络理论一书【6 3 1 1 4 网络的超连通度和限制连通度 从上一节的分析，我们知道了在计算机互连网络拓扑结构的设计和分析中， 连通度是度量网络容错性的重要参数但从组合网络理论一书 6 3 】，我们知道： 用连通度和边连通度来度量网络的容错性有三个缺陷首先，两个图的连通度( 或 边连通度) 即使相同，它们的可靠性也不一定一样，因为它们的最小点割数( 或最 小边割数) 可能不同其次，这两个参数不能区别按不同方式移去圪个点( 或a 条 边) 后所产生的不同的连通分支的情况这说明连通度和边连通度不能反映由于 处理机或通讯信道损坏造成的系统损坏程度因而这两个参数在某些应用上不够 精确第三，在分析和应用这两个参数时我们都不言而喻的假定了系统的任何部 分都可能同时失灵，也就是说对这些参数没有加任何限制然而，在带有某种类型 故障可诊断算法的计算机互连网络中，人们可以安全地假定网络组件的某些子集 是不会同时失灵的，或者对这些参数加上某些限制对于这样的网络，经典的连通 度就不能精确的度量其可靠性了 事实上，我们在确定图g 的连通度或边连通度时，只是考虑使得g s 不连 通的点割或边割s 的最小数，忽略了相应的集合s 同时发生故障的可能性换句 话说，在连通度和边连通度的定义中，对g s 的分支和分离集s 没有加任何条 件或限制所以，为了弥补以上缺陷，人们很自然的想到对g s 的分支和分离集 s 加上一些条件或限制，从而推广了经典连通度的概念 假设图g = ( v e ) 的每个点发生故障的可能性均为m ( 0 p v 1 ) ，且 各点能否正常工作是相互独立的；每条边发生故障的可能性也相同