推广立方连通圈网络的Hamilton分解的算法

The Algorithms for the Hamiltonian Decomposition of the General Cube-Connected Cycles Network

摘要: 立方连通圈网络是超立方体的有界度变形，它具有超立方体几乎所有的优良性质，而且克服了超立方体顶点度随网络规模增大而增大的缺点，是代替超立方体的一个具有强大竞争力的网络结构。但立方连通圈网络的结构是简单还是复杂呢？这是一个悬而未决的问题。带弦环网络是一类经典的互连网络，该网络具有结构简单等优点。在这篇文章中利用师海忠提出的正则图连通圈网络模型设计出了包含立方连通圈网络的一类网络——推广立方连通圈网络GCCC(n) (n > 2)，证明了GCCC(n) (n > 2)可分解为边不交的一个Hamilton圈和一个完美对集的并，即GCCC(n) (n > 2)是带弦环网络。并给出推广立方连通圈网络分解为边不交的一个Hamilton圈和一个完美对集的并的算法。

Abstract: The cube-connected cycles network is a hypercube of bounded-degree derivative. It has almost all of the excellent properties of hypercube. It also overcomes the shortcoming of hypercube vertices of degrees which will increase with the augment of the network size. But the cube-connected cycles network is simple or complex? This is an open question. Chordal ring network is a kind of classical interconnection network, which has the advantages of simple structure and so on. In this article, a model of the regular graph connected cycle network which is proposed by Haizhong Shi is used to design a kind of network which contains the cube-connected cycles network—the generalized cube-connected network GCCC(n) (n > 2). The authors prove that GCCC(n) (n > 2) can be decomposed into union of edge-disjoint a Hamiltonian cycle and a perfect matching, namely, GCCC(n) (n > 2) is a chordal ring network. They also make a algorithm for GCCC(n) (n > 2) can be decomposed into union of edge-disjoint a Hamiltonian cycle and a perfect matching.