推广立方连通圈网络的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.

1. 引言

互连网络是超级计算机的重要组成部分，互连网络通常模型化为一个图，图的顶点对应处理机，图的边对应通信全过程。各种已有互连网络参见 [1] - [18] 。立方连通圈网络是由Preparate和Vailemin [19] 首先提出并研究的，它具有超立方体几乎所有的优良性质，而且克服了超立方体大顶点度的缺点。它是三连通三正则图，而且是Hamilton图(详细参见 [20] - [25] )。

推广立方连通圈网络GCCC(n) (n > 2) (见定义3)是含有立方连通圈网络的一簇网络，它是三正则的，有个顶点和条边，这篇文章中提出了推广立方连通圈网络的概念，并证明了推广立方连通圈网络可分解为边不交的Hamilton圈和一个完美对集的并，即GCCC(n) (n > 2)是带弦环网络。并给出了推广立方连通圈网络分解为边不交的Hamilton圈和一个完美对集的并的算法。本文的其它结构为：2基本概念，3推广立方连通圈网络的Hamilton分解的算法，4案例举证，5结束语。

2. 基本概念

2.1. 推广立方连通圈网络的定义

定义1 [5] ：n-立方体定义如下无向图

定义2 [5] ：CCC(n)定义如下

顶点集，两顶点和由一条无向边相连当且仅当，或者

(i)且，或者

(ii)且和恰有第个指标不同。

定义3：用一个圈代替立方体中的每个顶点，且每个圈中顶点恰位于立方体中与该顶点关联的一条边上，得到的新的网络叫做推广立体连通圈网络，记作GCCC(n)。

2.2. 正则图G的Hamilton分解

定义4 [26] ：设是正则图，是的边集．我们称是Hamilton可分解的。如果

要么

(i)且能被划分成个Hamilton圈；

要么

(ii)且能被划分成个Hamilton圈和一个完美对集；

这里表示的顶点度。

2.3. 推广立方连通圈网络的Hamilton分解

定义5 [27] ：设是一个图，的Euler回是指经过每条边恰好一次的回。

定义6 [27] ：一个图若包含Euler回，则称这个图为Euler图。

定理1：有Euler回路。

引理1 [27] ：一个非空连通图是Euler图当且仅当该图的每个顶点度均为偶数。

给定的完美对集

我们有

定理2：是连通的。

证明：当时，此时

是中的圈，故连通。

假设当时，连通，即对有

路，则

当时，

由有路知

对有路；

对有路；

对有路；

对有路。

综上所述

对有路，即连通。

由数学归纳法知连通。

定理3：当为奇数时， ()是Euler图。

定理4 [28] ：2r-正则图连通圈网络是Hamilton可分解的。

定理5：(1) GCCC(2r)是Hamilton可分解的；(2) GCCC(2r)是带弦环网络。

由定理2~5得：

推论1：(1) GCCC(2r + 1)可分解为边不交的一个Hamilton圈和一个完美对集的并，即GCCC(2r + 1)是Hamilton可分解的；(2) GCCC(n) (2r + 1)是带弦环网络。

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

算法：

输入()

If为偶数

Then

{

1) let

2) 运用Fleury算法 [26] 找到的一个Euler回路

3) 对顶点，找到其关联的条边在Euler回路中配成的相邻的对，记为，，且，用标号为的圈代替，其中与 ()关联。中嵌入后得到GCCC(n) ，Euler回路中嵌入后得到GCCC(n)的一个Hamilton圈，其于边构成GCCC(n) 的一个完美对集。转7

}

Else

{

4) let

5) 运用Fleury算法找到的一个Euler回路

6) 对顶点，找到其关联的条边在Euler回路中配成的相邻的对，记为，，且，用标号为的圈代替，其中与 ()关联，与中的边关联。中嵌入后得到GCCC(n)，Euler回路中嵌入及后得到GCCC(n)的一个Hamilton圈，其于边构成GCCC(n)的一个完美对集。转7

}

7) 输出GCCC(n)及它的Hamilton圈和完美对集，结束。

4. 案例举证

4.1. n = 3时的情形

当n = 3时，输入(如图1所示)

由Fleury算法得到的Euler回路为：

输出的GCCC(3)如图2所示

输出的Hamilton圈为：

Figure 1. Q₃

图1. Q₃

Figure 2. GCCC(3)

图2. GCCC(3)

输出的完美对集为：

；；；；；；；；；；；。

此时由和得到的图如图3所示

把上述Hamilton圈记为：

得到相应的完美对集为：

；；；；；；；；；；

；。

得到的图如图4所示，显然图4为带弦环网络。

4.2. n = 4时的情形

当n = 4时，输入(如图5所示)

由Fleury算法得到的Euler回路为：

Figure 3. Figure constituted by the H₂₄ and M₂₄

图3. 由H₂₄和M₂₄构成的图

Figure 4. GCCC(3) corresponding to Chordal ring network

图4. GCCC(3)对应的带弦环网络

Figure 5. Q₄

图5. Q₄

输出的GCCC(4)如图6所示

输出的Hamilton圈为：

输出的完美对集为：

；；；；

；；；；

；；；；

；；；；

；；；；

；；；；

；；；；

；；；。

把上述Hamilton圈记为：

得到的相应的完美对集为：

；；；；；；；；；；；；；；；；；；；；；；；；；；；；；；。

得到的图如图7所示，显然图7为带弦环网络。

Figure 6. GCCC(4)

图6. GCCC(4)

Figure 7. GCCC(4) corresponding to Chordal ring network

图7. GCCC(4)对应的带弦环网络

5. 结束语

推广立方连通圈网络GCCC(n) (n > 2)是包含立方连通圈的一类网络，文章中证明了GCCC(n) (n > 2)可分解为边不交的一个Hamilton圈和一个完美对集的并，即GCCC(n) (n > 2)是带弦环网络。并给出了推广立方连通圈网络分解为边不交的一个Hamilton圈和一个完美对集的并的算法。但对一般的CCC(n) (n > 2)由Fleury算法构造恰当的Euler回路，以便设计构造CCC(n) (n > 2)的Hamilton分解的算法有待进一步的研究。