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

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

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

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

2. 基本概念 2.1. 推广立方连通圈网络的定义 定义1 [5]：n-立方体nQ 定义如下无向图 (), GV E= {}{}11 :0,1 , 1,2, , nniVx xxxin−=∈= {}{}11111, 1nnnnniiiEx xx y yyxy−−==−=∑ 定义2 [5]：CCC(n)定义如下 顶点集()(){};:,1nVx ixV Qin=∈≤≤，两顶点();x i 和();y i 由一条无向边相连当且仅当，或者 (i) xy=且()1 modijn−≡，或者