《Mobius超立方体网络的Hamilton分解》-工学论文，软件工程论文-论文范文参考-科学狗论文网

标题

Mobius超立方体网络的Hamilton分解

范文

王海锋++师海忠

摘要：互连网络是超级计算机的重要组成部分，在设计和选择一个互连网络时，Hamilton性是评估网络性能的一个重要指标，Mobius立方体作为最重要的互连网络拓扑结构之一，也具有优良的Hamilton性，师海忠提出两个猜想：猜想1：Mobius立方体网络MQn是Hamilton可分解的；猜想2：当n=2k（k≥2）时，MQ，，是边不交的z（1≤i≤k）个Hamilton圈和”-2z个完美匹配的并；当n=2k+l （k>l）时，MQn是边不交的i（1≤i≤k）个Hamilton圈和n-2i个完美匹配的并。当i=k时，猜想2即为猜想1。本文将对n=3，4，5时，证明猜想1和猜想2是正确的，当n=6；i=1，2时，猜想2是成立的。

关键词：Mobius立方体；Hamilton圈；完美匹配；互连网络；超级计算机

中图分类号：TP393 文献标识码：A DOI： 10.3969/j.issn.1003-6970.2015.10.023

引言

互连网络是超级计算机的重要组成部分，其拓扑结构可以模型化为一个图，互连网络的设计及其性质的研究是超级计算机的一个重要课题。

超立方体网络是现今典型的，最有效的互连网络拓扑结构，Mobius立方体是超立方体的一种变形，由Cull和Larson于1995年首次文献中提出，被证明与含有相同数目点的超立方体相比具有更好的性能。和超立方体一样，Mobius立方体也是可扩展的，也有简单的路由算法和高容错性，而且它的直径只有大约超立方体直径的1/2，平均距离只有超立方体的2/3，其中具有Hamilton性是设计网络时最基本也是最重要的要求之一，在文献中，师海忠提出如下猜想：

猜想1：Mobius立方体是Hamilton可分解的。

师海忠进一步给出一个更强的猜想：

猜想2：当n 2k（k≥2）时，MQn是边不交的i（1≤i≤k）个Hamilton圈和n-2i个完美匹配的并；当n=2k+l（k>1）时，MQn是边不交的i（1≤i≤k）个Hamilton圈和n-2i个完美匹配的并。

当i=k时，猜想2即为猜想1。

本文证明n=3，4，5时，Mobius立方体是Hamilton可分解的，即当n=3，4，5时猜想l和猜想2是正确的，当n 6；i=1，2时，猜想2是成立的。

本文其余结构如下：第2节，概念及其基本性质；第3节，MQn（n=3，4，5，6）的Hamilton分解；第4节，结束语。

1 概念及基本性质

本文所考虑的图都是有限的简单无向图，也就是说所考虑的无向图都有有限的顶点集和边集，并且既不包含环，也没有两条连接同一对顶点的边。下面介绍文中用到的概念，记号以及一些基本性质。

定义1设G=（V，E）是一个无向图，其中V=V（G），E=E（G）分别表示图G的顶点集和边集。用图表示互连网络时，顶点代表网络节点（处理器），边代表节点之间直接通信连接。

定义2图G中一个点边接续交替J叶J现的序列称为图G的一条途径，其中和Vik分别称为途径w的起点和终点，w上其余顶点称为中途点；图G中边不重复出现的途径称为迹，起点和终点相同的途径称为闭途径，边不重复出现的闭途径称为闭迹，中途点不重复出现的闭迹称为圈；经过图G的每个顶点一次的圈称为一个Hamilton圈，记为HC。

定义3设G是一个图，由G中一些不相邻的边组成的集合M称为G的一个匹配，对匹配M中每条边e=uv，其两端点u和v被称为匹配M所匹配，而u和v都称为是M饱和的。如果图G中每个顶点都是M饱和的，则称M是G的完美匹配。图G的含边数最多的匹配称为G的最大匹配，可见图G的完美匹配也是它的最大匹配。

定义4n维Mobius立方体，记为且MQn是无向图，它的顶点集与超立方体Qn一样，顶点X=X1X2.…Xn连到另外n个顶点Yi（1≤i≤n）

x与Yi之间是否有边确定，于是，当xo=0时，该网络称为O-Mobius立方体；当Xo=1时，该网络称为l-Mobius立方体，分别表示为0- MQn和1-MQn。

定义5设G是正则图，E（G）是G的边集，我们称G是Hamilton可分解的，如果

要么（a）d（G）=2k且E能被划分成k个边不交的Hamilton圈；

要么（b）d（G）=2k+1且E（G）能被划分成k个边不交的Hamilton圈和一个完美匹配。

MQn的主要性质：

（a）MQn是n正则的，有个2n顶点和n2n-1条边，MQ有连通度n；

（b）o-MQn有直径有直径平均距离满足：

