故障互连网络中含经过指定边的无错误哈密顿圈问题研究

Interconnection network (network for short) is usually represented by a graph where vertices represent processors and edges represent communication links between processors. Study of topological properties of interconnection networks is an essential part for the study of parallel and distributed computing. One major aspect of designing the topological structure of a network is to consider its Hamiltonian properties, since the topological structure containing Hamiltonian path or Hamiltonian cycle can effectively simulate the alogorithms designed on linear array or ring. The study of kinds of Hamiltonian properties of interconnection networks has attracted many scholars’ attention. However, the study of fault-free Hamiltonian cycle passing through prescribed edges on faulty interconnection networks is rare, which is the main research content of this project. We will apply mathematical induction, finding the corresponding fault-free Hamiltonian cycle in every n-1 dimensional sub-networks, and then combining to a desired Hamiltonian cycle in n dimensional networks. We believe that our theoretical research will have an important significance to the Hamiltonian properties of networks and will lay a theoretical foundation for the potential application.

互连网络（简称网络）通常用一个图来表示，其中的点表示处理器，边表示处理器之间的连线。研究互连网络的拓扑性质是研究并行和分布式计算的一个重要部分。设计网络拓扑结构的一个主要方面是考虑哈密顿性质，因为包含哈密顿路或哈密顿圈的拓扑结构可以有效地模拟许多在线性列阵或环上设计的算法。研究互连网络的各种哈密顿性质已经引起了许多学者的关注，然而研究在故障互连网络中含有经过指定边的无错误哈密顿圈问题目前还比较少，这是本项目的主要研究内容。本项目将采用数学归纳法，在n-1维网络中找到对应的无错误的哈密顿圈，再合并成n维网络中预期得到的哈密顿圈。本项目的理论研究在网络的哈密顿性质上具有重要的理论意义，也为网络的潜在应用奠定理论基础。