交换立访体网络的相关性质分析

《交换立访体网络的相关性质分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、o)EveryedgeofEH(s，t)(2≤s≤t)liesonalleven／-cyclewhere8≤l≤2I褂1；(Ⅱ)ForanysubsetFofE(EH(s，t))(2≤s≤t)withIFI≤s一1，EH(s，t)一Fremainshamiltonian．KEYWORDS：Intc咖。cti∞networks；Exchangedhypercube；Cycle；Edgefaulttolerancem目录摘要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯IABSTRACT．．．．．．．．．

2、．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．1[I目录⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．：⋯⋯⋯IVl绪论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．11．1图的基本概念⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．21．2图的嵌入理论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．513超立方体网络及其变型网络的若干已有结果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯92交换立方体的泛圈性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．132．1交换立方体

3、网络的定义及其性质⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．132．2交换立方体中圈的嵌入⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．153交换立方体的边容错Hamilton性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯223．1存在故障边的交换立方体中Hamilton圈的嵌入⋯⋯⋯⋯⋯⋯⋯⋯⋯．224结束语⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯324．1本文的主要结果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯324．2有待研究的问题⋯_⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯32参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．3

4、4在学期间的研究成果及发表的论文⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．37致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．38学位论文独创性声明及授权声明⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯39学位论文诚信承诺书⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．40IV1绪论超大规模集成(VLSD电路技术的出现和现代通讯技术的高速发展已给计算机理论、技术和应用都带来了深刻的革命，它使人们能够建造出更复杂而又更经济快捷的高性能计算机．出于诸多方面的考虑，新一代的超级计算机系统可以通过增加处理器的数量，而不是单单靠利

5、用更快的处理器来提高运算速度．由成千上万个相互独立的处理器组成的系统称为超级处理器系统，它具有运行并行算法的能力用来解决超大规模的实际问题．系统中元件之间的连接模式称为该系统的互连网络．显然，互连网络可以用图来表示，其中图的顶点表示系统中的元件，图的边表示元件之间的物理连线，关联函数指定了元件之间的连接方式，这样的图称为互连网络的拓扑结构．建造高速快捷的超级计算机系统最困难的技术问题是如何连接这些数目庞大的处理器，选择一个高性能低成本的互连网络拓扑结构就成为了一个迫切需要解决的问题．设计互连网络的拓扑结

6、构时会有许多相互矛盾的要求，要设计一个从各个方面考虑都是最优的互连网络几乎是不太可能的，于是我们就需要在这些要求中寻找一些平衡．首先，要根据要求和功能来设计一个合适的网络；其次，在设计和评估一个网络时最核心的问题是别的网络是否能够嵌入到该网络，即是一个网络是否能被另一个网络来模拟．网络模拟的问题可以归结为图的嵌入问题．在并行处理系统中，假设某个处理过程能分解成若干个并行处理的过程，并且这些子过程之间保持通信．这样的组件处理器的计算就可以归结为图的嵌入问题．大规模集成电路板的设计者根据要求需要把电子元件安

7、置在印刷电路板上。一个基本要求是避免线路交叉，否则会导致短路．因此，希望找到一个方法来解决网络线路的交叉问题，这些线路的布置问题也可以归结为图的嵌入问题．网络故障是不可避免的，尤其是超大规模计算机互连网络和计算机系统，因11绪论此为一个系统设计者或者选择互连网络拓扑结构，一个基本的考虑是它容错性，我们讨论得“容错性”是指：尽管故障出现只要网络中任何两个非故障元件之间存在非故障路线，那么就认为该系统具有功能．即网络的拓扑结构仍保持连通．容错系统的性能应该包含两方面：计算上的有效性和计算上的可靠性．当用图来

8、表示网络的拓扑结构时，网络的可靠性常用图的连通度和边连通度来度量．图的连通度越高，网络的可靠性越大．本文主要讨论网络的拓扑结构—交换立方体的圈的嵌入问题和交换立方体产生坏边时Hamilton圈的嵌入问题．1．1图的基本概念在这一节中，我们将简单介绍一下本学位论文中要用到的图的一些基本概念以及一些常用的符号．如果需要详细的了解，读者可以参阅文献[x1．图G是指有序的三元组(y(G)，E(G)，妒)，其中v(a)非空称为G的顶点集，V(G)中的