HCH—立方体的Hamilton连通性

Hamilton- connectivity on HCH- cubes

新型并行计算系统的研制依赖于对新型互连网络结构及其性质的研究。超立方体及其变型——交叉立方体具有优点,也具有缺点。文献[1]给出了在超立方体与交叉立方体的顶点之间的一种连接——超连接,从而得到了一种称为HCH-立方体的互连网络,文章证明了当n≥4,HCH-立方体任意两个顶点之间存在Hamilton路径,即HCH-立方体是Hamilton连通的,而超立方体不是Hamilton连通的。这表明HCH-立方体具备了交叉立方体在Hamilton连通性方面的性质。文章还给出了在n维HCH-立方体中构造任意两个顶点之间Hamilton路径的算法,该算法的时间复杂度为O(N),其中N=2n,为n维HCH-立方体的顶点个数。

The research and production of new parallel computing systems depend on the research of new interconnection network structures and their properties.The hypercube and the crossed cube,as a variant of the hypercube,have both merits and defects.Ill gives a kind of connection-the hyper connection between the nodes of the hypercube and the crossed cube.Thus a interconnection network called a HCH-cube is obtained.This paper proves that HCH-cube is Hamilton-connected.The relative algorithm of the process of finding Hamilton paths is also given.The time complexity of this algorithm is O（N）,N=2^n.