基于FQn和圈的细胞分裂生长网络FQCC(n,k)及其性质

折叠立方体连通圈网络FQCC(n) (n > 1)是一类典型的互连网络，它是3正则的。师海忠根据折叠立方体连通圈网络FQCC(n) (n > 1)和细胞分裂生长图模型设计出了一种新的互连网络——FQCC(n,k) (n > 1，k是非负整数)：用三长的圈代替FQCC(n)的每个顶点且圈中每个顶点恰位于折叠立方体连通圈网络FQCC(n) (n > 1)中与该顶点关联的一条边上，得到新的网络FQCC(n,1)；再类似的用三长的圈代替FQCC(n,1)的每个顶点得FQCC(n,2)，循环执行上述方法k次得到的新网络称为FQCC(n,k) (n > 1，k是非负整数)。该网络FQCC(n,k)在保持了FQCC(n)的小的固定的度(为3)的特性外，还有比FQCC(n)更好的扩展性。进而提出了猜想：FQCC(n,k)是Hamilton图。赵媛证明了FQCC(2,k)是平面图和Hamilton图，还证明了FQCC(n,k) (k > 1)不是点可迁的。

互连网络是超级计算机的重要组成部分。网络遵循八个原则：小的固定顶点度；小通信传输延迟；简单的路由算法；均匀性或对称性；高容错性；可扩性；可嵌入性；有效的布图算法。大规模集成电路技术的出现和现代通信技术的飞速发展要求人们设计出多核的互连网络，对这种网络来讲网络的平面性是一项很重要的指标。互连网络的基本拓扑结构是连通图G(V,E)。其中V 是处理器的集合，E 是网络通信链路的集合[1] [2]。

许多学者设计出了多种互连网络，例如：折叠Petersen 立方体、折叠立方体、正则图连通圈网络(折叠立方体连通圈网络，立方体连通圈网络等)、细胞分裂生长图模型、层次环群论模型等并给出了它们的部分性质[3]-[17]。这些互连网络都有许多优点，也各自存在一些缺点。比如折叠立方体，它的度(n + 1)随着规模( 2n )的增大而增大。

折叠立方体连通圈具有优点——小的固定的度(都为3)， 但它的扩展性较差。

在这篇文章中，根据文献[8]和[10]中提出的设计互连网络的新思想，师海忠设计出了新的互连网络() (), 2, 0FQCC n knk≥≥。除了保持折叠立方体连通圈( )FQCC n 的优点——小的固定的度(为3)外，当固定n 之后，它有较好的可扩展性，即规模可随着k 的增大而增大。特别是赵媛证明了()2, FQCCk 是个平面图和Hamilton 图，还证明了() (), 2FQCC n kk ≥不是点可迁的。

本文其余结构是：第2 节，基本概念；第3 节，新互连网络k 及其性质；第4 节，结束语。

2. 基本概念 定义1 [14]：令0 11nxx xx −=是一个n 比特二元串， 我们用( ) jx来定义比特jx 。

令( )ixy=当x 和y 仅在第i 个位置比特不同。