几类网络的容错哈密尔顿性

发布时间：2020-06-11 21:36

【摘要】：通常,我们将多处理器系统看作网络,其中多处理器系统的处理器对应网络的顶点,处理器之间的连线对应网络的边.大规模多处理器系统在运行过程中,处理器或连线出现故障无法避免,这就要求系统具有容错性.多处理器系统的容错性可以对应到网络的容错性.在设计网络时,哈密尔顿性是最基本的要求之一.这就促使这篇文章重点考虑网络的边容错哈密尔顿性,即在有故障边的网络中是否存在无故障的哈密尔顿圈.因为网络存在无故障的哈密尔顿圈的前提是每个顶点至少关联两条无故障边,所以考虑网络的条件边容错哈密尔顿性是有意义的.本文结合数学归纳和对故障边的随机分布进行分类讨论的方法分别研究了复合网络DVCube的哈密尔顿性和复合网络DHcube的边容错哈密尔顿性,并讨论了k-维n-元数据中心网络Dk,u的条件边容错哈密尔顿性.论文结构如下:第一章是绪论,主要介绍了本文用到的图论基本概念、图的(条件)边容错哈密尔顿性的背景知识、两类网络的定义及本文研究的主要工作.第二章给出了复合网络DVcube的相关性质,证明了DVcube V(m,d,n)中每个网络都是哈密尔顿的.由这一结果直接推出了 Hung在[Theoret.Comput.Sci.498(2013)28-45]中给出的几个结论.同时也研究了复合网络DHcubeDH(m,d,n)的边容错哈密尔顿性.证明了当n ≥ 2时,复合网络DH(m,d,n)中每个网络都是(n-1)-边容错哈密尔顿的.第三章基于数据中心网络Dk,n的相关性质,分析了Dk n的条件边容错哈密尔顿性.证明了当k≥0且n≥2时,数据中心网络Dk,n是条件(2n + 2k-9)-边容错哈密尔顿的,其中k=1且n≥6的情况除外,这一结果在故障边的数量上改进了已有的Dk,n的(n +-3)-边容错哈密尔顿的结果.第四章中对本文进行了总结,并给出了进一步的研究方向。
【图文】：

同构图,边集,连接点

圆盘图的点集ＶＸ0（ｍ，ｔ／））邋＝邋ＶＯＵＶＣＯ，边集五⑷（ｍ，ｃ0）＝五（ＣＯＵＥＯＵＣＵ私）．逡逑ｋ＝Ｑ逡逑由定义，Ｚ）（ｍ，ｄ邋＋邋１）邋＝邋Ｄ（ｍ，ｄ）邋Ｕ邋￡心逡逑由定义Ｕ，以／ｎ，邋ｒｆ）是⑷＊２）－正则的．图１．１描述了圆盘图Ｄ（６，２）和Ｄ（６，３）？对逡逑于／邋ｅ邋｛１，２｝，若《Ｗ（Ｃ，），用Ｐｃ，（？，ｖ）表示圈Ｃ，．上按逆时针方向连接点《和ｖ邋＾逡逑路．对于Ｕ邋ｅ邋Ｖ（Ｚ）0ｎ，ｃ0）和两个不同的整数ｅ邋｛０，…，ｄ邋－邋１｝，用0，ｙ）表７Ｋ逡逑连接点ｘ和ｙ的（氏，五；）－交替路，且与Ｉ关联的是尽中的边？例如，在Ｄ（６，２）中，逡逑路户（＾（“１，“４）邋＝邋（Ｍｌ，Ｍ２，《３，《４）？在乃（６，邋３）中，路■Ｐｌ，0（Ｍｉ，邋Ｖ４）邋＝邋（Ｍｌ，邋Ｖ２，》２，邋Ｖ３，，Ｍ３，邋Ｖ４）．逡逑定义１．２给定两个阶为《的图Ｇ逦和（？２邋＝邋（７２，五２）．设点集Ｖｌ邋＝逡逑｛Ｖ１，…，Ｖｎ丨，Ｖ２邋＝邋｛Ｍｌ，…，Ｍ？｝．设Ｔ是集合｛１，．．．到自身的一个一一映射逡逑Ｇ２表示由和Ｔ构造的新图，它的顶点集Ｖ邋＝邋Ｒ邋Ｕ邋Ｖ２，边集￡邋＝五１邋ＵＡＵＥｏ’逡逑其中五０邋＝邋｛（Ｖｉ

复合图,复合图,超立方体,数据中心

络ＤＣｃｍ心ＺＸ：（ｍ，邋Ａｎ）都是复合网络中的具体网络，另外中还包逡逑括圆盘图和类超立方体中其他图形成的很多复合网络，所以是这些具体逡逑网络的推广．图１．３给出了邋Ｚ）０（４，２，２）．逡逑定义１．６设凡是中满足（《邋－邋２）－容错哈密尔顿的和（《邋－邋３）－容错哈密尔顿连逡逑通的图的集合．由圆盘图Ｄ（ｍ，ｄ）和代中的图形成的复合图的集合，称为复合网逡逑络邋ＤＨｃｕｂｅ，记为邋ＤＨ（ｍ，ｄ，ｎ）．由定火，ＤＨｃｕｂｅ邋Ｇ邋ＤＶｃｕｂｅ．逡逑１．３．２数据中心网络的定义逡逑下面给出数据中心网络？邋（简称ＤＣｅ／／）的定义．逡逑定义１．７设ｉｔ，ｎ是整数，其中）＾０且《之２．定义函数逡逑｜邋ｎ逦ｋ邋＝邋０＼逡逑＼逦＋邋１）逦ｋ＞＼．逡逑定义１．８邋（［２０］）设ｔｎ是整数，其中0０且ｎ２邋２．用Ｚ＼？表示有Ａ：－维ｎ－元数据中逡逑心网络，它的阶为４，？．数据中心网络认，？可用如下方法递归地构造：逡逑对于ｙｔ邋＝邋０，令Ｚ＼ｎ三尺对于灸＞邋０，数据中心网络Ｚ＼？由＋邋１个不交逡逑的的拷贝组成，其中第；个拷贝用Ｚ＾＿ｌｎ表示．拷贝Ｚ＾＿ｌｎ中的每个点ｖ由一逡逑、逦个（灸＋邋１）－元组邋0＊
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【参考文献】