（应用数学专业论文）某些容错网络的嵌入研究.pdf

摘要 互连网络拓扑结构可以用无向图g 来表示，顶点集和边集v ( c ) 和e ( o ) 分别 表示处理器和处理器之间的通信线路互连网络结构的设计和评价中，一个重要的 课题是结构嵌入问题，归结为图论问题就是图的嵌入线性阵列和环是并行和分布 式计算中最基本结构，大量应用在如图像和信号处理的实际问题中因此研究在网 络结构中有效的嵌入路和圈具有很大重要性，前人在这方面做出了大量的工作由 于网络在使用中会发生故障，对出现故障的网络的研究就很有必要，衡量一个网络 的容错能力就成为了互连网络结构研究的另一个重要课题在所有的互连网络拓 扑结构中，超立方体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 章研究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 网络最长路的嵌入问题，得到以下结果 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 一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 疋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 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 nd 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 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 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 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 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 sd 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 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 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 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 h e3 r dc h a p t e r ，w es t u d yb a s i cp r o p o s i t i o n so fb u b b l e - s o r tn e t w o r k ，w ef i r s t o b t a i nt h es u p e rc o n n e c t i v i 锣a n ds u p e re d g e - c o n n e c t i v i t y 1 f o r 他3 ，( b n ) = 2 n 一4 f o r 佗之5 ，入7 ( b n ) = 2 n 一4 v 中国科学技术大学博士学位论文 t h e nw eo b t a i nt h eb i p a n c o n n e c t i v i t yo fb u b b l e - s o r tn e t w o r k s 2 f o r 佗5 ，e v e r yp a i rn o d e sz ，yi nb n ，t h e r ee x i s t sax y - p a t ho fl e n g t h w i t h d ( x ，耖) + 2 z 佗! 一1 ，2i 一d ( x ，耖) ) i nt h e4 t hc h a p t e r ，w es t u d yt h ee m b e d d i n go fp a t h si n t ob u b b l e - s o r tn e t w o r k s w i t hf a u l t yv e r t i c e s w eo b t a i nt h ef o l l o w i n gm a i nr e s u l t s 1 f o rn 之4 ，f a u l t yv e r t i c e ss e tro fb nw i t h1 日lsn 一3 a n yp a i rd i f f e r e n t c o l o r e dv e r t i c e soa n d 可i n 风一蜀，t h e r ee x i s t sx y - p a t ho fl e n g t h 佗! 一2 a 一1 a c c o r d i n gt ot h ea b o v er e s u l t ，w eo b t a i n ： 2 f o rn 4 ，f a u l t yv e r t i c e ss e tro fb nw i t h1 日l n 一3 h 风一蜀，t h e r e e x i s t sc y c l eo f l e n g t h 佗! 一2 厶 3 f o rn 之4 ，f a u l t yv e r t i c e ss e t 蜀o f 晶w i t hi r lsn - - 3 a n yp a i rs a n l ec o l o r e d v e r t i c e sza n dyi n 玩一日，t h e r ee x i s t sx y - p a t ho fl e n g t h 佗! 一2 a 一2 i nt h e5 t hc h a p t e r ，w es t u d yt h ee m b e d d i n go fb u b b l e - s o r tn e t w o r k sa n d h y p e r c u b e s w i t hf a u l t ye d g e s w eo b t a i nt h ef o l l o w i n gm a i nr e s u l t s 1 f o rn 5 ，f a u l t ye d g e ss e t 尻o f b nw i t hi 最i n 一3 e v e r ye d g eo f b n 一足， l i e so ne v e nc y c l eo fl e n g t he ，6 ls 州 2 f o rn 4 ，f a u l t ye d g e ss e te o f 玩w i t hi 尻i 2 n 一7a n de v e r yv e r t e xo f 风一足i n c i d e n tw i t ha tl e a s t2n o n f a u l t ye d g e s ，t h e r ee x i s t sh a m i l t o nc y c l e 3 f o rn 4 ，f a u l t ye d g e ss e t 最o fb nw i t hl 足l 2 n 一7a n de v e r yv e r t e xo f b ，i f ei n c i d e n tw i t ha tl e a s t2n o n - f a u l t ye d g e s ，t h e r ee x i s t se v e nc y c l eo fl e n g t hz ， 6 扎! 4 f o rn 4 ，f a u l t ye d g e ss e te o f q nw i t hi r ej n 一1a n dn o ta l lf a u l t ye d g e s i n c i d e n tw i t h1v e r t e x ，e v e r yp a i rn o d e su ，钐i nq l 一足，t h e r ee x i s t sau v - p a t ho fl e n g t h zw i t hd ( x ，可) + 4s 粤2 n l ，2 i 一d ( x ，可) ) i nt h e6 t hc h a p t e r ，w ec o n c l u d eo u rr e s u l t sa n dg i v es o m ec o n j e c t u r e sa n dp r o b l e m s t ob es t u d i e df u r t h e r i nt h ea p p e n d i x ，w eg i v et h ed a t au s e di no u rp r o o f 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志 对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位 论文。 保密的学位论文在解密后也遵守此规定。 名罐作者签名：丝竺 第一章绪论 1 1图论的历史 图论见诸文字的历史开始于1 7 3 6 年，俄国数学家伟大的e u l e r 为解决困惑k s - n i g s b e r g 城居民的“七桥问题”，对于岛屿和桥进行了数学上的抽象，把解决的问题 发表为论文f 1 1 这被认为是数学历史上的第一篇图论论文，它标志着数学两个分 支：图论和拓扑学的萌芽 直到1 9 世纪中叶，图论问题主要是迷宫问题、博弈问题、棋盘走马等一些游 戏问题1 8 5 4 年，德国物理学家k i r c h b o f f 为了解决电路问题而创建“树”理论他把 电网络的元件数学抽象化，然后对方程组进行求解 1 8 5 6 年，英国大数学家h a m i l t o n 在来往信函中提出了一个称为“环游世界”的 问题这一类后来以他的名字命名的引申问题至今尚未完全解决对它们的研究 发展出了复杂性理论 1 8 7 2 年，多产的c a y l e y ( 数学史上第三多产的数学家，仅次于欧拉和柯西) 正式 向伦敦数学会提出了“四色猜想”难题在经历了1 8 7 8 年至1 8 8 0 年k e m p e 和t a y l o r 二人先后错误的宣称成功证明后，人们才意识到这是一个可以媲美“费马猜想”的 重大难题 经过了百年的苦苦探索和失败，终于在1 9 7 6 年，由美国数学家a p p e l ，h a k e n 和k o c h 根据当年k e m p e 的思路，用电子计算机，经过了1 2 0 0 小时的计算，总共进行 了惊人的1 0 0 亿次判断，给出了对于“四色猜想”的计算机证明二十年后的1 9 9 6 年， 由r o b e r t s o n ，s a n d e r s ，s e y m o u r 和t h o m a s 将最初的1 9 3 6 种情况降低到了6 6 3 种情 况当然，这类计算机证明到现在还不被很多“纯”数学家所接受，他们仍然在努 力想给出一个“纯”数学的证明“四色猜想”的提出是对图论乃至数学历史都有重 大意义的事件，在对这个永远诱人的问题的研究中诞生了种种成果，其中最著名的 有“染色”理论 c a y l e y 还曾经用“树”的理论去解决有机化合物的分子结构的问题，这后来成 了图论在分子化学中应用的鼻祖 历史的指针指向了1 9 3 6 ，匈牙利数学家k b n i g 在这一年出版了图论的第一本 专著，名为t h e o r i ed e re n d l i c h e nu n du n e n d l i c h e ng r a p h e n ( 有限图和无限图的理 论) 2 】一般认为这是图论作为一个独立数学分支的形成标志在这段时期里，由 1 2 中国科学技术大学博士学位论文 波兰数学家k u r a t o w s k i ，美国数学家m e n g e r ，r a m s e y , w h i t n e y 等人，对于图论的一 系列问题作出了大量的研究，奠定了图论的基础理论 进入2 0 世纪4 0 - 6 0 年代，第二次世界大战的爆发，促进了图论相关的重大事件 的发生首先，战争中军事和对于生产管理交通运输方面涌现出来的大量的关于 离散数学模型的问题催生了运筹学；其次，为了进行大规模的弹道计算，伟大的美国 科学家v o nn e u m a n n 领导发明了电子计算机，使大规模实际问题，如电网络、交通 网络、电路设计、数据结构以及社会科学中的复杂问题的分析和解决成为可能这 时的电子计算机还只是极少数如i b m 公司和美国政府等大型机构才能生产消费的 起的奢侈品，于是为了共享集中的系统资源，也导致对高性能计算相关的图论问题 的研究 ， 这一时期，图论在理论上也得到了新的发展：如英国数学家t u t t e 和r a d o 等 以1 9 3 5 年w h i t n e y 提出的概念为基础发展了拟阵理论近代图论之父法国数学家法 国数学家b e r g e 等在1 9 7 0 年提出并发展了超图理论传奇的匈牙利数学家e r d s s 等 人提出并发展了极图理论等等 随着2 0 世纪7 0 年代开始，i n t e l 在1 9 7 0 年开发出了微处理器，使得计算机的功 能更强大，体积更小，进而引导1 9 7 5 年第一台个人微型计算机的出现同时为了更 为有效的共享分散的资源，用网络将不同的计算机连接在一起，从7 0 年代初的美 国的a r p a n e t 到9 0 年代初的瑞士的万维网，互连网应运而生从此世界真正进 入了一个信息爆炸的时代，计算机科学的迅猛发展大大促进了图论的发展，也为图 论开拓了广阔的应用前景 在史学家格鲁赛的不朽名著草原帝国的前言中有这样一段话：“阿提拉与 匈人，成吉思汗与蒙古人，帖木儿与金帐汗国，这些近乎传奇中的名字，对于不是 专门从事历史研究的知识分子来说也不陌生他们所建立的帝国的历史重要性 在于不断地影响着历史的发展草原游牧民族的早期历史仍处于模糊不清的状 态，只有当他们和那些有文字历史的文明接触时，这种模糊不清的状态才稍微明朗 了一些” 有趣的是，对于图论这样一个数学大家族中的新兴学科，我们发现它的历史和 游牧民族的历史有着惊人的相似之处即使没有学过数学的人也都听说过“四色 猜想”、“环游世界”和“售货员问题”，并为之痴迷图论早期的历史也是模糊不清 的，但每当它和相关的科学领域接触时，就会迸发出灿烂的火花从1 7 3 6 年第一个 游牧民出现在远远的地平线上，在短短不到3 0 0 年的时间里，图论的足迹遍布现代 科学的物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社 1 2 计算机科学和互连网络拓扑结构 3 会科学及经济管理等几乎所有学科领域 1 9 9 0 年在美国阿拉斯加( a l a s k a ) 大学举行的国际图论讨论会，主题是：图论向 何处? ( q u ov a d i s ，g r a p ht h e o r y ? ) 会上图论大家b o l l o b a s 在“图论的未来”一文的 结尾时预测：“今后二十或五十年，图论是否会存在? 将变化吗? 如果是，将以何种方 式变化? 我相信图论的未来是灿烂光明的，因为有太多美好的事情为它纷至沓来 图论有一个极大的问题源供给漂亮、自然的问题，它还是与计算机科学非常密切 的一个数学分支我们几乎没有开始发展解决我们的问题的工具，也几乎未利用 我们与计算机科学的这种亲近关系当二者均发生时，我们将真正腾飞”我们期 待着b o u o b a s 先生提到的腾飞，试看2 0 3 6 年图论的疆域将会扩展得何等的广阔 1 2 计算机科学和互连网络拓扑结构 电子计算机在诞生之初主要就是为科学计算服务的到2 0 世纪6 0 年代，随着 技术的成熟，计算机开始走向商业领域，且应用范围越来越广为有别子“通用计算 机”，专门针对科学计算进行优化设计的计算机开始被称为“高性能计算机”( h p c ) 2 0 世纪7 0 年代出现的向量计算机可看作是第一代h p c ，通过在计算机中加入 向量流水部件，大大提高了科学计算中向量运算的速度8 0 年代初期，随着v l s i 技 术和微处理器技术的发展，向量机一统天下的格局逐渐被打破，“性价比”而非单 一性能成为衡量h p c 系统的重要指标9 0 年代初期，大规模并行处理( m p p ) 系统 已开始成为h p c 发展的主流近些年来，随着电脑和互联网全球化普及，网络化 是h p c 最重要的趋势，网格( g i r d ) 已成为高性能计算一个新的研究热点网格将分 布于全世界的计算机、数据、存储设备、用户、软件等组织成一个逻辑整体，各 行业可以在此基础上运行各自的应用网格于是现代高性能计算进行大规模运算 的载体广泛化为互连网络( i n t e r c o n n e c t i o nn e t w o r k ) 它有别于日常意义下的万维 网i n t e r n e t 或元件连接，而是泛指一些运算节点通过有线或无线通讯信道按照一定 的方式相互连接构成的系统包括了计算机内部的处理器存储器其他元件和设备 大到计算机和计算机子网络各个元件之间的连接方式是设计计算机互连网络的 或制造超大规模并行计算机系统的第一步，我们称这种连接方式为网络的拓扑结 构( t o p o l o g i c a ls t r u c t u r e s ) 高性能计算硬件技术的蓬勃发展，给相应配套的软件带来了巨大的压力应 运而生的并行计算，是提高计算机系统计算速度和处理能力的一种有效手段，算法 是求解问题的方法和步骤，而并行算法就是用多台处理机联合协调求解问题的方 4 中国科学技术大学博士学位论文 法和步骤并行算法执行过程是将给定的问题首先分解成若干个尽量相互独立的 子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解 从历史上看，2 0 世纪7 0 年代末和8 0 年代初是并行算法研究的顶峰时期，最著 名的成果是递归问题的向量化随着多向量处理并行计算机( 如c r a yy - m p ，y h - 2 ) 的出现，既要考虑多处理机间的任务级大粒度并行，又要考虑单处理机上向量 级细粒度并行的算法在8 0 年代初期和中期比较流行基于s i m d 并行计算机设计 的并行算法在8 0 年代中期较热门，但因缺少通用性，过分依赖机器，程序设计复 杂，随着8 0 年代后期高性能计算机的发展，很快被淘汰目前，并行算法的设计 以m i m d 类为主流，要求具有可扩展性和可移植性9 0 年代中期后，并行算法研究 渐渐面向实际而内容有所拓宽，不但研究并行算法的设计与分析，同时也兼顾到并 行机体系结构和并行程序设计 近几年来，随着半导体器件工艺水平的提高以及计算技术和通信网络的迅速 发展，双c p u 或4 c p u 的高档机已随处可见，h p c 的普及，也给并行算法的研究带 来新的机遇同时，近几年来由于硬件技术的飞速发展，使得拥有成千上万个c p u 的h p c 相继研制成功，如何充分有效地利用如此巨量的c p u ，成为并行算法研究 面对的一个极富挑战性的问题 于是从硬件和软件的两方面给出了互连网络拓扑结构的设计要求其基本的 出发点是高性能低成本，归结出以下一些有时相互抵触的基本原则： ( 1 ) 小且固定的接口数，每个物理节点连接的端口数越多，构建网络的成本就 越高，同时带来了对支持软件的压力小的接口数可以降低网络的成本和软件的 要求 ( 2 ) 小通信传输延迟( s m a l lc o m m u n i c a t i o nt r a n s m i s s i o nd e l a y ) ，网络中的每一个 加点的信息传送到另外一点的单位时间要尽可能小小的的通信传输延迟可以确 保网络的有效性和降低网路的建设成本 ( 3 ) 简单的路由算法( r o u t i n ga l g o r i t h m ) ，数据传输必然经过预先设计好的路由 选择，第一个简单有效的路由算法是非常必要的 ( 4 ) 均匀性( u n 渤r m i 锣) 和对称性( s y m m e t 珂) ，希望网络中的各个节点的容量和 连线的负载保持平衡，所有组件都以相同方式工作连接 、 ( 5 ) 高容错性( f a u l tt o l e r a n c e ) ，要容许网络中若干部件发生故障时仍可继续有 效的工作 ( 6 ) 可扩性( e x t e n d a b i l i t y ) 和可嵌入性( e m b e d d a b i l i t y ) ，要求所提供的设计方法 1 2 计算机科学和互连网络拓扑结构 5 可以适用从一个小网络扩展成大网络同时保有原有的优秀性质另外对于简单的 网络拓扑机构的软件支持，要求小网络可以嵌入新的大网络中来应用 ( 7 ) 有效的布图( 1 a y o u t ) 算法，v l s i 的不同就是超大规模计算机系统设计要遇 到的实际问题虽然任何一个布图问题都是n p c 的，但是对于具体的互连网络来 说，布图问题的有效算法是可能存在的 早期的互连网络大部分都是一些平凡网络，例如完全图、树、单环网等，然而 所有这些简单拓扑结构无一不存在较大缺陷，无法满足网络设计的基本原则例如， 完全图虽然具有很好的均匀性和对称性，但是由于它的接口数非常巨大，导致了昂 贵的构建成本单环网虽然具有很小而且固定的接口数，但是他的通信传输延迟 十分严重树虽然具有比较简单的路由算法，但是它的容错性比较差人们开始设 计一些比较复杂的网络结构来满足尽可能多的网络设计基本原则其中比较早出 现的超立方体网络( h y p e r c u b i cn e t w o r k ) ，简称超立方体( h y p e r c u b e ，也称为c o s m i c c u b e ，n - c u b e ，b i n a r yn - c u b e ，b o o l e a nn - c u b e ) ，具有简单的递归和高对称性结构、高 容错、很好的可扩性，对于软件方面，由于它具有很好的可嵌入性，因而具有简单 的路由选择算法等支持它是多指令多数据( m i m d ，m u l t i p l ei n s t r u c t i o nm u l t i p l e d a t a ) 体统网络的首选拓扑结构，因而成为了分布式超级并行计算机系统互联网络 中一个最为人熟知同时也是最重要的拓扑结构由于它独特的拓扑结构，是目前 人们研究的最深入的非平凡网络人们已经相继在此结构的基础上研制出了多种 并行计算机处理系统并且投入了使用同时对于在超立方体上运行的并行计算算 法，也有大量的研究专著 本文主要研究b u b b l e - s o r t 网络和超立方体网络的性质第2 章介绍图论的基本 概念、可嵌入性的定义、容错性和超连通度、b u b b l e - s o r t 网络和超立方体网络的 定义和基本性质，然后给出有关b u b b l e - s o r t 网络和超立方体网络路和圈嵌入问题 目前已经取得的一些结果第3 章是b u b b l e - s o r t 网络的连通度和路嵌入问题第4 章 是点容错b u b b l e - s o r t 网络的路嵌入问题第5 章是边容错b u b b l e s o r t 网络和超立方 体的嵌入问题第6 章总结了前三章的结论并且提出了今后继续研究的问题 第二章预备知识 2 1图论术语的介绍 本节简单给出图的基本概念和今后讨论要用到的记号详细的定义和记号请 参见图论教科书徐俊明 3 ，4 ，5 】 所谓匿 ( g r a p h ) 指的是一个三元组( ke ，妒) 其中y 非空集称为图的顶点集( v e r - t e x - s e t ) ，它的元素称为图的顶点( v e r t e x ) e 称为图的边集( e d g e - s e t ) ，它的元素称 为图的边( e d g e ) 妒是e 到y 中元素有序或无序对簇v v 的函数，称为关联函 数，它刻划了边与顶点之间的关联关系一般用v ( g ) 和e ( g ) 来表示图g 的顶点 集和边集一条边e 和两个顶点相关联( i n c i d e n t ) ，即e = ( u ，t ，) ，其中“，口y ；此时 称u 为e 的起点( o r i g i n ) ，移为e 的终点( t e r m i n u s ) ，统称u ，口为e 的端点( e n d v e r t e x ) 给 定一个图g = ( ve ) ，其顶点的个数i y l 和边的条数吲分别称为g 的阶数( o r d e r ) 和 边数( s i z e ) ，记作v 和本文只考虑有限图( 丘n i t eg r a p h ) ，即口和e 都是有限数阶数 为1 边数为0 的图称为平凡图( t r i v i a lg r a p h ) 图2 1 有向图、无向图、平行边和环的例子 如果一条边e = ( u ，移) 的两个项点相同，即u = ，我们称这样的边为环( 1 0 0 p ) 若两条边e l = ( u ，t ，) 和e 2 = ( “，t i ) 具有相同的两个顶点，称为平行边( p a r a l l e le d g e s ) 或多重边( m u l t i - e d g e s ) 我们称无环而且无平行边的图为简单 羽( s i m p l eg r a p h ) 若边e = ( u ，口) 的妒使得v v 是无序对，我们称这种边为无向边，并用u 口这 种形式来表示若对图中每条边都有( u ，t ，) = ( u ，u ) ，那么称这样的图为无向图( u n - d i r e c t e dg r a p h ) ，反之若妒使得v v 是有序对，即( u ， ) 和( 口，t | ) 并非同一条边，那 么称这样的边为有向边，而u 和v 分别称为边( u ， ) 的起点和终点；每条边都有方向 的图称为有向图( d i g r a p h ) 一般用g 来表示无向图用d 来表示有向图 6 2 1 图论术语的介绍 7 本文中，以下如不加以特殊说明，所涉及到的图均为简单有限无向图 若图日满足v ( h ) y ( g ) ，e ( h ) 冬e ( g ) ，则称日为g 的子图( s u b g r 印h ) ；阶数 等于几( g ) 的子图称为g 的支撑子 ( s p a n n i n gs u b g r a p h ) 若s 冬y ( g ) ，则用g 【吲表 示s 的导出子 ( i n d u c e dg r a p h ) ( 也叫生成的子图) ，其顶点集为s s 中两点“，t ，相 邻当且仅当它们在g 中相邻 我们经常通过从原有的图g 中通过删除或添加某些点和边来得到新的图着 点集日满足日v ( g ) ，则g 一日= g v 】是从g 中删除h 的点和所有与这些 点相连的g 中的边的到的的子图相应的若e ，则g 一= ( y ( g ) ，e ) 若h = z 和= e ，我们习惯简写为g z 和g e g 1 和g 2 的并( u n i o n ) ( 记为g 1 jg 2 ) 是指图日，其中v ( h ) = y ( g 1 ) uv ( c 2 ) ， e ( h ) = e ( g 1 ) ue ( g 2 ) 设e 7 中各边端点集为y ( ) 并且有v ( e 7 ) y ( g 1 ) ，则g i + e 7 是子图日，其中v ( h ) = y ( g 1 ) 且e ( 日) = e ( g 1 ) u e 若e 7 = e ) ，则简记g 1 + e ，为g 1 + e g 的支撑子图g e 1 图2 2 图g 和其支撑子图，导出子图，删边，删点 z 3 若图的顶点集可以划分为两个非空子集m 阶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 a t i o n ) 任何两点同属于x ( 或y ) 被称 为同色点，否则称为异色点我们可以通过染色分辨若x 中每个顶点和y 中每个 顶点都有边相连，称为完全2 部分图( c o m p l e t eb i p a r t i t eg r a p h ) ，记为习惯上， 称完全二部分图所，m 为星( s t a r ) 同样可以定义k 部分图匮一：，缸 所有和口相邻的点构成u 的邻集，记为g ( ) 我们称邻点的个数f g c ( v ) l 为 点 的度，记为如( 可) 点度为0 的点被称为孤立点图g 中点度的最大值和最小 值分别称为g 的最大度和最小度，记为a ( g ) 和6 ( g ) 对于无向图g 若每个顶点 的度都相等，即a ( g ) = 6 ( g ) = 南，则称g 是k 正则图任意两顶点间都有边相 连的简单有向图被称为完全图( c o m p l e t eg r a p h ) ，记为。完全的有向图称为竞赛 8 中国科学技术大学博士学位论文 图( t o r n a m e n t ) 设g 1 = ( ，e 1 ) 和g 2 = ( ，易) 是两个无向图g 1 和g 2 的笛卡尔乘积是一个 无向图，称为笛卡尔乘s n ( c a r t e s i a np r o d u c tg r a p h s ) ，记为g 1xg 2 ，其中v ( g 1 g 2 ) = v lx 场；两个不同顶点x l x 2 和y l y 2 在g 1x g 2 中相邻或者x l = y l 且x 2 和y 2 在g 2 中相邻，或者z 2 = 耽且z 1 和y l 在g 1 中相邻g 1 和g 2 称为笛卡尔乘积图g 1 x g 2 的因子图 刀。八 脍憨 n 。 k e 觚一 图2 3 完全图，二部分图，笛卡尔乘积图 如果两个图g 和h 的顶点集v ( g ) 和v ( h ) 存在双射：v ( a ) _ y ( 日) ，使 得x y e ( a ) 当且仅当咖( z ) ( y ) e ( 日) ，则称g 和h 是同构的，并称砂为同构映 射通常认为同构的图是一样的 g 到自身的同构称为自同构( i s o m o r p h i s m ) 图g 上的自同构集记作qo 是一 个合成运算n 和p 的合成q o 简记为q p 于是( q ，o ) 构成v ( a ) 上的一个置换群， 称为g 的自同构群，简记为g 的群，记号a u t ( g ) 若对于g 中的任意两点z 和存在图g 的自同构0 a u t ( g ) ，使得8 ( x ) = y ， 则称z 和y 是点相似的( v e r t e x - s i m i l a r ) 如果图g 中任何两顶点都是相似的，则称g 是点可迂( v e r t e x - t r a n s i t i v e ) 同样对于g 中的任意两边u 和u 存在图g 的自同构 0 a u t ( g ) ，使得o ( u ) = t ，则称u 和t ，是边相似的( e d g e - s i m i l a r ) 如果图g 中任何 两边都是相似的，则称g 是边可迁的( e d g e - t r a n s i t i v e ) 点可迁和边可迁图作为互连 网络的拓扑结构有着高度的对称性 英国数学家c a y l e y 提出一类以群论的代数方法构造的重要图类定：设r 是一 个非平凡有限群，子集scr ，并且s 不含r 的单位元e 定义一个有向图g = c r ( s ) 如下： 2 2 圈和路的嵌入 9 v ( c ) = r ；对于z ，y r ，( z ，y ) r x - l y s 这种图类被命名为c a y l e y 图c a y l e y 图具有高度的对称性，它都是点可迁的 我们称两种情况为相邻的( a d j a c e n t ) ，当两点u ，u 关联于同一条边e = ( u ，口) 或 两条边( u ，t 7 ) ，( v ，w ) 关联于同一个点设x ，y 是图g 中两顶点，连接z 和y 长度为 忌的路( p a t h ) ，是指顶点黾和边e i 交替出现的序列p = x i o ( = z ) 龟，z n 龟2 e i k z 砝(