故障互连网络在一定条件下的容错泛圈性及推广性质研究

In designing and choosing interconnection networks, one important reference factor is cycle embedding. The interconnection networks' fault-tolerant pancyclicity and generalized properties have been a hot research topic. Early research has shown that the interconnection networks such as hypercubes, folded hypercubes, balanced hypercubes and augmented cubes are fault-tolerant pancyclic (or fault-tolerant bipancyclic) under the conditional fault model. However it is not sure whether they are still fault-tolerant edge pancyclic (or bipancyclic) or fault-tolerant vertex pancyclic (or bipancyclic ) when the number of faulty elements is larger. In order to enlarge the number of fault-tolerant elements of interconnection networks, we propose 3-good edges model in this project, i.e., each vertex is incident to at least three fault-free edges. This project will combine related knowledge of Graph theory, Combined network theory, Combinatorial mathematics, and Group theory to investigate the above interconnection netwoks. We will use network dimension division technology to make the netwoks with lower dimensions still being under the conditional fault model and 3-good edges model. Comprehensively use of the interconnection networks' recursive property and mathematical induction to prove their fault-tolerant pancyclicity and generalized properties. The project's research will make important theoretical sense to interconnection networks' cycle embedding and fault-tolerance, as well as practical value to interconnection networks' potential application value.

在设计和选择互连网络时，圈嵌入是一个非常重要的参考因素。互连网络的容错泛圈性及推广性质已经成为研究热点。前期研究表明超立方体、折叠超立方体、平衡超立方体和增广立方体等互连网络在条件错误模型下具有容错泛圈性（或容错偶泛圈性）等性质，但是他们的容错边（偶）泛圈性或容错点（偶）泛圈性或在错误元素增大时是否仍然具有这些性质尚未知。为增大互连网络的容错元素数目，本项目提出3-好邻边模型，即网络中的每个点都至少与三条无错误边相连。本课题将结合图论、组合网络理论、组合学及群论等相关知识研究以上各个互连网络，利用互连网络维数划分技术使得网络在降低维数下仍然满足条件错误模型和3-好邻边模型的要求，综合运用互连网络的递归性质及数学归纳法证明它们的容错泛圈性及推广性质。本项目的研究对互连网络的圈嵌入及容错性具有重要的理论意义，对互连网络的潜在应用具有实际价值。

在并行和分布式计算机系统中，处理器的连接是依赖于给定的互连网络。互连网络通常用一个图来表示，其中点表示处理器，边表示处理器之间的物理连线。在实际应用中，处理器或它们之间的物理连线可能会出现故障，因此考虑含有错误点或错误边的互连网络是非常有意义的。本项目在研究互连网络的泛圈性及推广性质的基础上主要研究了超立方体、交叉立方体、折叠超立方体以及平衡超立方体等互连网络的容错性质，具体包括正则图里的g-好邻点条件诊断与g-好邻点连通度之间的关系、含有错误边集的折叠超立方体中经过指定边集的无错误哈密顿圈性质、平衡超立方体中经过指定边集的哈密顿路和哈密顿圈性质、交叉立方体和平衡超立方体的结构连通度和子结构连通度、以及含有错误点和错误边的超立方体中的连接两个相邻点的点不相交的路性质。本项目的研究结果对互连网络的潜在应用具有一定的理论意义。