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

摘要

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

目录

声明

致谢

摘要

1．1研究背景和意义

1．2基本概念和预备知识

1．3两类网络的定义

1．3．1 复合网络DVcube和DHcube的定义

1．3．2数据中心网络Dk,n的定义

1．4两类网络的研究现状

1．4．1 复合网络DVcube的研究现状

1．4．2 数据中心网络Dk,n的研究现状

1．5本文主要结论

第2章复合网络的哈密尔顿性及边容错哈密尔顿性

2．1 复合网络DVcube的哈密尔顿性

2．2 复合网络DHcube的边容错哈密尔顿性

第3章数据中心网络的条件边容错哈密尔顿性

3．1数据中心网络的性质

3．2低维数据中心网络的条件边容错哈密尔顿性

3．3数据中心网络的条件边容错哈密尔顿性

第4章结论与展望

参考文献

作者简历

学位论文数据集