Computer Science and Application 计算机科学与应用, 2024, 10(6), 1122-1130 Published Online June 2024 in Hans. http://www.hanspub.org/journal/csa https://doi.org/10.12677/csa.2024.106116
The Hamiltonian Decomposition and Its Properties of Exchanged Folded Crossed Cube
Yaxin Gou
College of Mathematics and Statistics, Northwest Normal University, Lanzhou Gansu
ththth
Received: May 16, 2024; accepted: May 28, 2024; published: Jun. 4, 2024
Abstract
Exchanged folded crossed cube (EFCQ(s,t)) is a new interconnection network for parallel com-putation. 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.
Keywords
Exchanged Folded Crossed Cube, Hamiltonian Decomposition, Hamiltonian Cycle, Perfect Matching
交换折叠交叉立方体的Hamilton分解及其性质
苟娅昕
西北师范大学数学与统计学院，甘肃 兰州
收稿日期：2024年5月16日；录用日期：2024年5月28日；发布日期：2024年6月4日
摘 要
交换折叠交叉立方体(EFCQ(s,t))是一种用于并行计算的新型互连网络。在这篇文章中，作者证明了
s=t=1;2时，EFCQ(s,t)是Hamilton可分解的；s=t=1;2;3时，EFCQ(s,t)可以分解为一个Hamilton
圈和s个完美对集。最后对EFCQ(s,t)的一些性质进行了证明。
文章引用: 苟娅昕. 交换折叠交叉立方体的Hamilton分解及其性质[J]. 计算机科学与应用, 2024, 10(6): 1122-1130. DOI: 10.12677/csa.2024.106116
苟娅昕
关键词
交换折叠交叉立方体，Hamilton可分解，Hamilton圈，完美对集
Copyright ? 2024 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0). http://creativecommons.org/licenses/by/4.0/
Open Access 1. 引言
互连网络在并行计算机系统中扮演了十分重要的角色，影响着系统的性能。尤其是在硬件开销，可扩展性，通信性能，可靠性等方面起着决定性的作用。为使大规模的并行计算系统拥有性能高的优点，并且极大地降低成本。选择有效的互连网络拓扑，成为研究界非常关注的重点。刚开始提出的均为一些平凡网络，但这些网络很多都存在不足之处。但随着超立方体网络的诞生，因为其可扩展性，正则性，强容错性以及对称性，这些很好的性质，使得超立方体网络成为并行处理和并行计算机系统常用的拓扑之一，并且得到了非常广泛的应用。与此同时超立方体网络的某些方面又存在一定的不足，为了改进这些现有的问题，超立方体的变型又被相继提出。例如折叠交叉立方体[1]，交换超立方体[2]，交换交叉立方体[3]，交叉超立方体[4]，莫比乌斯立方体[4]等。其中，K. Bhavani和Sudarson Jena在2024年提出交换折叠交叉立方体。交换折叠交叉立方体的出现，相对于互连网络中其他拓扑，在成本和直径上有了实质性的改善。2024年，蔡学鹏，杨伟等人提出交换折叠交叉立方体的连通度和超连通度。
在这篇文章中，证明了交换折叠交叉立方体的正则性以及该网络是一个Hamilton图，并且证明了在EFCQ(s,t)中，若有s=t=1;2，则EFCQ(s,t)是Hamilton可分解的和若有s=t=1;2;3，则EFCQ(s,t)可以分解为一个Hamilton圈和s个完美对集的并。并且给出了EFCQ(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)=2k，且E(G)能被划分成k个Hamilton圈；
要么b) deg(G=)2k+1，且E(G)能被划分成k个Hamilton圈和一个完美对集。 其中deg(G)表示G的顶点度。
定义6 [7] [8] [9] s+t+1-维交换折叠交叉立方体网络被定义为一个无向图EFCQ(s,t)=(V,E)，其中
s≥1,t≥1。
=VV是图中顶点的集合，且
DOI: 10.12677/csa.2024.106116
{as?1?a0bt?1?b0c|ai,bj,c∈{0,1},i∈[0,s?1],j∈[0,t?1]}。
E是图中边的集合，且E是由四种互不相交的边集E1∪E2∪E3∪E4组成，对任意两个顶点有
1123
计算机科学与应用
苟娅昕
u,v∈V,E1,E2,E3,E4，定义如下
1) (u,v)∈E1，当且仅当u[0]≠v[0],u⊕v=1其中⊕是异或操作。
2) (u,v)∈E2，当且仅当u[t=:1]v[t:1],u=[0]v=[0]0并且(u[s+t:t+1],v[s+t:t+1])∈E(CQS)。 3) (u,v)∈E3，当且仅当u[s+t:t+1]=v[s+t:t+1],u[0]=v[0]=1并且(u[t:1],v[t:1])∈E(CQt)。
as?1?a0bt?1?b0c},v{=当且仅当u4) (u,v)∈E4，
{as?11?ai,bj=1?bj,c=1?c ?a0bt?1?b0c且ai=}ai,bj,c∈{0,1},i∈[0,s?1],j∈[0,t?1]。
3. 主要结果
引理[7]在EFCQ(s,t)中二进制字符串最低位为0的点的度为s+2；二进制字符串最低位为1的点的度为t+2。
定理1：EFCQ(s,t)是正则的，若s=t,s≥1,t≥1。 EFCQ(s,t)是非正则的，若s≠t,s≥1,t≥1。
证明：K. Bhavani在文献[7]中证明了EFCQ(s,t)的度。在EFCQ(s,t)中二进制字符串最低位为0的点的度为s+2；二进制字符串最低位为1的点的度为t+2。故当s=t时，在EFCQ(s,t)中，对任意v∈V，都有deg(v)=s+2。根据定义3，EFCQ(s,t)是正则的。同理，当s≠t时，EFCQ(s,t)是非正则的。
定理2：EFCQ(s,t)是Hamilton图。
证明：周东仿在文献[9]中，提出了Hamiltonian cycle算法，通过调用这个算法可以得到ECQ(s,t)上的一个Hamilton圈。由于EFCQ(s,t)是在ECQ(s,t)的基础上在互补的两个点上增加一条补边所得，根据定义2，EFCQ(s,t)是Hamilton图。
定理3：1) EFCQ(1,1)是Hamilton可分解的。 2) EFCQ(2,2)是Hamilton可分解的。
证明1)：在EFCQ(1,1)中，deg(EFCQ(1,1))=3，EFCQ(1,1)是正则图。则根据定义5可知EFCQ(1,1)能被划分成1个边不交的Hamilton圈和1个完美对集的并(如图1)。
Figure 1. EFCQ(1,1) 图1. EFCQ(1,1)的图表示
EFCQ(1,1)中的Hamilton圈为：
100-101-111-110-010-011-001-000-100 EFCQ(1,1)中的完美对集为：
100-011, 101-010, 111-000, 110-001
证明2)：在EFCQ(2,2)中，deg(EFCQ(2,2))=4，EFCQ(2,2)是正则图。则根据定义5可知EFCQ(2,2)能被划分成2个边不交的Hamilton圈(如图2)。
EFCQ(2,2)中的Hamilton圈H1为：
DOI: 10.12677/csa.2024.106116
1124
计算机科学与应用
苟娅昕
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
EFCQ(2,2)中的Hamilton圈H2为：
01000-11000-00111-00101-11010-10010-01101-01001-10110-00110-11001-11101-00010-01010-10101-1
0001-01110-11110-00001-00011-11100-10100-01011-01111-10000-00000-11111-11011-00100-01100-10011-10111-01000
Figure 2. EFCQ(2,2) 图2. EFCQ(2,2)的图表示
定理4 1) EFCQ(3,3)可以分解为24个8圈16个4圈和一个完美对集并。 2) EFCQ(3,3)可以分解为32个4圈16个8圈和一个完美对集并。
3) EFCQ(3,3)可以分解为一个Hamilton圈22个4圈5个8圈和一个完美对集的并(如图3)。
图3是ECQ(3,3)，EFCQ(3,3)是在它的基础上增加补边，连接ECQ(3,3)中互补的两个点所得。 证明1)：令a2∈{0,1}，EFCQ(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；
DOI: 10.12677/csa.2024.106116
1125
计算机科学与应用
苟娅昕
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； 令a2a1a0∈{000,001,010,011,100,101,110,111}，24个8圈中剩余8个8圈可以表示为：
a2a1a01101-a2a1a01111-a2a1a00011-a2a1a00001-a2a1a01001-a2a1a01011-a2a1a00111-a2a1a00101-a2a1a01101
Figure 3. ECQ(3,3) 图3. ECQ(3,3)的图表示
DOI: 10.12677/csa.2024.106116
1126
计算机科学与应用
交换折叠交叉立方体的Hamilton分解及其性质 - 图文
