计算机科学与应用  >> Vol. 10 No. 6 (June 2020)

交换折叠交叉立方体的Hamilton分解及其性质
The Hamiltonian Decomposition and Its Properties of Exchanged Folded Crossed Cube

DOI: 10.12677/CSA.2020.106116, PDF, 下载: 174  浏览: 254 

作者: 苟娅昕:西北师范大学数学与统计学院,甘肃 兰州

关键词: 交换折叠交叉立方体Hamilton可分解Hamilton圈完美对集Exchanged Folded Crossed Cube Hamiltonian Decomposition Hamiltonian Cycle Perfect Matching

摘要: 交换折叠交叉立方体(EFCQ(s,t))是一种用于并行计算的新型互连网络。在这篇文章中,作者证明了s=t=1;2 时,EFCQ(s,t)是Hamilton可分解的;s=t=1;2;3时,EFCQ(s,t)可以分解为一个Hamilton圈和s个完美对集。最后对EFCQ(s,t)的一些性质进行了证明。
Abstract: Exchanged folded crossed cube (EFCQ(s,t)) is a new interconnection network for parallel computation. In this article, author proved EFCQ(s,t) is Hamiltonian decomposition, when s=t=1;2. And EFCQ(s,t) can be decomposed into a Hamiltonian cycle and s perfect matching, when s=t=1;2;3. Finally, some properties of EFCQ(s,t) are proved.

文章引用: 苟娅昕. 交换折叠交叉立方体的Hamilton分解及其性质[J]. 计算机科学与应用, 2020, 10(6): 1122-1130. https://doi.org/10.12677/CSA.2020.106116

1. 引言

互连网络在并行计算机系统中扮演了十分重要的角色,影响着系统的性能。尤其是在硬件开销,可扩展性,通信性能,可靠性等方面起着决定性的作用。为使大规模的并行计算系统拥有性能高的优点,并且极大地降低成本。选择有效的互连网络拓扑,成为研究界非常关注的重点。刚开始提出的均为一些平凡网络,但这些网络很多都存在不足之处。但随着超立方体网络的诞生,因为其可扩展性,正则性,强容错性以及对称性,这些很好的性质,使得超立方体网络成为并行处理和并行计算机系统常用的拓扑之一,并且得到了非常广泛的应用。与此同时超立方体网络的某些方面又存在一定的不足,为了改进这些现有的问题,超立方体的变型又被相继提出。例如折叠交叉立方体 [1],交换超立方体 [2],交换交叉立方体 [3],交叉超立方体 [4],莫比乌斯立方体 [4] 等。其中,K. Bhavani和Sudarson Jena在2018年提出交换折叠交叉立方体。交换折叠交叉立方体的出现,相对于互连网络中其他拓扑,在成本和直径上有了实质性的改善。2019年,蔡学鹏,杨伟等人提出交换折叠交叉立方体的连通度和超连通度。

在这篇文章中,证明了交换折叠交叉立方体的正则性以及该网络是一个Hamilton图,并且证明了在 E F C Q ( s , t ) 中,若有 s = t = 1 ; 2 ,则 E F C Q ( s , t ) 是Hamilton可分解的和若有 s = t = 1 ; 2 ; 3 ,则 E F C Q ( s , t ) 可以分解为一个Hamilton圈和s个完美对集的并。并且给出了 E F C Q ( 3 , 3 ) 的三条性质。

2. 基本概念

定义1 [5] G的Hamilton圈是指包含G的每个顶点的圈。

定义2 [5] 一个图若包含Hamilton圈,则称这个图是Hamilton图。

定义3 [5] 称图G是k正则的,若对所有 v V ,有 d ( v ) = k

定义4 [5] 设M是E的一个子集,它的元素是G中的连杆,并且这些连杆中的任意两个在G中均不相邻,则称M为G的对集(或匹配);M中的一条边的两个端点称为在M下是配对的;若对集M的某条边与顶点v关联,则称M饱和顶点v,并且称v是M饱和的,否则称v是M非饱和的。若G的每个顶点均为M饱和的,则称M为G的完美对集。

定义5 [6] 设G是正则图, E ( G ) 是G的边集,我们称G是Hamilton可分解的,如果

