王海鋒++師海忠

摘要：互連網絡是超級計算機的重要組成部分，在設計和選擇一個互連網絡時，Hamilton性是評估網絡性能的一個重要指標，Mobius立方體作為最重要的互連網絡拓撲結構之一，也具有優(yōu)良的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節(jié)，概念及其基本性質；第3節(jié)，MQn（n=3，4，5，6）的Hamilton分解；第4節(jié)，結束語。

1 概念及基本性質

本文所考慮的圖都是有限的簡單無向圖，也就是說所考慮的無向圖都有有限的頂點集和邊集，并且既不包含環(huán)，也沒有兩條連接同一對頂點的邊。下面介紹文中用到的概念，記號以及一些基本性質。

定義1設G=（V，E）是一個無向圖，其中V=V（G），E=E（G）分別表示圖G的頂點集和邊集。用圖表示互連網絡時，頂點代表網絡節(jié)點（處理器），邊代表節(jié)點之間直接通信連接。

定義2圖G中一個點邊接續(xù)交替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有直徑有直徑平均距離滿足：

互連網絡在發(fā)生某些鏈接故障時，各處理器能否保持通信，是結構設計中的一個重要問題，其中路和圈的嵌入是衡量其性能的重要指標，而Hamilton圈作為互連網絡中最長的圈，引起設計者的很多關注。本節(jié)將證明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是否成立還有待進一步的研究。