（运筹学与控制论专业论文）局部纽立方体网络的相关性质研究.pdf

f i f f i f f f l l f f f f f f i i f f f i f i f f f f f 川f f j i f 舢 18 0 4 3 9 1 局部纽立方体网络的相关性质研究 摘要 在设计和选择一个互连网络的拓扑结构时，容错性是评估网络性能的重要标 准高容错性的互连网络一直是网络设计者所遵循的基本原则之一我们从网络 的拓扑结构上考虑硬件故障对网络容错性的影响，即在网络结点和( 或) 连线可能 发生故障的情况下的数据传输的可靠性在这种意义下，我们所说的网络容错性 是指该网络能容忍多少组件和( 或) 连线同时发生故障，剩余的子网络中仍然含有 某些特殊结构并仍能正常工作因此，考虑网络的容错性具有实际意义 超立方体网络q n 是现今最著名，最通用的，也是最有效的互连网络拓扑结 构之一作为超立方体网络的一个重要变型，局部纽立方体网络l t q n 首先是由 y a n g 等提出的，它有许多与q n 一样的优良性质，即点数相同，边数相同，礼正则， n 连通且都有简单的递归结构而且l t q n 还有一些优于超立方体网络的性质 如，l t q n 的直径几乎是q n 的一半，l t q n 中含任意长为z ( 4 z 2 n ) 的圈因 此，考虑局部纽立方体网络l t q n 的更多性质具有研究价值 本文围绕局部纽立方体网络的容错性问题，主要研究l t q n 的容错直径和宽 直径，以及有故障的l t q n 中路的嵌入问题运用数学归纳法证明了： ( 1 ) 只要网络故障点数和故障边数之和不超过m 一3 ) ，l t q n 3 ) 中任何两 点间都有长度f ( 2 铲1 1 2s2 孔一1 ) 的路； ( 2 ) 局部纽立方体的容错直径和宽直径相等并且 。i _ i ( l t q , , ) = d ( l t q 扣幡怕箸； 关键词：局部纽立方体网络；容错直径；宽直径；路 i 一 卜 r ，一 ， s o m ep r o p e r t i e so fl o c a l l yt w i s t e dc u b e s a b s t r a c t w h e no n e d e s i g na n ds e l e c tat o p o l o g i c 引s t r u c t u r ef o ra ni n t e r c o n n e c t i o nn e t w o r k ， f a u l tt o l e r a n c ei sas i g n i f i c a n tc r i t e r i o nf o re v a l u a t i n gt h ep e r f o r m a n c eo ft h en e t w o r k m a x i m u mf a u l tt o l e r a n c ei s a l w a y so n eo ft h em a j o rp r i n c i p l e sp u r s u e db yn e t w o r k d e s i g n e r s w ec o n s i d e rt h ee f f e c to nr e l i a b i l i t yc a u s e db yh a r d w a r e f a i l u r e sf r o mt h e t o p o l o g i c a ls t r u c t u r eo fn e t w o r k ，t h a ti s ，t h er e l i a b i l i t yo fd a t at r a n s m i s s i o nw h e nt h e r e a r ef a u l t yv e r t i c e sa n d ( o r ) e d g e s u n d e rt h i sc o n c e p t ，t h et e r m s “f a u l tt o l e r a n c e m e a n s w h e nh o wm a n yf a i l u r e se x i s td o e st h er e m a i n e ds u b n e t w o r ks t i l lc o n t a i ns o m e s p e c i a l s t r u c t u r ea n dp e r f o r mc o r r e c t l y s i n c ev e r t e xf a u l t sa n d ( o r ) e d g ef a u l t sm a y h a p p e n w h e nan e t w o r ki su s e d ，i ti sp r a c t i c a l l ym e a n i n g f u lt oc o n s i d e rf a u l t yn e t w o r k s t h e h y p e r c u b ei so n eo ft h em o s tp o p u l a r , v e r s a t i l ea n de 伍c i e n tt 叩o l o g i c a is t r u c t u r e so fi n t e r c o n n e c t i o nn e t w o r ka tp r e s e n t a sa ni m p o r t a n tv a r i a n to fq n ，t h el o c a l l y t w i s t e dc u b el t q n ，f i r s tp r o p o s e db yy a n ge ta l ，h a sm a n y a t t r a c t i v ep r o p e r t i e sa st h o s e o ft h eh y p e r c u b e t h e yh a v et h es a m en u m b e ro fv e r t i c e sa n de d g e s 。n r e g u l a r i t y , 他一 c o n n e c t i v e a n das i m p l er e c u r s i v es t r u c t u r e f u r t h e r m o r e ，l t q nh a ss o m ep r o p e r t i e s s u p e r i o rt oq n f o re x a m p l e ，t h ed i a m e t e ro fl t q ni sa p p r o x i m a t e l yo n eh a l fo ft h e d i a m e t e ro fq n ，a n dl t q nc o n t a i n sc y c l e sw i t ha n y l e n g t hlf o r4 l 2 n t h e r e f o r e ， i ti sw o r t ht or e s e a r c hm o r e p r o p e r t i e so fl t q n t h i sd i s s e r t a t i o nm a i n l ys t u d i e st h ef a u l tt o l e r a n tp r o b l e m so fl t q n ，s a y , f a u l t d i a m e t e r , w i d ed i a m e t e ra n dp a t h si nt h ef a u l t yl t q n t h ec o n c l u s i o n sa r ea sf o l l o w s ( i ) ap a t ho fl e n g t hlc a nb ee m b e d d e db e t w e e n a n yt w od i s t i n c tv e r t i c e si nl t q n f f o ra n y f a u l t ys e tf cv ( l t q n ) ue ( l t q n ) w i t hl f i 佗一3a n da n y i n t e g e rlw i t h 2 n 一1 1 f l v ( l t q n f ) i 一1f o ra n yi n t e g e rn 3 ； i i ( ) t h ef a u l td i a m e t e ra n dt h ew i d ed i a m e t e ro fl t q na r ct h es a m e ，w h i c hi s 咖删圳诹，= 蝇喇n - - - - 4 5 ； k e y w o r d s ：l o c a l l y t w i s t e dc u b e s ；f a u l td i a m e t e r ；w i d ed i a m e t e r ；p a t h i i i 目录 摘要i a b s t r a c t j 】 目录i v 1 绪论 1 1 1 基本概念1 1 2 网络容错性的研究概况3 2 局部纽立方体网络的基本概念和研究概况6 2 1 局部纽立方体网络的基本概念6 2 2 局部纽立方体网络的研究概况8 2 3 本文主要结果9 3 局部纽立方体网络l t q ，。中路的嵌入1 0 3 1 三个引理1 0 3 2 故障l t q ，。中路的嵌入1 6 4 l t q n 的容错直径和宽直径_ 2 0 4 1 l t q , n 中最短路的一些性质2 0 4 2 l t q n 的容错直径和宽直径2 2 攻读学位期间取得的研究成果4 3 致谢4 4 浙江师范大学学位论文独创性声明4 5 学位论文使用授权声明4 5 学位论文诚信承诺书4 6 i v 一 1 1 基本概念 1 绪论 本节定义一些图论的基本术语与符号把一个有序的二元组( y ( g ) ，e ( g ) ) 称为一个图g ，其中v ( a ) 是g 的顶点集合，v ( a ) 中的元素叫做图g 的顶点或 者点；e ( g ) v ( a ) v ( a ) 称为g 的边集，e ( g ) 中的元素叫做图g 的边通常 地，用y 和e 分别表示一个图g 的项点集合和边集合，用i g l 和i i g 0 分别表示 g 的顶点数和边数。对于图g 的顶点u 和 ，若e = ( u ，u ) e ，则称1 1 和u 在g 中相邻，或u 和u 互为邻点这时又称t 和u 是边e 的两个端点一条边的两个端 点也可能是相同的，这样的边称为环没有重边和环的图叫做简单图本文仅考虑 顶点数有限的简单图 图g 中连接顶点u 和u 且长度为k 的链，记为伽链，定义为一个点边交替 序列 w = ( t = 1 1 0 e l v l e 2 e 七= 1 1 ) ， 其中e i = 忱一1 忱e ( g ) ，1 i k 若链上的边e l ，e 2 ，e 七互不相同，则称 彬为伽迹又若链上的点v o ，u 1 ，讥互不相同，则称为u u 路，用p 或 p ( u ，t ，) 或p = ( t ，p ( u ，s ) ，s ，p ( t ，1 1 ) ，u ) 表示，其中p ( 1 1 ，s ) 和p ( t ，u ) 分别表示 p ( u ，移) 中u 到s 的子路和t 到u 的子路两端点相同且长度至少为3 的路称为圈 路( 圈) 上的边数为路( 圈) 的长度把图g 中长度为尼的圈叫做k 一圈k 为偶( 奇) 数 时，k 圈称为偶( 奇) 圈包含g 中每个项点的圈称为h a m i l t o n 圈若图g 包含 h a m i l t o n 圈，则称g 为h a m i l t o n 图包含g 中每个顶点的路称为h a m i l t o n 路若 图g 中任意两个不同顶点间都有一条h a m i l t o n 路，则称g 为h a m i l t o n 连通的设 t 和u 是图g 的任意两个不同顶点若对任意整数c ( d g ( 1 1 ，移) z 冬i y ( g ) l 一1 ) ， g 中都有长为z 的u t ，路。则称图g 是泛连通的 用f 表示图g 的任意故障集，记为fcv ( a ) ue ( g ) 对图g 的任意故障 点( 或边) 集f ，若当i f i k 时，图g f 仍是h a m i l t o n 的，则称图g 是七容错 h a m i l t o n 的对任何一点都至少与两条非故障边相连及故障边集fce ( g ) ，若 当i f l 2 n 一5 时，图g f 仍是h a m i l t o n 的，则称图g 是七限制容错h a m i l t o n 的类似地，可有七容错h a m i l t o n 连通，七限制容错h a m i l t o n 连通 1 绪论 在g 中连接两顶点u 和u 的所有路中，长度最短的路，称为最短u v 一路，又称 为g 中从u 到t ? 的距离，记为d c ( u ，”) g 中任何两顶点之间的最大距离称为g 的直径，记为d ( g ) ，即， d ( g ) = m a x d c ( 札，v ) l u ， y ( g ) ) 若对于图g 中的任意两个顶点u 和u ，g 中都存在一条u u 一路，则称g 为连 通图，否则称为非连通图不含圈的连通图称为树如果存在非空子集scy ( g ) ， 使得g s 非连通，那么s 称为g 的点分离集g 的所有点分离集中最小点数称 为g 的连通度，记为k ( g ) ，则 k ( g ) = m i n t c c ( u ，u ) i u ，u y ( g ) ，( 仳， ) e ) 含k ( g ) 个顶点的点分离集称为k 分离集若存在整数k ，使得k ( g ) k ，则称g 为k 连通的 设g 是k 连通图，对于任何故障点集fcy ( g ) 若l f i k ，则g 的( k 一1 ) 容错直径，记为d j f 一。( g ) ，定义为 d f l ( g ) = m a x d ( g f ) i fcy ( g ) ，i f ：i 啦一7 3 i i = 1 i = 0 由定义，在超立方体q n 中，任意两点u ，t ，间的h a m m i n g 距离( u ， ) 可定 义为其分量不同的个数另一方面，q n 并不是各方面拓扑性质都最好的网络，如 它的直径比较大，于是人们突出了很多超立方体的变型，如交叉立方体c q n 5 1 ， 纽立方体t q n 【6 1 ，折叠立方体f q n 【7 】等这些变型在点数和边数与超立方体相 同的情况下，直径大约是超立方体的一半 由超立方体的特殊结构，2 0 0 3 年，l i 和t s a i 等人【8 】证明得到了 定理1 1 【8 】在超立方体q n 中，任意两不同点u 间都有长为f ( h ( u ，u ) f i y i 一1 ) 的路，其中z h ( u ，u ) 三o ( m o d 2 ) 与此同时，不少学者对其他立方体的泛连通进行了研究如 x u 和m a 等人【9 】证明了 定理1 2 【9 】在莫比斯立方体m q 几和交叉立方体c q n 中，任何两不同点 t t ，u 间 都有长为2 ( d v ( u ，u ) + 2 f i y ( g ) i 一1 ) 的路 m a 和l i u 等人【1 0 】证明了 定理1 3 在增强立方体a q n 中，任何两不同点仳，u 间都有长为f ( d g ( “， ) f l v ( c ) i _ 1 ) 的路 网络故障是不可避免的，特别是超大规模计算机互连网络和计算机系 统但一高性能的网络应有一定的容错性，即当网络中若干结点和( 或) 连线 发生故障时仍能继续有效地运行对故障集fcv ( c ) ue ( c ) 及任意整数 c ( 如( i t ， 1 1 ) + 2 z l v ( c f ) i 一1 ) 当i f i 礼一3 时，g f 中任意两不同点 乱，t ，间都有长为f 的u ? 3 一路，则称图g 是k 容错泛连通的围绕图的容错泛连通， 在确定故障集的基础上减弱结论或是简化故障集得基础上结论不变，目前已产生 一些结果如 m a 和x u 等人在文献【ll 】中证明了 定理1 4 【1 1 】对故障点集fce ( o n ) 及任意整数z ( d q 。( u ，t ，) + 2 z 2 n 一1 ) 当i f l n 一2 时，q n f 中任意两不同点u ， 间都有长为l 的u u 一路 f a n 和l i i l 等人【1 2 】证明了 4 1 绪论 定理1 5f 1 2 l 对故障集fcv ( t q n ) ue ( t q 。) 及任意整数f ( 2 n 一1 z i v ( t q n f ) i 一1 ) 当i f is 礼一3 时，t q n f 中任意两不同点牡，u 间都有长为 l 的u u 路 f a n 和j i a 等人【1 3 】证明了 定理1 61 1 3 j 对故障集fcv ( m q n ) ue ( m q n ) 及任意整数f ( 2 ”1 一l z i v ( m q n f ) i 一1 ) ) 当i f l 7 1 , 一3 时，m q n f 中任意两不同点u ，”间都有长 为l 的u t ，一路 m a 和l i u 等人【1 4 】证明了 定理1 71 1 4 l 对故障集fcv ( c q n ) ue ( c q n ) 及任意整数z ( 2 n _ 1 1 z i v ( c q n f ) i 一1 ) ) 当l f i n 一3 时，c q n f 中任意两不同点u ，口间都有长 为2 的删路 关于图的容错泛连通问题，人们发现路长的上界可达，但相应的下界 如( u ，u ) + 2 不一定可达，因此考虑图的容错直径和宽直径成为关键所在 1 9 8 1 年，a r m s t r o n g 和g r a y 【1 5 】首先证明了 定理1 81 1 5 j 在超立方体网络q n 中，有d ：一l ( q n ) = d n ( q n ) = n + 1 1 9 9 9 年，c h a n g 和w a n g 等人【1 6 】证明了 定理1 91 1 6 1 在超立方体网络t q n 中，有噬一l ( t q n ) = d n ( t q n ) = + 2 2 0 0 0 年，c h a n g 和s u n g 等人【1 7 】证明了 定理1 1 0 i t i 在超立方体网络c q n 中，有d 二一l ( c q n ) = d n ( c q n ) = f 鸶1 + 2 随着容错直径d 一，( g ) 和宽直径仇( g ) 研究的深入，人们发现对一般图类 都有d 一1 ( g ) = 仇( g ) m e n g e r 定理虽然解决了d 一l ( g ) ，d k ( g ) 的存在性，但 对于一般k 连通图g ，给出d f 一，( g ) ，d 七( g ) 的值是困难的这是p 完备f , - j 题 【1 8 】，但人们已经确定了某些具体图类的容错直径和宽直径，如t q n ，c q n 的容 错直径和宽直径分别在文献【1 6 】和文献【1 7 】中得到证明 5 2 局部纽立方体网络的基本概念和研究概况 局部纽立方体网络作为超立方体网络的一种变型，尽大可能的保留了超立方 体网络的递归结构等很好的性质它的两个相邻的顶点至多有两个相继分量不 同一个n 维的局部纽立方体网络的连通度是n ，有较为简单的路由算法，高容错 性和高对称性，简单结构的可嵌入性，简单路由选择算法和易扩充性等许多好的 性质被看作超立方体网络的一种很好的替代者 2 1 局部纽立方体网络的基本概念 2 0 0 4 年，y a n g ，e v a n s 和m e g s o n 首先定义了超立方体的一种新变型一一局部 纽立方体l t q n 1 9 1 ， 定义2 11 1 9 1 扎维局部纽立方体l t q n ( 亿2 ) 的顶点集是定义在2 元集 o ，1 ) 上 的长为竹的字符串，即 v = 1 1 2 1 ：v i o ，1 ) ，i = 1 ，2 ，n 任意两顶点u = u 。1 2 2 u 1 和u = 1 1 n u 2 u l 之间有边相连，当且仅当它们 满足下列两条件之一： ( 1 ) 存在整数3 k n ，使得 ( a ) u k = 该( 砒是班在 0 ，1 ) 中的补) ； ( b ) t k 一1 = 1 1 k 一1 + 牡1 ； ( c ) u 和u 的其余分量都相同 ( 2 ) 存在整数k 1 ，2 ) ，使得u 和t ，只有第k 个分量不同 图2 1 给出了l t q 3 和l t q 4 根据上述定义，局部纽立方体l t q n 是由有 2 n 个点的n 正则图 为给出局部纽立方体的另一种定义，我们引入集合 o ，1 ) n 对于模2 加法运算 构成的线性空间( o ，1 ) n ，+ ) 设集合b e = e i l l i 佗) 中的元素构成空间的一组基，其中， 6 2 局部纽立方体网络的基本概念和研究概况 ( a ) l t q3 的一般画法( b ) u n q 3 的对称式画法 ( c ) l t q 4 图2 1 局部纽立方体l t q 3 和l t q 4 e l = 0 0 0 0 0 1 ，e 2 = 0 0 0 0 1 0 ，e n - 1 = 0 1 0 0 0 0 ，e n = 1 0 0 0 0 0 设集合b e = 局j 1 i n ) 中的元素构成空间的另一组基，其中， e l = e l = 0 0 0 0 0 1 ，易= e 2 = 0 0 0 0 0 0 1 0 ，e 3 = 0 0 0 0 0 1 1 0 ， b 一1 = 0 1 1 0 0 0 ，日= 1 1 0 0 0 0 定义b = b et 3b e 为构成空间的冗余基集合，则称b 中所有的二元字 符串为基字符串因此，对网络中的任何仡维点名，都可以表示为b 中的一些 基字符串的和m ( x ) 定义为由最少基字符串组成的多重集，使得z 等于所有 基字符串的和定义s ( x ) 为m ( x ) 中所有基字符串的和显然，m ( x ) cb 且 s ( x ) = z 记m ( z ) = 厶( z ) t 9m e ( x ) ，其中，耽( z ) = m ( x ) nb e ， 如( z ) = m ( z ) f 3 ( 曰e 一 e l ，易) ) 因此，帆( z ) n 如( z ) = d 类似可得& ( z ) ，( z ) 例：令z = 1 1 0 1 1 0 0 1 0 1 1 1 0 ，贝0m ( z ) =e 2 ，e 3 ，e 6 ，e o ，e 1 2 ， ( z ) =e 2 ，e 6 ) ， ( z ) = 易，局，e 1 2 ，& ( z ) = e 2 + e 6 = 0 0 0 0 0 0 0 1 0 0 0 1 0 7 2 局部纽立方体网络的基本概念和研究概况 定义2 21 1 9 礼维2 纽立方体q n ，2 ( 7 , 2 ) 的顶点集是定义在2 元集 o ，1 ) 上的长为 n 的字符串任意两点u 和u 之间有边相连当且仅当，u = u + 鼠，其中l k 几 局部纽立方体也可以定义为： 定义2 3 【1 9 】n 维局部纽立方体厶t q n 可定义如下： ( 1 ) 在佗一1 维超立方体q n 一1 的所有顶点后面加“o ”得到q n - - 1 0 ； ( 2 ) 在t , 一1 维2 纽立方体q - 1 , 2 的所有顶点后面加“1 ”得到q - 1 , 2 1 ； ( 3 ) 再把q n 1 0 中的点x l x 2 x , ，- l o 和q n - l , 2 1 中的点z l x 2 x n - 1 1 连边即可 由文献 1 9 】知，q 们同构于q n 由定义2 - 3 得，佗维局部纽立方体的另一种 画法( 如图2 2 所示) 0 0 q 一，0 a 八1 弋 - l & vv l 幺一，d i q 哪 ( a ) l r q 的一般画法( b ) l t q 。的对称式画法 图2 2n 维局部纽立方体l t q 。 根据图2 2 知，l t q n 水平对称且垂直对称，且o o q n - 3 0 $ o l q n - 3 0 0 1 0 q n - - 3 0 0 l l q n 一3 0 = q n t o ，o o q n 一3 ，2 1oo l q n 一3 ，2 1ol o q n 一3 ，2 1ol l q n 一3 ，2 = q n 一1 ，2 1 叉寸 l t q n 中任意两点“和u 由上述定义知，u 和u 间的距离也可表示为 im i n l m ( u + u ) l + 2 ，i m e ( u + u ) 1 ) ， u ，u v ( q n 一1 0 ) ； d l t q 。( u ，t ，) = m i n l m ( u + t ，) i + 2 ，i m e ( u + ) i ) ， u ，u v ( q n 一1 ，2 1 ) ； im i n l m ( u + t ，) i ) ，z v ( q n 一1 0 ) ，y v ( q n 1 1 ) 2 2 局部纽立方体网络的研究概况 2 0 0 4 年，y a n g ，e v a n s 和m e g s o n 【1 9 】证明了 8 2 局部纽立方体网络的摹本概念和研究概况 定理2 1 【1 9 】局部纽立方体的直径为 毗叫蠢 接着，他们【2 0 】又证明了 定理2 2 【2 0 】l t q n ( 礼2 ) 含有长为z ( 4 z 2 n ) 的圈 2 0 0 6 年，在文献【2 l 】中m 瘌x u 得出 定理2 3 2 1 】l t q n 3 ) 中任何两点u ，u 间都有长为f ( d l t q 。( 。，y ) + 2 z 2 n 一1 ) 的路 2 0 0 9 年，他们【2 2 】又总结了几种立方体中任意圈长含任何边的问题，证明了 定理2 4 2 2 ll t q n 中任何一条边都含在长为z ( 4 f 2 n ) 的圈中 此外，关于l t q n 的容错性问题，截至目前，已产生以下的一些结果 c h a n g ，m a 和x u 在文献 2 3 】中证明了 定理2 51 2 3 l 对故障集fcv ( l t q n ) ue ( l t q n ) 当i f l n 一2 时，局部纽立方 体l t q n f 中含有长为f ( 4 z i v ( l t q n f ) i ) 的圈 h s i e h 和w u 在文献【2 4 】中证明了 定理2 6 对n 3 及任何一点都至少与两条非故障边相连当故障边数 i f i 2 n 一5 时，l t q n f 是( 2 n 一5 ) 限制容错h a m i l t o n 的 2 3 本文主要结果 本文对局部纽立方体l t q n 的容错性问题做了进一步的研究，将在 第三章证明：当n 3 时，局部纽立方体l t q n 的故障集fcv ( l t q n ) u e ( l t q n ) 若i f i 礼一3 ，则l t q n f 中任何两点间都有长度z ( 2 铲1 1 z i v ( l t q n f ) | _ 1 ) 的路； 第四章证明：局部纽立方体的容错直径和宽直径相等并且 。l - 1 ( l 丁q n ) = 。n ( l 丁q n ) 2 是1 + 3 ，：薹三：5 ： 9 3 局部纽立方体网络l t q n 中路的嵌入 x u 等人【9 】证明了莫比斯立方体网络m q n 和交叉立方体网络c q n 中，任 何两不同点u ，v 间都有长为z ( d g ( u ，u ) + 2 z 2 n 一1 的路2 0 0 6 年，m a 和x u 【2 1 】证明了对局部纽立方体网络l t q n 中路的嵌入，也有 9 】中的结论而网络 中的结点和( 或) 连线发生故障是不可避免的于是在各种各样的故障网络中的路 嵌入被证明文献【1 2 ，1 3 ，1 4 】分别证明了纽立方体网络t q n ，莫比斯立方体网络 和交叉立方体网络中，若故障点数和故障边数之和至多达到7 1 , 一3 ，那么网络g 中任何两不同点间都有长为f ( 2 铲1 1 z i v ( c f ) i 一1 ) 的路本节证明了： 当n 3 时，局部纽立方体网络l t q n 与m q n ，c q n 有类似的性质 3 1 三个引理 为了给出本节的主要结果，我们需要应用下面三个已知结论： 引理3 1 【2 5 j 当礼3 时，局部纽立方体网络l t q n 的故障集为f = rur ，其 中疋表示厶条故障边集，r 表示厶个故障点集 ( 1 ) 当丘+ 礼一2 时，l t q n f 是h a m i l t o n 的 ( 2 ) 当 + n 一3 时，l t q n f 是h a m i l t o n 连通的 引理3 2 【2 1 】当r , 3 时，局部纽立方体网络l t q n 中，任意两点u ，u 间都有长为 z ( d l t q 。( u ，u ) + 2 f 2 n 一1 ) 的路 引理3 3 【2 4 】当n 4 时，局部纽立方体网络l t q n 中，任意不同点u ，u ，x ，y 间有两条内不交的路p ( u ，u ) 和尸( z ，) ，分别连接u ，u 和x ，y ，且v ( p ( u ，u ) ) u v ( p ( x ，y ) ) = v ( l t q n ) 从以上三个已知结论中，我们得到了以下五个有用的引理： 引理3 43 维局部纽立方体网络l t q 3 中，任意两不同点u ，u 间都有长为f ( 3 l 7 ) 的路 证明：设任意两不同点t | ，u v ( l t q 3 ) 由于3 维局部纽立方体网络l t q 3 的直 径为d ( l t q 3 ) = 2 ，则对任意不相邻两点u ，u 有d l t q 。( 让，u ) = 2 又由引理3 2 知，任意两不同点u ，u 间都有长为f ( d l t q 。( u ，u ) + 2 z 7 ) 的路因此，下只需 1o 3 局部纽立方体网络l t q 。中路的嵌入 找到不相邻的点u 和u 间长为3 的路由图2 1 ( b ) 知l t q 3 是点可迁图，则只需证 当，“= 0 0 0 和u 0 0 1 ，1 1 1 ，1 1 0 ，0 1 0 ) 时，在l t q a 中u 和，u 间有长为3 的路，即 ( 0 0 0 ，0 1 0 ，0 1 1 ，0 0 1 ) ；( 0 0 0 ，1 0 0 ，1 0 1 ，1 1 1 ) ；( 0 0 0 ，0 0 1 ，1 1 1 ，1 1 0 ) ；( 0 0 0 ，1 0 0 ，1 1 0 ，o l o ) i 引理3 5 设任意f 4 ，5 ，7 ) 及点刀v ( l t q a ) ，在l t q 3 一z 中至少有3 条2 维边 在长为2 的圈上 证明：由图2 1 ( b ) 知l t q 3 是点可迁图，则我们只需证当z = 0 0 0 时，对任意 l 4 ，5 ，7 ) ，在l t q a z 中至少有3 条2 维边在长为z 的圈上用下划线表示2 维 边，构造圈如下 当z = 4 时： 当z = 5 时： 当z = 7 时： ( 0 0 1 ，0 1 1 ，1 0 1 ，1 1 1 ，0 0 1 ) ( 1 1 0 ，1 0 0 ，1 0 1 ，1 1 1 ，1 1 0 ) ( 0 0 1 ，0 1 1 ，0 1 0 ，1 1 0 ，1 1 1 ，0 0 1 ) ( 1 1 1 ，1 0 1 ，0 1 1 ，0 1 0 ，1 1 0 ，1 1 1 ) ( 1 1 0 ，1 0 0 ，1 0 1 ，0 1 1 ，0 1 0 ，1 1 0 ) ( 0 0 1 ，0 1 1 ，0 1 0 ，11 0 ，1 0 0 ，1 0 1 ，1 1 1 ，0 0 1 ) - 引理3 6 对任意f 6 ，7 ) 及两不同点u ，t ，v ( l t q 3 ) ，l t q 3 中至少有2 条2 维 边在长为f 的u t ，路上 证明：由图2 1 ( b ) 知l t q 3 是点可迁图，则我们只需证当u = 0 0 0 和u o o l ，1 1 1 ，1 1 0 ，o l o 时，在l t q 3 中至少有2 条2 维边在长为z ( f 6 ，7 ) ) 的u 1 ) 一路 上用下划线表示2 维边，构造u v 一路如下 若u = 0 0 1 ，则长为f 的u u 路为： r ( u ，u ) = ( 0 0 0 ，1 0 0 ，1 1 0 ，1 1 1 ，1 0 1 ，0 1 1 ，0 0 1 ) b ( u ，u ) = ( 0 0 0 ，1 0 0 ，1 1 0 ，0 1 0 ，0 1 1 ，1 0 1 ，1 11 ，0 0 1 ) 若u = 1 1 1 ，则长为l 的u 1 ) 路为： r ( u ，u ) = ( 0 0 0 ，1 0 0 ，1 1 0 ，0 1 0 ，0 1 1 ，1 0 1 ，1 1 1 ) 岛( t ，u ) = ( 0 0 0 ，0 1 0 ，1 1 0 ，1 0 0 ，1 0 1 ，0 1 1 ，0 0 1 ，1 1 1 ) 若t ，= 1 1 0 ，则长为2 的u u 路为： 乓( u ，u ) = ( 0 0 0 ，0 0 1 ，1 1 1 ，1 0 1 ，0 1 1 ，0 1 0 ，1 1 0 ) 户：；。( u ，u ) = ( 0 0 0 ，1 0 0 ，1 0 1 ，0 1 1 ，0 0 1 ，1 1 1 ，1 1 0 ) b ( _ u ，u ) = ( 0 0 0 ，0 1 0 ，0 1 1 ，0 0 1 ，1 1 1 ，1 0 1 ，1 0 0 ，1 1 0 ) 1 1 3 局部纽立方体网络l t q 。中路的嵌入 若u = 0 1 0 ，则长为l 的u u 路为： r ( u ，u ) = ( 0 0 0 ，0 0 1 ，! ! ! ! ! 里! ，! 旦q ! ! ! q ，o l o ) p ；( u ，u ) = ( 0 0 0 ，1 0 0 ，1 0 1 ，q ! ! ! 里q ! ，1 1 1 ，1 1 0 ，0 1 0 ) 群( u ， ) = ( 0 0 0 ，0 0 1 ，1 1 1 ，! ! 里! ! q q ，1 0 1 ，0 1 1 ，0 1 0 ) 引理3 7 设4 维局部纽立方体网络l t q 4 的故障集为fcv ( l t q 4 ) ue ( l t q 4 ) 若l f i 1 ，则l t q 4 一f 中任意两不同点间有长为2 ( 7 f i v ( l t q 4 一f ) i 一1 ) 的路 证明：设任意两不同点u ，u l t q 4 一f 记l t q 4 = lor ，其中，l = o l t q 3 ，r = 1 l t q 3 当i f i = 0 时，由引理3 2 知，引理3 7 成立当i f l = 1 时， 分以下三种情形讨论 情形1 f = z ) cv ( l t q 4 ) 不妨设x y ( l ) 分下列三种子情形来构造长为 f ( 7 f 1 4 ) 的路 情形1 1 钆，u v ( l ) 一 z ) 令4 f l 7 ，3 f r 7 ，则f = ( 1 l 一2 ) + 坛+ 2 记可能存在故障边或故障 点的路为隐故障路由引理3 4 知，在l 中存在长为屯的隐故障路兄( u ，u ) 如果 z y ( 户i l ( u ，u ) ) ，设p l = ( u ，p l ( “，y ) ，y ，z ，z ，p l ( z ，u ) ，u ) ；如果x 譬y ( p l ( u ，u ) ) ， 记a 为路兄( ，u ) 上不同于u ，u 的点，则设咒= ( 乱，p l ( 7 2 ，可) ，y ，a ，z ，p lz ， ) ，u ) 用y r ，z 兄分别表示y ，z 在r 中的邻点由引理3 4 知，在兄中存在长为k 的路 玮( 如，细) 因此，在l t q 4 一f 中有长为f 的u v - 路p = ( u ，兄( u ，秒) ，y ，y r ，p r ( y r ， z r ) ，z r ，z ，f z ( z ，u ) ，u ) ( 如图3 1 0 ) 所示) 情形1 2 钍v ( l ) 一 z ) ，u y ( r ) 令3 i 6 ，3 f r 7 ，则f = i + z r + 1 由引理3 1 知，在l f 中存在 长为7 的圈c = ( u ，u 1 ，u 2 ，“6 ，u ) 显然，圈g 上有两条以牡为起点长为i 的 路，即( u ，u l ，u ) 和( u ，一：，u 7 一i ) 对任意的3 i 6 都有u i u 7 - t 任取 仇 u t ，嘶一i ，使得地凡u ，其中，忱五是耽在兄中的邻点不失一般性，设吨= 以 令凡是t i 在r 中的邻点由引理3 4 知，在r 中存在长为f r 的路p r ( 让妇，u ) 因 此，在l t q 4 一f 中有长为f 的u u 一路p = ( u ，t t l ，牡i ，地凡，忍( 地r ，u ) ，u ) ( 如图 3 1 ( b ) 所示) 情形1 3 u ，u y ( r ) 由引理3 4 知，在冗中存在长从3 到7 的u u 路p r ( u ，u ) 因此，下只需证长 从8 到1 4 的u u 一路 1 2 lili叫11 3 局部纽立方体网络l t q 。中路的嵌入 l月 0夕v h h lr 产u a h 1 b 乜 t ， 图3 1 引理3 7 证明中的图示 直线和曲线分别表示两点间的边和路 对于长为f 8 ，9 ) 的u u - 路令坛 6 ，7 ，则z = 坛一1 + 3 由引理 3 6 知，冗中至少有两条2 维边在长为f r 的u t ，路( u ，u ) 上设( y r ，z r ) 和 ( 秒二，磊) 为u u 一路上任意两条2 维边不妨设2 维边( y r ，砌) 在路r 上，满足 鲰和细在l 中的邻点钆和钇都不是z 在l t q 4 一f 中有长为z 的t u 路 尸= ( 缸，斥( u ，y a ) ，y r ，y l ，z l ，z r ，p r ( 砌， ) ，u ) ( 如图3 1 ( c ) 所示) 对于长为z ( 1 0 z 1 4 ) 的u u 路令i n 4 ，5 ，7 ，z r 6 ，7 ，则z = ( z l 一1 ) + ( f r + 1 ) 由引理3 5 知，l z 中至少有3 条2 维边在长为z l 的圈c 上 再由引理3 6 知，兄中至少有两条2 维边在长为k 的u u 路r ( u ，u ) 上因为 l 和r 中都只有4 条2 维边，所以圈c 上存在一条2 维边，记为( y 工，钇) ，与伽路 斥( u ，u ) 上一条2 维边相对应，记为( y r ，砌) ，即如和翔分别是钆和z l 在兄中 的邻点记p l = c 一( y l ，z l ) ，玮= ( u ，p r ( u ，y r ) ，y r ，z r ，r ( 钮，u ) ，u ) 因此，在 l t q 4 一f 中有长为l 的缸u 一路p = ( u ，p r ( u ，y r ) ，y r ，y l ，p l ，z l ，z r ，p r ( z r ，u ) ，u ) ( 如图3 1 ( d ) 所示) 情形2 fce ( l ) 或fce ( r ) 不失一般性，设fc e ( l ) 1 3 3 局部纽立方体网络l t q 。中路的嵌入 设