互连网络的条件嵌入与容错.doc

互连网络的条件嵌入与容错【摘要】：电子计算机的出现引起了信息科学突飞猛进的发展.信息量的增加和计算量的日益增大,迫切要求计算机存储能力和运算速度的提升.单台计算机的性能提升即将遇到集成电路制作工艺的瓶颈,这加剧了并行计算机系统的诞生.并行计算机系统通常以某种具有优秀性质的互连网络作为拓扑结构,将多个处理机互连,并行处理,以期大幅提升系统的性能.在众多的互连网络中,路和圈以其简单的结构成为最为基础也最为重要的两种网络拓扑.在设计和选择互连网络时,路和圈的可嵌入性是一个非常重要的因素.因此,互连网络中路和圈的嵌入问题成为一个颇具吸引力的研究领域.在实际的系统中,元器件和通信信道故障在所难免,对应在互连网络中,节点(顶点)故障和通信连线(边)故障是不可避免的.这就要求在嵌入路和圈时,这些路和圈不能够通过故障边,即“规避嵌入”.另外,如果某些元器件或通信线路出现故障,那么原网络将遭到一定程度的破坏.在此情形下,人们希望网络的拓扑结构性质得到最大程度的保持.因此,网络的容错能力的度量成为一个重要的课题.另一方面,在某些情形下,人们在选择路由时,希望路由线路通过某些特定的信道,这就使得“指定嵌入”意义非凡.本文共分六章.第一章介绍论文的研究内容和意义、一些基本概念和性质、相关的研究进展及论文获得的主要结果.第二章到第四章研究了k元n立方网络中穿越某些指定子图(线性森林和路)的圈嵌入问题.后两章分别研究了Bubblc-sort网络和Star网络的容错能力.在无故障k元n立方网络中穿越指定线性森林的哈密尔顿圈的嵌入问题上,我们在第二章证明了对于k元n立方网络(n2,k3)中的任意一个边数不超过2n-1的线性森林,这一k元n立方中可以嵌入一个穿越该线性森林的哈密尔顿圈.这推广了Wang等在文献97中的部分结果.在只有故障边的3元n立方网络中穿越指定线性森林的哈密尔顿圈的嵌入问题上,我们在第三章证明了对于3元n立方网络(n2)中的任意一个边数m2n-1的线性森林L,若故障边数不超过n-|m/2|-1,则这一3元n立方中可以嵌入一个穿越L的无故障哈密尔顿圈。这一结论将Chen在文献59中关于故障超立方网络的指定嵌入的结果推广到了3元n立方网络中.泛圈性是比哈密尔顿性更强的网络性质.在k元n立方网络中穿越指定路的泛圈性问题上,我们在第四章证明了对于k元n立方网络(n2为整数,k5为奇数)中的任意一个边数不超过2n-1的路P,在该k元n立方中可以嵌入长从(k-1)(n-1)/2+k到kn且穿越P的圈.网络的容错能力常用在出现一定数目的故障顶点或故障边的情况下,网络的优良拓扑性质的保存程度来度量.在Bubble-sort网络的容错参数的研究方面,我们研究了在n-维的Bubble-sort网络中使得所有的(n-k)-维子Bubble-sort网络都发生故障所需要的最小顶点数FB(n,k)和最小边数fB(n,k).对于一些特殊的k,我们得到了这两个参数的确切值.而在k=2时,我们使用一种巧妙的构造映射的方法,得到了FB(n,2)和fB(n,2)的一个上界；并使用这一思想,得到了fB(n,k)和fB(n,k)的一个上界.连通度在一定程度上也可以度量互连网络的容错能力.在这一方面,由于在迭代的网络发生故障时,网络可能不再连通,在此情形下,我们希望故障互连网络的每个连通分支都有和原网络具有相同拓扑性质的小规模的非故障的子网.基于这种考虑,我们提出了迭代网络的k-嵌入限制连通度的概念,并以Star网络为例研究了嵌入限制连通度和其它一些连通度之间的关系；对于某些k,得到了Star网络的k-嵌入限制连通度的值.【关键词】：互连网络容错线性森林哈密尔顿圈k元n立方bubble-sort网络star网络【学位授予单位】：山西大学【学位级别】：博士【学位授予年份】：2012【分类号】：TP393.0;O157.5【目录】：中文摘要8-10ABSTRACT10-14第一章绪论14-271.1研究内容与意义14-161.1.1研究内容141.1.2研究意义14-161.2基本概念和性质16-221.2.1图论的基本概念和记号16-181.2.2互连网络模型18-221.3连网络的嵌入与容错的研究进展22-251.3.1网络嵌入的研究进展22-241.3.2网络容错参数的研究进展24-251.4本文的主要结果25-27第二章k元n立方网络中的指定嵌入27-512.1准备工作27-282.2奇元n立方网络中的指定嵌入28-402.3偶元n立方网络中的指定嵌入40-492.4本章小结49-51第三章故障3元n立方网络中的指定嵌入51-633.1准备工作51-523.2哈密尔顿圈嵌入52-623.3本章小结62-63第四章k元n立方网络中穿越指定路的圈嵌入63-734.1准备工作63-644.2k元2立方网络的路泛圈性64-664.3k元n立方网络的路泛圈性66-724.4本章小结72-73第五章Bubble-sort网络的条件容错73-845.1准备工作73-755.2Bubble-sort网络的容错性75-825.2.1F_B(n,k)和f_B(n,k)的界75-765.2.2f_B(n,1)的确定76-775.2.3f_B(n,2)的一个上界77-815.2.4f_B(n,k)的一个改进的上界81-825.3本章小结82-84第六章Star网络的嵌人限制连通性度量84-906.1准备工作84-