要么a) deg ( G ) = 2 k ,且 E ( G ) 能被划分成k个Hamilton圈;

要么b) deg ( G ) = 2 k + 1 ,且 E ( G ) 能被划分成k个Hamilton圈和一个完美对集。

其中 deg ( G ) 表示G的顶点度。

定义6 [7] [8] [9] s + t + 1 -维交换折叠交叉立方体网络被定义为一个无向图 E F C Q ( s , t ) = ( V , E ) ,其中 s 1 , t 1

V是图中顶点的集合,且 V = { a s 1 a 0 b t 1 b 0 c | a i , b j , c { 0 , 1 } , i [ 0 , s 1 ] , j [ 0 , t 1 ] }

E是图中边的集合,且E是由四种互不相交的边集 E 1 E 2 E 3 E 4 组成,对任意两个顶点有 u , v V , E 1 , E 2 , E 3 , E 4 ,定义如下

1) ( u , v ) E 1 ,当且仅当 u [ 0 ] v [ 0 ] , u v = 1 其中 是异或操作。

2) ( u , v ) E 2 ,当且仅当 u [ t : 1 ] = v [ t : 1 ] , u [ 0 ] = v [ 0 ] = 0 并且 ( u [ s + t : t + 1 ] , v [ s + t : t + 1 ] ) E ( C Q S )

3) ( u , v ) E 3 ,当且仅当 u [ s + t : t + 1 ] = v [ s + t : t + 1 ] , u [ 0 ] = v [ 0 ] = 1 并且 ( u [ t : 1 ] , v [ t : 1 ] ) E ( C Q t )

4) ( u , v ) E 4 ,当且仅当 u = { a s 1 a 0 b t 1 b 0 c } , v = { a s 1 ¯ a 0 ¯ b t 1 ¯ b 0 ¯ c ¯ } a i ¯ = 1 a i , b j ¯ = 1 b j , c ¯ = 1 c

a i , b j , c { 0 , 1 } , i [ 0 , s 1 ] , j [ 0 , t 1 ]

3. 主要结果

引理 [7] 在 E F C Q ( s , t ) 中二进制字符串最低位为0的点的度为 s + 2 ;二进制字符串最低位为1的点的度为 t + 2

定理1: E F C Q ( s , t ) 是正则的,若 s = t , s 1 , t 1

E F C Q ( s , t ) 是非正则的,若 s t , s 1 , t 1

证明:K. Bhavani在文献 [7] 中证明了 E F C Q ( s , t ) 的度。在 E F C Q ( s , t ) 中二进制字符串最低位为0的点的度为 s + 2 ;二进制字符串最低位为1的点的度为 t + 2 。故当 s = t 时,在 E F C Q ( s , t ) 中,对任意 v V ,都有 deg ( v ) = s + 2 。根据定义3, E F C Q ( s , t ) 是正则的。同理,当 s t 时, E F C Q ( s , t ) 是非正则的。

定理2: E F C Q ( s , t ) 是Hamilton图。

证明:周东仿在文献 [9] 中,提出了Hamiltonian cycle算法,通过调用这个算法可以得到 E C Q ( s , t ) 上的一个Hamilton圈。由于 E F C Q ( s , t ) 是在 E C Q ( s , t ) 的基础上在互补的两个点上增加一条补边所得,根据定义2, E F C Q ( s , t ) 是Hamilton图。

定理3:1) E F C Q ( 1 , 1 ) 是Hamilton可分解的。

2) E F C Q ( 2 , 2 ) 是Hamilton可分解的。

证明1):在 E F C Q ( 1 , 1 ) 中, deg ( E F C Q ( 1 , 1 ) ) = 3 E F C Q ( 1 , 1 ) 是正则图。则根据定义5可知 E F C Q ( 1 , 1 ) 能被划分成1个边不交的Hamilton圈和1个完美对集的并(如图1)。

Figure 1. E F C Q ( 1 , 1 )

图1. E F C Q ( 1 , 1 ) 的图表示

E F C Q ( 1 , 1 ) 中的Hamilton圈为:

100-101-111-110-010-011-001-000-100