互连网络在发生某些链接故障时，各处理器能否保持通信，是结构设计中的一个重要问题，其中路和圈的嵌入是衡量其性能的重要指标，而Hamilton圈作为互连网络中最长的圈，引起设计者的很多关注。本节将证明MQn（n=3，4，5）是Hamilton可分解的，MQ6可分解成两个边不交的Hamilton圈和两个完美匹配，从而找出MQn（n=3，4，5，6）相应的Hamilton圈和相应的完美匹配，具体见定理1-4。

定理l MQ3是一个Hamilton圈和一个完美匹配的并，即当n=3时，猜想l和猜想2是正确的。

证明：如图l，MQ3是3正则图，共有8个顶点

0-MQ3的Hamilton圈为：

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

完美匹配为：000-001， 010-011，100-111，101-110：

1-MQ3的Hamilton圈为：

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

完美匹配为：000-001，010-011，100-111，101-110：

所以当n=3时猜想l是正确的，猜想2中i=k=l即为猜想l，也是正确的，定理l得证。定理2（1）MQ4是两个边不交的Hamilton圈的并，即n=4时猜想l和/=k=2时猜想2是正确的；（2） MQ4是一个Hamilton圈和两个完美匹配的并，即i=1时猜想2是正确的。

证明：如图2，MQ4是4正则图，共有16个顶点

0-MQ4的Hamilton圈为：

HC1：

0000-0001-0011-0010-0110-0101-0100-0111-1111-1100-1101-1110-1001-1011

-1010-1000-0000：

HG2：

0000-0010-1010-1101-0101-0001-1001-1000-1111-1110

-0110-0111-0011-1011-1100-0100-0000：

1-MQ4的Hamilton圈为：

Hc1：

0000-0001-0101-0100-0111-0110-0010-0011-1100-1101-1110-1001-1011-1010

-1000-1111-0000：

HC2：

0000-0010-1101-1010-0101-0110-1001-1000-0111-0011

-0001-1110-1111-1100-1011-0100-0000：

所以当n=4时猜想l是正确的，当i=k=2时猜想2即为猜想l，也是正确的，（1）成立；对于（2），由（1）的证明知MQ4中有两个边不交的Hamilton圈，对0-MQ4不妨取HC2：0000-0010--1010-1101--0101-0001--1001-1000--1111-1110--0110-0111--

0011-1011--1100-0100--0000；其中一连接的表示完美匹配l，--连接的表示完美匹配2，所以对0-MQ4，i=1时猜想2是正确的；同理可证1-MQ4，i=1时猜想2是正确的，（2）成立，定理2得证。

定理3（1） MQ5是两个边不交的Hamilton圈和一个完美匹配的并，即n=5时猜想l和i=k=2时猜想2是正确的；（2） MQs是一个Hamilton圈和三个完美匹配的并，即i=1时猜想2是正确的。

证明：如图3，MQ5是5正则图，共有32个顶点

0-MQ5的Hamilton圈为：

Hc1：

00000-00001-100011-00010-00110-00101-00100—00111-01111-01100-01101-01110

-01001-01011-01010-01000-11000-11010-11011-1100 1-11110-11101-11100-11111-10111

-10100-10101-10110-10010-10011-10001-10000-00000；

HC2： 00000-00010-10010-10000

-10100-11100-11011-10011-10111-10110-11110-11111-11000-11001-10 001-10101-11101

-11010-01010-01101-00101-00001-01001-01000-01111-01110-00110-00111-00011-01011

-01100-00100-00000：

完美匹配为：00000-01000，00010-01010，00001-10001，00100-10100，00101-10101，

00110-10110，00111-10111，01100-11100.01111-11111，01101-11101，01011-11011，

01001-11001，11000-10000，10010-11010.00011-10011，01110-11110；

1-MQ5的Hamilton圈为：

HC1：

00000-00001-00101-00100-00111-00110-00010-00011-01100-01101-01110-01001

-01011-01010-01000-01111-11111-11000-11010-11011-11001-11110-11101-11100-10011

-10010-10110-10111-10100-10101-10001-10000-00000；

HC2：00000-00010-10010-10000

-10100-11011-11100-11111-11110-10001-10011-10111-11000-11001-10110-10101-11010

-11101-01101-01010-00101-00110-01001-01000-00111-00011-00001-01110-01111-01100

-01011-00100-00000：

完美匹配为：00000-01111，00010-01101，00110-10110，00111-10111，00100-10100，

00101-10101，01000-11000. 01010-11010.01001-11001， 01011-11011，01100-11100，

01110-11110，00011-10011. 00001-10001.10000-11111，10010-11101；

所以当n=5时猜想l是正确的，当i=k=2时猜想2即为猜想l，也是正确的，（1）成立。对于（2）利用定理2中（2）的证明方法可证（2）成立，定理3得证。

定理4（1）MQ6是两个边不交的Hamilton圈和两个完美匹配的并，即对MQ6来说，i=2时猜想2是正确的；（2） MQ6是一个Hamilton圈和四个完美匹配的并，即对于MQ6来说，i=1时猜想2是正确的。

