平衡超立方和类超立方图的容错哈密尔顿圈嵌入研究

The combinatorial network theory is an important research field in graph theory. Studying design and analysis of interconnection network topology not only promotes the development of graph theory, but also provides a powerful tool for the development of multi-processor systems. In this project, we mainly study fault-tolerant Hamiltonian cycle embedding of two kinds of novel interconnection network topologies-the balanced hypercube and hypercube-like graph, as well as algorithms and computational complexities of these problems. The content of this project detailedly contains: discussing relationships between perfect matching and Hamiltonian cycle, studying edge-disjoint Hamiltonian cycle decomposition, seeking requirements of Hamiltonian cycle embedding and bipancyclicity under high order fault assumption, investigating Hamiltonian cycles passing through prescribed edges and k-disjoint path cover problem under different fault assumptions. The research of this project will deeply reveal fault-tolerant embedding property and excellent network performance of the balanced hypercube and hypercube-like graph, providing solid theoretical foundation for them as interconnection networks of the next generation. Meanwhile, this project will also enrich theoretical system of computational complexity of Hamiltonian cycle embedding problem under additional conditions in networks.

组合网络理论是图论的一个重要研究方向。研究网络拓扑结构的设计与分析，不仅能促进图论自身的发展，而且能为多处理器系统的发展提供强有力的工具。本项目主要研究两类新型互连网络拓扑－平衡超立方和类超立方图的容错哈密尔顿圈嵌入以及该类问题的算法和计算复杂性，具体内容包括：讨论完美匹配与哈密尔顿圈的关系；研究边不交的哈密尔顿圈分解；寻求高阶故障情形下哈密尔顿圈嵌入和双泛圈的条件；探讨不同故障情形下遍历给定一组边的哈密尔顿圈嵌入和k-不交路覆盖问题。本研究有望能够深刻揭示平衡超立方和类超立方图的容错嵌入性质及其优越的网络性能，为它们作为下一代互连网络提供坚实的理论依据；同时，还将丰富和发展网络中附加条件下哈密尔顿问题计算复杂性的理论体系。

本项目主要用图论方法研究几类著名互连网络拓扑结构的组合性质和网络特性,为此类网络作为下一代网络模型奠定坚实的理论基础.本项目主要研究了以下五个方面的内容:(1)研究了平衡超立方的哈密尔顿圈分解,故障条件下以及通过给定一组边的哈密尔顿圈的存在性,给出了平衡超立方的两个边不交的哈密尔顿圈并得到了线性时间算法;证明了在至多发生5n-4条故障边且不存在禁止4圈时,平衡超立方一定存在哈密尔顿圈;证明了通过给定至多n条边的线性森林,平衡超立方一定存在哈密尔顿圈.(2)研究了平衡超立方的多对多不交路覆盖,证明了在至多发生2n−3条故障边的情形下,平衡超立方中始终存在配对的2-不交路覆盖,且故障边数的最大值2n−3是最优的;证明了平衡超立方中存在未配对的(2n−2)-不交路覆盖,且不交路的最大条数2n−2是最优的.(3)研究了数据中心网络DCell的对称性,限制边连通度和(条件)匹配排除数,解决了关于DCell点传递性的一个猜想,得到了DCell的高阶限制边连通度,作为限制边连通度的一个应用,得到了DCell的(条件)匹配排除数并刻画了平凡的匹配排除集.(4)研究了平衡超立方的(子)结构连通度以及(子)结构连通度的计算复杂性,得到了平衡超立方在星图和4长圈故障下的(子)结构连通度,证明了结构连通度和子结构连通度都是NP-完全的.(5)研究了匹配排除问题,条件匹配排除问题,反凯库勒问题以及s-限制匹配排除问题的计算复杂性,证明了这些问题均是NP-完全的,得到了类超立方网络的分数(强)匹配排除数,并证明了一个关于折叠立方的猜想(删除折叠立方的任意一个完美匹配后的图均同构于超立方).上述研究内容丰富了组合网络理论和计算复杂性理论的内容,并且解决了两个相关的猜想,推动了组合网络理论的进一步发展.