几类凯莱图的若干网络性质和组合性质研究

《几类凯莱图的若干网络性质和组合性质研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号:O157,O158密级：公开研究生学位论文论文题目（中文）几类凯莱图的若干网络性质和组合性质研究论文题目（外文）StudiesonnetworkandcombinatorialpropertiesofsomeclassesofCayleygraphs研究生姓名陈丹学科、专业计算机科学与技术·计算机应用技术研究方向计算机网络体系结构学位级别博士导师姓名、职称周庆国教授论文工作起止年月2015年4月至2018年3月论文提交日期2018年5月论文答辩日期2018年6月学位授予日期2018年6月校址：甘肃省兰州市几类凯莱图的若干网络性质和组合性质研究中文摘

2、要随着信息科学的不断发展，各科研领域数据规模不断增长，对计算速度的需求也与日俱增。并行和分布式系统应运而生，并在近年来得到了广泛发展和研究。并行计算机系统的一个基本特征是将大量元件按照某种互连结构连接起来，使得多个处理器能够互相配合、并行处理，从而提高运算能力。并行计算系统因为规模庞大而不可避免的出现处理器或者通信故障。我们希望当故障发生时，系统做为一个整体能够继续运行而不致崩溃，也就是系统应具有一定的容错能力。容错性是衡量互连网络性能的关键指标之一，它主要考虑在网络发生故障时网络中某些特有性质的保持能力。因此，并行系统中互连网络的容错性研究是一个重要的课

3、题。并行处理计算机系统、分布式计算机系统等由大量功能部件所组成的系统，都会遇到部件或者部件之间连接的问题。系统中元件之间的连接模式称为该系统的互连网络模型。互连网络可以用图来表示，图的顶点表示系统中的元件，图的边表示元件之间的物理连接，而关联函数指定了元件之间的连接方式，这样的图称为互连网络拓扑结构，用于完成计算机系统中的数据传送和变换。本文主要考虑互连网络应具有的如下特点：对称性好（对应图具有高度对称性），以均匀分布信息流量，实现高效路由算法；容错性好，当少数节点或通信连接发生故障时（对应图的顶点或边错误），仍能保持原有互连网络的某些重要结构特性。从拓扑

4、结构上讲，一个系统的互连网络模型从本质上反映了该系统的结构特点。反之，图可以用来准确描述互连网络的拓扑结构。在本文中我们将不区分“图”和“互连网络”，将网络、元件和连线分别看成图、顶点和边。凯莱图因具有较好的对称性和容错性，常用于构造并行式系统的网络原型，在大规模并行处理系统的设计与分析中起着重要的作用。超立方体网络，双环网络，星图等都是凯莱图，并且已经得到一定的研究。但凯莱图中平衡超立方图的相关研究较少，尤其是关于其容错性方面。本文主要研究了凯莱图在容错性和对称性等方面的性质，特别是平衡超立方的容错性质和蜂窝超环面图的转发指标。最后将研究对象扩展到与凯莱

5、图有诸多相似性的半凯莱图、双凯莱图的容错性、可靠性、可嵌入性等性质方面。对上述方向的研究主要取得了以下成果。(1)互连网络设计中稳定性和容错性是重要的考虑因素，所以研究平衡超立方的容错性是比较重要的。平衡超立方是由超立方变换而来的，它的一个重要特性是平衡超立方中存在一条无错哈密尔顿路。图的哈密尔顿路是指一条穿过该图所有顶点的路。任意两个顶点间均有哈密尔顿路的图称为哈密尔顿连通的。本文研究并证I明了平衡超立方是2?−2边容错哈密尔顿可带的。(2)因为互连网络在实际应用中可能会出现错误元素，所以考虑有错误元素的网络具有实际意义。容错圈嵌入（或路嵌入）指的是在有

6、错误元素的互连网络中找到给定长度的无错误圈（或无错误路）。在这种情形下，寻找遍历特定顶点或者边的路和圈就显得很有意义。遍历给定一组边的问题在超立方及其部分超立方的变形中得到了一些研究，但在平衡超立方中仅有边泛双圈的结论。我们将遍历一组边的哈密尔顿路问题扩展到平衡超立方中进行研究，部分地推广了边双泛圈的结论。在本文第三章研究了平衡超立方中遍历给定一条边的哈密尔顿可带性，得到如下结论：对于任意给定的边?，任意不同部的两个顶点之间都存在一条哈密尔顿路遍历?。(3)网络转发指标可用来度量网络的路由效率和容量。蜂窝超环面图作为一种新型的凯莱图被互连网络设计领域广泛研

7、究。其转发指标的计算依赖于图中任意不同两点的距离和，此值恰好是Wiener指标的2倍。对于统一的蜂窝超环面图???(?,2?,2?+?mod(2?))，当?≤?≤2?−?和?≥2?+1时，已经得到了它的Wiener指标的表达式，也即得到了它的转发指标。但对于不满足上述条件的蜂窝超环面图，其Wiener指标和转发指标仍是不确定的。本文第四章给出了适用于大部分情形的蜂窝超环面图转发指标计算方法。(4)凯莱图模型具有很多优良的特性，例如简单、高度对称、易于扩展等，逐渐成为构造与设计互连网络的有力工具。上述特性可以极大的简化拓扑维护和路由算法的设计，许多互连网络拓

8、扑设计都基于群论中的凯莱图模型。因此，第五章详细的讨论了不同凯莱图