n维超立方体中边不交的汉密尔顿圈
|
摘要
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.
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.
引文
[1] Bondy J A,Murty U S.Graph Theory with Applications [M].London:The Macmillan Press Ltd,1976:134.
[2] 徐俊明.组合网络理论[M].北京:科学出版社,2007:152-155.
[3] 高随祥.图论与网络流理论[M].北京:高等教育出版社,2009:102-105.
[4] 师海忠.正则图联通圈:多种互连网络的统一模型[C].北京:中国运筹学会第十一届学术交流会论文集,2010:202-208.
[5] Bae M.Resource placement,data rearrangement,and Hamiltonian cycles in torus networks[J].PhD thesis,Dept.of Computer Science,Oregon State Univ.,1996,5(2):101-112.
[6] Foregger M F.Hamiltonian decomposition of products of cycles[J].Discrete Math.,1978,24(4):251-260.
[7] Chan M Y,Lee S J.On the existence of Hamiltonian circuits in faulty hypercubes[J].SIAM J.Discrete Math.,1991,4(4):511-527.
[8] Lin H,McKinley P K,Ni L M.Deadlock-free multicast wormhole routing in 2D mesh multicomputers[J].IEEE Transactions on Parallel and Distributed Systems,1994,5(8):793-804.
[9] Lin H,Ni L M.Deadlock-free multicast wormhole routing in multicomputer networks[J].Discrete Math.,2012,8(3):121-126.
[10] 刘有耀,杨晓强,杜慧敏,等.一种基于超立方体的可扩展并行计算互连网络拓扑结构[R].专利号CN101414952A,2009:231-235.
[11] Fan J X .Hamilton-connectivity and cycle-embedding of the M?bius cubes[J].Information Processing Letters,2002,8(2):113-117.
[12] 樊建席,温东.交叉立方体互连网络的Hamilton连通性[J].青岛大学学报,1999,12(2):28-31.
[13] 樊建席.M?bius立方体互连网络上的圈嵌入算法[J].计算机研究与发展,1998,35(11):1033-1036.
[14] Abraham S,Padamanabhan K.The twisted cube topology for multiprocessors[J].Journal of Parallel and Distributed Computing,1991,13(3):104-110.
[15] 徐俊明.图论及其应用[M].合肥:中国科学技术大学出版社.2004:110-121.
[2] 徐俊明.组合网络理论[M].北京:科学出版社,2007:152-155.
[3] 高随祥.图论与网络流理论[M].北京:高等教育出版社,2009:102-105.
[4] 师海忠.正则图联通圈:多种互连网络的统一模型[C].北京:中国运筹学会第十一届学术交流会论文集,2010:202-208.
[5] Bae M.Resource placement,data rearrangement,and Hamiltonian cycles in torus networks[J].PhD thesis,Dept.of Computer Science,Oregon State Univ.,1996,5(2):101-112.
[6] Foregger M F.Hamiltonian decomposition of products of cycles[J].Discrete Math.,1978,24(4):251-260.
[7] Chan M Y,Lee S J.On the existence of Hamiltonian circuits in faulty hypercubes[J].SIAM J.Discrete Math.,1991,4(4):511-527.
[8] Lin H,McKinley P K,Ni L M.Deadlock-free multicast wormhole routing in 2D mesh multicomputers[J].IEEE Transactions on Parallel and Distributed Systems,1994,5(8):793-804.
[9] Lin H,Ni L M.Deadlock-free multicast wormhole routing in multicomputer networks[J].Discrete Math.,2012,8(3):121-126.
[10] 刘有耀,杨晓强,杜慧敏,等.一种基于超立方体的可扩展并行计算互连网络拓扑结构[R].专利号CN101414952A,2009:231-235.
[11] Fan J X .Hamilton-connectivity and cycle-embedding of the M?bius cubes[J].Information Processing Letters,2002,8(2):113-117.
[12] 樊建席,温东.交叉立方体互连网络的Hamilton连通性[J].青岛大学学报,1999,12(2):28-31.
[13] 樊建席.M?bius立方体互连网络上的圈嵌入算法[J].计算机研究与发展,1998,35(11):1033-1036.
[14] Abraham S,Padamanabhan K.The twisted cube topology for multiprocessors[J].Journal of Parallel and Distributed Computing,1991,13(3):104-110.
[15] 徐俊明.图论及其应用[M].合肥:中国科学技术大学出版社.2004:110-121.