E F C Q ( 1 , 1 ) 中的完美对集为:

100-011, 101-010, 111-000, 110-001

证明2):在 E F C Q ( 2 , 2 ) 中, deg ( E F C Q ( 2 , 2 ) ) = 4 E F C Q ( 2 , 2 ) 是正则图。则根据定义5可知 E F C Q ( 2 , 2 ) 能被划分成2个边不交的Hamilton圈(如图2)。

E F C Q ( 2 , 2 ) 中的Hamilton圈 H 1 为:

01000-01001-01011-01010-11010-11011-11001-11000-10000-10001-10011-10010-00010-00011-00111-00110-01110-01111-01101-01100-11100-11101-11111-11110-10110-10111-10101-10100-00100-00101-00001-00000-01000

E F C Q ( 2 , 2 ) 中的Hamilton圈 H 2 为:

01000-11000-00111-00101-11010-10010-01101-01001-10110-00110-11001-11101-00010-01010-10101-10001-01110-11110-00001-00011-11100-10100-01011-01111-10000-00000-11111-11011-00100-01100-10011-10111-01000

Figure 2. E F C Q ( 2 , 2 )

图2. E F C Q ( 2 , 2 ) 的图表示

定理4 1) E F C Q ( 3 , 3 ) 可以分解为24个8圈16个4圈和一个完美对集并。

2) E F C Q ( 3 , 3 ) 可以分解为32个4圈16个8圈和一个完美对集并。

3) E F C Q ( 3 , 3 ) 可以分解为一个Hamilton圈22个4圈5个8圈和一个完美对集的并(如图3)。

图3 E C Q ( 3 , 3 ) E F C Q ( 3 , 3 ) 是在它的基础上增加补边,连接 E C Q ( 3 , 3 ) 中互补的两个点所得。

证明1):令 a 2 { 0 , 1 } E F C Q ( 3 , 3 ) 中有24个8圈其中16个可以表示为:

a2001011-a2001010-a2011010-a2011011-a2011111-a2011110-a2001110-a2001111-a2001011;

a2001001-a2001000-a2011000-a2011001-a2011101-a2011100-a2001100-a2001101-a2001001;

a2000011-a2000010-a2010010-a2010011-a2010111-a2010110-a2000110-a2000111-a2000011;

a2000001-a2000000-a2010000-a2010001-a2010101-a2010100-a2000100-a2000101-a2000001;

a2101011-a2101010-a2111010-a2111011-a2111111-a2111110-a2101110-a2101111-a2101011;

a2101001-a2101000-a2111000-a2111001-a2111101-a2111100-a2101100-a2101101-a2101001;

a2100011-a2100010-a2110010-a2110011-a2110111-a2110110-a2100110-a2100111-a2100011;

a2100001-a2100000-a2110000-a2110001-a2110101-a2110100-a2100100-a2100101-a2100001;

a 2 a 1 a 0 { 000 , 001 , 010 , 011 , 100 , 101 , 110 , 111 } ,24个8圈中剩余8个8圈可以表示为:

a 2 a 1 a 0 1101 - a 2 a 1 a 0 1111 - a 2 a 1 a 0 0011 - a 2 a 1 a 0 0001 - a 2 a 1 a 0 1001 - a 2 a 1 a 0 1011 - a 2 a 1 a 0 0111 - a 2 a 1 a 0 0101 - a 2 a 1 a 0 1101

Figure 3. E C Q ( 3 , 3 )

图3. E C Q ( 3 , 3 ) 的图表示

b 2 b 1 b 0 c { 1000 , 1100 , 0000 , 0100 } , b 2 b 1 b 0 c { 1010 , 1110 , 0010 , 0110 }

E F C Q ( 3 , 3 ) 中有16个4圈可以表示为:

000 b 2 b 1 b 0 c - 010 b 2 b 1 b 0 c - 110 b 2 b 1 b 0 c - 100 b 2 b 1 b 0 c - 000 b 2 b 1 b 0 c 001 b 2 b 1 b 0 c - 011 b 2 b 1 b 0 c - 101 b 2 b 1 b 0 c - 111 b 2 b 1 b 0 c - 001 b 2 b 1 b 0 c 000 b 2 b 1 b 0 c - 010 b 2 b 1 b 0 c - 110 b 2 b 1 b 0 c - 100 b 2 b 1 b 0 c - 000 b 2 b 1 b 0 c 001 b 2 b 1 b 0 c - 011 b 2 b 1 b 0 c - 101 b 2 b 1 b 0 c - 111 b 2 b 1 b 0 c - 001 b 2 b 1 b 0 c

E F C Q ( 3 , 3 ) 中的完美对集为M:

0001000-1110111, 0001001-1110110, 0001011-1110100, 0001010-1110101, 0001100-1110011,

0001101-1110010, 0001111-1110000, 0001110-1110001, 0000000-1111111, 0000001-1111110,

0000011-1111100, 0000010-1111101, 0000100-1111011, 0000101-1111010, 0000111-1111000,

0000110-1111001, 0011000-1100111, 0011001-1100110, 0011011-1100100, 0011010-1100101,

0011100-1100011, 0011101-1100010, 0011111-1100000, 0011110-1100001, 0010000-1101111,

0010001-1101110, 0010011-1101100, 0010010-1101101, 0010100-1101011, 0010101-1101010,

0010111-1101000, 0010110-1101001, 0101000-1010111, 0101001-1010110, 0101011-1010100,

0101010-1010101, 0101100-1010011, 0101101-1010010, 0101111-1010000, 0101110-1010001,

0100000-1011111, 0100001-1011110, 0100011-1011100, 0100010-1011101, 0100100-1011011,

0100101-1011010, 0100111-1011000, 0100110-1011001, 0111000-1000111, 0111001-1000110,

0111011-1000100, 0111010-1000101, 0111100-1000011, 0111101-1000010, 0111111-1000000,

0111110-1000001, 0110000-1001111, 0110001-1001110, 0110011-1001100, 0110010-1001101,

0110100-1001011, 0110101-1001010, 0110111-1001000, 0110110-1001001.

即: E F C Q ( 3 , 3 ) 可以分解为24个8圈16个4圈和一个完美对集M的并。

证明2):令 a 2 a 1 a 0 { 000 , 010 , 100 , 110 } , a 2 a 1 a 0 { 001 , 011 , 101 , 111 }

a 2 a 1 a 0 = 000 时,同一个圈内 a 2 a 1 a 0 = 001 a 2 a 1 a 0 = 010 时,同一个圈内 a 2 a 1 a 0 = 011 ;当 a 2 a 1 a 0 = 100 时,同一个圈内 a 2 a 1 a 0 = 101 a 2 a 1 a 0 = 110 时,同一个圈内 a 2 a 1 a 0 = 111 E F C Q ( 3 , 3 ) 中的16个8圈可以表示为:

a 2 a 1 a 0 1000 - a 2 a 1 a 0 1001 - a 2 a 1 a 0 1011 - a 2 a 1 a 0 1010 - a 2 a 1 a 0 1010 - a 2 a 1 a 0 1011 - a 2 a 1 a 0 1001 - a 2 a 1 a 0 1000 - a 2 a 1 a 0 1000

a 2 a 1 a 0 1100 - a 2 a 1 a 0 1101 - a 2 a 1 a 0 1111 - a 2 a 1 a 0 1110 - a 2 a 1 a 0 1110 - a 2 a 1 a 0 1111 - a 2 a 1 a 0 1101 - a 2 a 1 a 0 1100 - a 2 a 1 a 0 1100

a 2 a 1 a 0 0000 - a 2 a 1 a 0 0001 - a 2 a 1 a 0 0011 - a 2 a 1 a 0 0010 - a 2 a 1 a 0 0010 - a 2 a 1 a 0 0011 - a 2 a 1 a 0 0001- a 2 a 1 a 0 0000 - a 2 a 1 a 0 0000

a 2 a 1 a 0 0100 - a 2 a 1 a 0 0101 - a 2 a 1 a 0 0111 - a 2 a 1 a 0 0110 - a 2 a 1 a 0 0110 - a 2 a 1 a 0 0111 - a 2 a 1 a 0 0101 - a 2 a 1 a 0 0100 - a 2 a 1 a 0 0100

