n维超立方体中边不交的汉密尔顿圈

Edge-disjoint Hamiltonian Cycles in n- dimensional Hypercube

n维超立方体在并行计算领域有着广泛的应用,其特殊的拓扑结构对大规模的多处理器系统的性能具有重要的影响.在选择互连网络时,汉密尔顿性是评估网络性能的一个重要指标.本文研究n维超立方体Q_n中的汉密尔顿圈,采用构造的方法证明了以下结论:当n是2的幂次方时,Q_(2n)中有且仅有n个边不交的汉密尔顿圈.

N-dimensional hypercube is widely used in the field of parallel computer systems.The special topological structure of n-dimensional hypercube has significantly affected the performance of large multiprocessor systems.In the selection of an interconnection network topology,Hamilton is an important index to evaluate the performance of the network.This article will focus on the Hamilton cycle in n-dimensional hypercube.We prove the following result by construction:In 2n-dimensional hypercube where n is power of 2,there exist n edge-disjoint Hamiltonian cycles.