证明：如图4，图5，MQ6是6正则图，共有64个顶点

0-MQ6的Hamilton圈为：

HC1：

000000-000001-000011-000010-000110-000101-000100-000111-001111-001100

-001101-001110-001001-001011-001010-001000-011000-011010-011011-011001-011110

-011101-011100-011111-010111-010100-010101-010110-010010-010011-010001-010000

-110000-110001-110011-110010-110110-110101-110100-110111-111111-111100-111101

-111110-111001-111011-111010-111000-101000-101010-101011-101001-101110-101101

-101100-101111-100111-100100-100101-100110-100010-100011-100001-100000-000000：

HC2：

000000-000010-100010-100000-100100-101100 -101011-100011-100111-100110

-101110-101111-101000-101001-100001-100101-101101-101010-111010-111101-11010l

-110001-111001-111000-111111-111110-110110-110111-110011-111011-111100-110100

-110000-110010-010010-010000-010100-011100-011011-010011-010111-010110-011110

-011111-011000-011001-010001-010101-011101-011010-001010-001101-000101-000001

-001001-001000-001111-001110-000110-000111-000011-001011-001100-000100-000000：

完美匹配l为：000000-001000， 000001-010001，000100-010100，000110-010110，

000101-010101，000111-010111，000011-01001l， 000010-010010，001001-011001，

001100-011100，001110-011110，001101-011101，001111-011111，001011-011011，

001010-101010，011010-111010，011000-010000， 110010-100010，110011-100011，

110111-100111，110101-100101，110110-100110，100100-100100，110000-111000，

111111-101111，111101-101101，111110-101110.111100-101100.

111011-101011.

110001-100001，100000-101000，111001-101001；

完美匹配2为：000000-010000， 000001-100001，000100-100100，000110-100110.

000101-100101，000111-100111，000010-001010，000011-100011，001000-101000，

001001-101001，001100-101100， 001101-101101， 001111-101111，001011-101011，

011000-111000，OllOOl-lllOOI。011110-111110，011100-111100，011111-111111，

011101-111101，011010-010010，011011-111011，010001-110001，010100-110100，

010110-110110，010111-110111，010101-110101，010011-110011，110010-111010，

110000-100000，101010-100010，001110-101110；

1-MQ6的 Hanulton圈为：

HC1：

000000-000001-000101-000100-000111-000110-000010-000011-001100-001101

-001110-001001-001011-001010-001000-001111-011111-011000-011010-011011-011001

-011110-011101-011100-010011-010010-010110-010111-010100-010101-010001-010000

-110000-110001-110101-110100-110111-110110-110010-110011-111100-111101-111110

-111001-111011-111010-111000-111111-101111-101000-101010-101011-101001-101110

-101101-101100-100011-100010-100110-100111-100100-100101-100001-100000-000000；

HC2：

000000-0001000-001011-001100-001111-001110-000001-000011-000111-001000

-001001-000110-000101-001010-001101-011101-011010-010101-010110-011001-011000

-010111-010011-010001-011110-011111-011100-011011-010100-010000-010010-110010

-110000-110100-111011-111100-111111-111110-110001-110011-110111-111000-111001

-110110-110101-111010-111101-101101-101010-100101-100110-101001-101000-100111

-100011-100001-101110-101111-101100-101011-100100-100000-100010-000010-000000：

完美匹配l为：000000-001111，000001-10000l，000100-100100， 000110-100110，

000101-100101，000111-001101，000011-10001l，000010-010010， 001110-101110，

001011-011011，001001-101001，001010-101010，001000-101000，001100-101100，

001101-101101，011110-111110，011111-010000，011001-111001，011000-111000，

011010-111010，011101-111101，011100-111100，010001-110001，010110-110110，

010100-110100，010111-110111，010101-11010l，010011-110011， 110010-100010，

110000-111111，111011-101011，100000-101111；

完美匹配2为：000000-010000， 000001-010001，000100-010100，000110-010110，

000101-010101，000111-010111，000011-01001l，000010-001101，001111-101111，

001110-011110，001011-101011，001001-011001，001010-011010， 001000-011000，

001110-011100. 011111-111111，011011-111011，011101-010010，110010-111101，

110011-100011， 110111-100111， 110101-100101，110110-100110，110100-100100，

110000-100000，110001-100001，111100-101100，11000-101000，111010-101010，

111001-101001，111110-101110，101101-100010；

所以对于MQ6来说，i=2时猜想2是正确的，即定理中（1）成立；利用定理2中（2）的证明方法可证（2）成立，定理4得证。3结束语

本文对n=3，4，5，6时，Mobius立方体网络MQn，的Hamilton性进行了研究，由文献知MQn是Hamilton的。在这篇文章中证明了当n=3，4，5时猜想l和猜想2是正确的，当n= 6；i=1，2时猜想2是成立的。对于MQn（n≥7），我们可以找到一个Hamilton圈，对MQn，（n≥7），猜想l和猜想2是否成立还有待进一步的研究。

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。