a 2 a 1 a 0 { 000 , 001 , 010 , 011 , 100 , 101 , 110 , 111 } E F C Q ( 3 , 3 ) 中的32个4圈其中16个可以表示为:

a 2 a 1 a 0 1001 - a 2 a 1 a 0 1101 - a 2 a 1 a 0 0101 - a 2 a 1 a 0 0001 - a 2 a 1 a 0 1001

a 2 a 1 a 0 1011 - a 2 a 1 a 0 0111 - a 2 a 1 a 0 0011 - a 2 a 1 a 0 1111 - a 2 a 1 a 0 1011

E F C Q ( 3 , 3 ) 中有32个4圈剩余的16个和定理4 1)的证明中所找到的16个4圈相同。

完美对集为 E F C Q ( 3 , 3 ) 中的对集M。

即: E F C Q ( 3 , 3 ) 可以分解为16个8圈32个4圈和一个完美对集M的并。

证明3): E F C Q ( 3 , 3 ) 是一个Hamilton图,则可以找到 E F C Q ( 3 , 3 ) 中有一个Hamilton圈H

0011010-0011011-0010111-0010110-0000110-0000111-0000101-0000100-0010100-0010101-0010001-0010000-0000000-0000001-0000011-0000010-0010010-0010011-0011111-0011110-0001110-0001111-0001101-0001100-0011100-0011101-0011001-0011000-0001000-0001001-0001011-0001010-0101010-0101011-0101001-0101000-0111000-0111001-0111101-0111100-0101100-0101101-0101111-0101110-0111110-0111111-0110011-0110010-0100010-0100011-0100001-0100000-0110000-0110001-0110101-0110100-0100100-0100101-0100111-0100110-0110110-0110111-0111011-0111010-1011010-1011011-1010111-1010110-1000110-1000111-1000101-1000100-1010100-1010101-1010001-1010000-1000000-1000001-1000011-1000010-1010010-1010011-1011111-1011110-1001110-1001111-1001101-1001100-1011100-1011101-1011001-1011000-1001000-1001001-1001011-1001010-1101010-1101011-1101001-1101000-1111000-1111001-1111101-1111100-1101100-1101101-1101111-1101110-1111110-1111111-1110011-1110010-1100010-1100011-1100001-1100000-1110000-1110001-1110101-1110100-1100100-1100101-1100111-1100110-1110110-1110111-1111011-1111010-0011010

除去H所占用的边, E F C Q ( 3 , 3 ) 中剩余的边可以分解为的5个8圈22个4圈和一个完美对集的并。

其中所分解的5个8圈为:

0011001-0011011-0011111-0011101-0010101-0010111-0010011-0010001-0011001;

0111001-0111011-0111111-0111101-0110101-0110111-0110011-0110001-0111001;

1011001-1011011-1011111-1011101-1010101-1010111-1010011-1010001-1011001;

1111001-1111011-1111111-1111101-1110101-1110111-1110011-1110001-1111001;

0001010-0011010-0111010-0101010-1101010-1111010-1011010-1001010-0001010。

E F C Q ( 3 , 3 ) 中的22个4圈,其中14个4圈为定理4 1)证明中所找到的16个4圈中除去两个4圈0001010-0101010-1101010-1001010-0001010;0011010-0111010-1011010-1111010-0011010所得。

a 2 a 1 a 0 { 000 , 010 , 100 , 110 } ,22个4圈中剩余的8个4圈则可以表示为:

a 2 a 1 a 0 1001 - a 2 a 1 a 0 1101 - a 2 a 1 a 0 0101 - a 2 a 1 a 0 0001 - a 2 a 1 a 0 1001

a 2 a 1 a 0 1011 - a 2 a 1 a 0 0111 - a 2 a 1 a 0 0011 - a 2 a 1 a 0 1111 - a 2 a 1 a 0 1011

完美对集为 E F C Q ( 3 , 3 ) 中的对集M。

即: E F C Q ( 3 , 3 ) 可以分解为一个Hamilton圈5个8圈22个4圈和一个完美对集M的并。

定理5 1) E F C Q ( 1 , 1 ) 可以分解为一个Hamilton圈和1个完美对集的并。

