《某些容错网络的嵌入研究》由会员分享，可在线阅读，更多相关《某些容错网络的嵌入研究（116页珍藏版）》请在金锄头文库上搜索。
1、中国科学技术大学 博士学位论文 某些容错网络的嵌入研究 姓名：经衿 申请学位级别：博士 专业：应用数学 指导教师：徐俊明 20090401 摘要 互连网络拓扑结构可以用无向图G 来表示，顶点集和边集v ( c ) 和E ( O ) 分别 表示处理器和处理器之间的通信线路互连网络结构的设计和评价中，一个重要的 课题是结构嵌入问题，归结为图论问题就是图的嵌入线性阵列和环是并行和分布 式计算中最基本结构，大量应用在如图像和信号处理的实际问题中因此研究在网 络结构中有效的嵌入路和圈具有很大重要性，前人在这方面做出了大量的工作由 于网络在使用中会发生故障，对出现故障的网络的研究就很有必要，衡量一个网络
2、的容错能力就成为了互连网络结构研究的另一个重要课题在所有的互连网络拓 扑结构中，超立方体Q n 是最受关注的近来B u b b l e - s o r t 网络，是一种C a y l e y 图， 由于有着良好的拓扑结构特性，如高对称性和递归性，继超立方体后成为我们关注 的对象 本文主要研究B u b b l e - s o r t 网络和超立方体的( 容错) 路和圈嵌入问题，共分6 章 其中第3 章至第5 章是主要部分 第1 章绪论主要说明研究的背景，理论意义和使用价值 第2 章介绍图和网络的基本概念，嵌入和容错的定义，B u b b l e - s o r t 网络和超立 方体的定义和基本
3、性质，以及一些已有的结果 第3 章研究B u b b l e - s o r t 网络的2 个基本性质 首先，我们得到B u b b l e - s o r t 网络超连通度和超边连通度 1 K 7 ( B n ) = 2 n 一4 ，当死3 时入7 ( B n ) = 2 n 一4 ，当n 5 时 然后我们得到B u b b l e s o r t 网络的二部分泛连通性 2 在鼠中，当佗5 时，任意2 点z ，Y 间存在长度为Z 的路，其中d ( x ，Y ) + 2 Z n ! 一1 ，2I 一d ( x ，y ) ) 第4 章研究点容错的B u b b l e s o r t 网络最长路
4、的嵌入问题，得到以下结果 1 玩中的故障点集R ，I R I n 一3 当T , 4 时，任何异色点X 和Y ，在 1 1 1 中国科学技术大学博士学位论文 幸存图鼠一R 中存在z 和y2 _ 间长度为n ! 一2 f v 一1 的路 并由此得到了点容错B u b b l e - s o r t 网络中最长圈的嵌入： 2 B n 中的故障点集R ，I R I n 一3 当n 4 时，在幸存图风一日中至 少存在长为扎! 一2 I R I 的圈 3 玩中的故障点集R ，I R I n 一3 当n 4 时，任何2 顶点X 和Y 同色， 则在幸存图风一R 中有从X 到Y 的长为n ! 一2 l R l
5、 一2 的路 在第5 章中，我们主要讨论了边容错B u b b l e s o r t 网络和超立方体中的嵌入问 题 1 巩中的故障边集疋满足I 疋I n 一3 ，B n 一疋的每条边都包含在一个 长度从6 到n ! 的偶圈上，当n 5 时 2 玩中故障边集E 满足I 疋l 2 n 一7 ，且任意顶点都至少有2 条边幸存时， 当n 4 时，幸存图J E i n 一疋中存在H a m i l t o n 圈 3 鼠中故障边集E 满足I 疋I 2 n 一7 ，且任意顶点都至少有2 条边幸存时， 当n 4 时，幸存图中有长为Z 的偶圈，其中6 之n ! 4 超立方体Q n 中的故障边集E 满足l 疋
6、I 礼一1 ，且当I R l = n 一1 时所有 故障边不和一个顶点相连当n 4 时，任意顶点u u ，在幸存图中存在一条长为Z 的牡u 路，其中d ( u ，u ) + 4SZ 2 n 一1 且2 1 ( e d ( u ，u ) ) 第6 章对本文的主要工作进行了总结，对有待进一步研究的问题提出了一些看 法和猜想 附录中我们给出了证明中用到的数据 A b s t r a c t A ni n t e r c o n n e c t i o nn e t w o r ki su s u a l l ym o d e l e db ya nu n d i r e c t e dg r a p
7、 hG T h es e t s o fv e r t i c e sa n de d g e so fGa r ed e n o t e db yv ( a ) a n dE ( G ) ，r e s p e c t i v e l yr e p r e s e n t sp r o - c e s s o r sa n d1 i n l 【sb e t w e e np r o c e s s o r s I ni n t e r c o n n e c t i o nn e t w o r k s o n eo ft h ei m p o r t a n t i s s u e si n
8、d e s i g n i n ga n d e v a l u a t i n ga ni n t e r c o n n e c t i o nn e t w o r ki st os t u d yh o ww e l lo t h e r e x i s t i n gn e t w o r k sc a nb ee m b e d d e di n t ot h i sn e t w o r k T h i sp r o b l e mC a nb em o d e l e db y g r a p he m b e d d i n gp r o b l e m L i n e a
9、ra r r a y sa n dr i n g s ( i e c y c l e s ) a r et w of u n d a m e n t a l n e t w o r k sf o rp a r a l l e la n dd i s t r i b u t e dc o m p u t a t i o n M a n ye f f i c i e n ta l g o r i t h m sw e r eo r i g - i n a l l yd e s i g n e db a s e do nl i n e a ra r r a y sa n dr i n g sf o
10、rs o l v i n gav a r i e t yo fg r a p hp r o b l e m s a n ds o m ep a r a l l e la p p l i c a t i o n s ，s u c ha st h o s ei ni m a g ea n ds i g n a lp r o c e s s i n g T h u s ，i ti s i m p o r t a n tt oh a v ea ne f f e c t i v ep a t ha n dc y c l ee m b e d d i n gi nan e t w o r k s T h
11、ep a t ha n d c y c l ee m b e d d i n gp r o p e r t i e so fm a n yi n t e r c o n n e c t i o nn e t w o r k sh a v eb e e ni n v e s t i g a t e d i nt h el i t e r a t u r e S i n c ef a u l t sm a yh a p p e nw h e nan e t w o r ki sp u ti nu s e ，i ti ss i g n i f - i c a n tt oc o n s i d e
12、rf a u l t yn e t w o r k s F a u l t - t o l e r a n c ea b i l i t yi sav e r yi m p o r t a n ti s s u eo f i n t e r c o n n e c t i o nn e t w o r k s A m o n ga l lt h ei n t e r c o n n e c t i o nn e t w o r kt o p o l o g i e sp r o p o s e d i nt h el i t e r a t u r e ，h y p e r c u b e s
13、d e n o t e db y “，i so n eo ft h em o s tp o p u l a rt o p o l o g i e s V e r y r e c e n t l y , b u b b l e - s o r t 口a p h sd e n o t e db yB n ，w h i c hb e l o n gt ot h ec l a s so fC a y l e yg r a p h s ， h a v eb e e na t t r a c t i v ea l t e r n a t i v et oh y p e r c u b e s I th a
14、 ss o m eg o o dt o p o l o g i c a lp r o p e r t i e s s u c ha sh i g h l ys y m m e t r ya n dr e c u r s i v es t r u c t u r e I nt h i sd i s s e r t a t i o n ，w ed i s c u s st h ee m b e d d i n go fp a t h sa n dc y c l e si n t o ( f a u l t y ) B u b b l e - s o r tn e t w o r ka n dh y
15、 p e r c u b e s I tc o n s i s t so f6c h a p t e r s ，i nw h i c ht h e 3 r dc h a p t e r t ot h e 5 t hc h a p t e ra r em a i np a r t s I nt h e1 s tc h a p t e r ，w ei n t r o d u c et h eb a c k g r o u n do fO U rw o r k s I nt h e2 n dc h a p t e r ，w ef i r s ti n t r o d u c et e r m i n
16、 o l o g ya n dn o t a t i o no fg r a p ht h e o r y T h e nw ei n t r o d u c et h ec o n c e p t so fe m b e d d i n ga n df a u l t - t o l e r a n c e F u r t h e r m o r e ，w eg i v e t h ed e f i n i t i o n sa n ds o m ep r o p o s i t i o no fB u b b l e - s o r tn e t w o r k sa n dh y p e r c u b e s F i n a l l y , w el i s ts o m ek n o w nr e s u l t so nt h et o p i c I nt