2) E F C Q ( 2 , 2 ) 可以分解为一个Hamilton圈和2个完美对集的并。

3) E F C Q ( 3 , 3 ) 可以分解为一个Hamilton圈和3个完美对集的并。

证明1):根据定理3 1)的证明,显然可得。

证明2):根据定理3 2)的证明, E F C Q ( 2 , 2 ) 中有一个Hamilton圈为 H 1

它的完美对集为 M 1 , M 2

M1: 01000-11000, 01100-00100, 00000-10000, 11100-10100, 01010-00010, 01110-11110, 00110-10110, 11010-10010, 01001-01101, 01011-01111, 00001-00011, 00101-00111, 11001-11101, 11011-11111, 10001-10101, 10011-10111.

M2: 01000-10111, 01001-10110, 01011-10100, 01010-10101, 01100-10011, 01101-10010, 01111-10000, 01110-10001, 00000-11111, 00001-11110, 00011-11100, 00010-11101, 00100-11011, 00101-11010, 00111-11000, 00110-11001.

证明3):根据定理2, E F C Q ( 3 , 3 ) 是一个Hamilton图。已知 E F C Q ( 3 , 3 ) 中有一个Hamilton圈H。除去H所包含的边,将剩余的边割裂为九块 E a , E b , E c , E d , E e , E f , E g , E h , E i

Ea: 0001000-0101000, 0001100-0101100, 0000000-0100000, 0000100-0100100, 0011000-0111000, 0011100-0111100, 0010000-0110000, 0010100-0110100, 1001000-1101000, 1001100-1101100, 1000000-1100000, 1000100-1100100, 1011000-1111000, 1011100-1111100, 1010000-1110000, 1010100-1110100.

Eb: 0001010-0011010, 0001110-0101110, 0000010-0100010, 0000110-0100110, 0011110-0111110, 0010010-0110010, 0010110-0110110, 0101010-0111010, 1001010-1011010, 1001110-1101110, 1000010-1100010, 1000110-1100110, 1011110-1111110, 1010010-1110010, 1010110-1110110, 1101010-1111010.

Ec: 0001000-1001000, 0001100-1001100, 0000000-1000000, 0000100-1000100, 0011000-1111000, 0011100-1111100, 0010000-1110000, 0010100-1110100, 0101000-1101000, 0101100-1101100, 0100000-1100000, 0100100-1100100, 0111000-1011000, 0111100-1011100, 0110000-1010000, 0110100-1010100.

Ed: 0001010-1001010, 0001110-1001110, 0000010-1000010, 0000110-1000110, 0011010-0111010, 0011110-1111110, 0010010-1110010, 0010110-1110110, 0101010-1101010, 0101110-1101110, 0100010-1100010, 0100110-1100110, 0111110-1011110, 0110010-1010010, 0110110-1010110, 1011010-1111010.

Ee: 0001001-0001101, 0000001-0000101, 0011101-0010101, 0011001-0010001, 0011011-0011111, 0010011-0010111, 0101001-0101101, 0100001-0100101, 0111101-0110101, 0111001-0110001, 0111011-0111111, 0110011-0110111, 1001001-1001101, 1000001-1000101, 1011101-1010101, 1011001-1010001, 1011011-1011111, 1010011-1010111, 1101001-1101101, 1100001-1100101, 1111101-1110101, 1111001-1110001, 1111011-1111111, 1110011-1110111.

Ef: 0001101-0000101, 0001001-0000001, 0011001-0011011, 0011101-0011111, 0010001-0010011, 0010101-0010111, 0101101-0100101, 0101001-0100001, 0111001-0111011, 0111101-0111111, 0110001-0110011, 0110101-0110111, 1001101-1000101, 1001001-1000001, 1011001-1011011, 1011101-1011111, 1010001-1010011, 1010101-1010111, 1101101-1100101, 1101001-1100001, 1111001-1111011, 1111101-1111111, 1110001-1110011, 1110101-1110111.

Eg: 0001011-0001111, 0000011-0000111, 0100011-0100111, 0101011-0101111, 1001011-1001111, 1000011-1000111, 1101011-1101111, 1100011-1100111.

Eh: 0001111-0000011, 0001011-0000111, 0101111-0100011, 0101011-0100111, 1001111-1000011, 1001011-1000111, 1101111-1100011, 1101011-1100111.

E i = E ( M )

我们所割裂的九块,可以组成17种完美对集分别为:

M 1 , M 2 , M 3 , M 4 , M 5 , M 6 , M 7 , M 8 , M 9 , M 10 , M 11 , M 12 , M 13 , M 14 , M 15 , M 16 , M M 1 = ( E a E b E e E g ) , M 2 = ( E a E b E f E h ) , M 3 = ( E a E b E e E h ) , M 4 = ( E a E b E f E g ) , M 5 = ( E c E d E f E h ) , M 6 = ( E c E d E e E g ) M 7 = ( E c E d E e E h ) , M 8 = ( E c E d E f E g ) , M 9 = ( E c E b E e E g )

M 10 = ( E c E b E f E h ) , M 11 = ( E c E b E e E h ) , M 12 = ( E c E b E f E g ) M 13 = ( E a E d E f E h ) , M 14 = ( E a E d E e E g ) , M 15 = ( E a E d E e E h ) M 16 = ( E a E d E f E g )

E ( E F C Q ( 3 , 3 ) ) = E ( H ) E ( M ) E ( M 1 ) E ( M 5 ) = E ( H ) E ( M ) E ( M 2 ) E ( M 6 ) = E ( H ) E ( M ) E ( M 3 ) E ( M 8 ) = E ( H ) E ( M ) E ( M 4 ) E ( M 7 ) = E ( H ) E ( M ) E ( M 9 ) E ( M 13 ) = E ( H ) E ( M ) E ( M 10 ) E ( M 14 ) = E ( H ) E ( M ) E ( M 11 ) E ( M 16 ) = E ( H ) E ( M ) E ( M 12 ) E ( M 15 )

即: E F C Q ( 3 , 3 ) 可以分解为一个Hamilton圈和三个完美对集的并。

4. 结束语

交换折叠交叉立方体网络作为一种新型的互连网络,具有非常重要的意义。本文中给出了 E F C Q ( s , t ) 相关定理,对低维的交换折叠交叉立方体的Hamilton可分解性做了证明,但对于 s = t 3 的情况, E F C Q ( s , t ) 是否是Hamilton可分解的以及 s = t 4 情况,是否可以分解为一个Hamilton圈和s个完美对集的问题仍需要进一步研究证明。

参考文献

[1] Nibedita, A. and Tripathy, C.R. (2010) The Folded Crossed Cube: A New Interconnection Network for Parallel Systems. International Journal of Computer Applications, 4, 43-40.
[2] Lon, P.K.K., Hsu, W.J. and Pan, Y. (2005) The Ex-changed Hypercube. IEEE Transaction on Parallel and Distributed Systems, 16, 866-874.
https://doi.org/10.1109/tpds.2005.113
[3] Li, K., Mu, Y., Li, K. and Min, G. (2013) Exchanged Crossed Cube: A Novel Interconnection Network for Parallel Computation. IEEE Transaction on Parallel and Distributed Systems, 24, 2211-2219.
https://doi.org/10.1109/tpds.2012.330
[4] 徐俊明. 组合网络理论[M]. 北京: 科学出版社, 2007.
[5] Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan Press Ltd., London and Basingstoke.
[6] 师海忠. 正则图连通圈: 多种互连网络的统一模型[C]//中国运筹学会第十届学术交流会论文集, 2010: 202-208.
[7] Bhavani, K. and Jena, S. (2018) Exchanged Folded Crossed Cube: A New Interconnection Network for Parallel Computation. Information Processing Letters, 137, 40-46.
https://doi.org/10.1016/j.ipl.2018.04.017
[8] 蔡学鹏, 杨伟, 杜洁, 任佰通. 交换折叠交叉立方体的连通度和超连通度[J]. 吉首大学学报, 2019, 40(5): 1-9.
[9] 周东仿. 交换交叉立方体上若干性质的研究[D]: [博士学位论文]. 苏州: 苏州大学, 2017.