Mobius超立方體網(wǎng)絡(luò)的Hamilton分解

王海鋒++師海忠

摘要：互連網(wǎng)絡(luò)是超級(jí)計(jì)算機(jī)的重要組成部分，在設(shè)計(jì)和選擇一個(gè)互連網(wǎng)絡(luò)時(shí)，Hamilton性是評(píng)估網(wǎng)絡(luò)性能的一個(gè)重要指標(biāo)，Mobius立方體作為最重要的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之一，也具有優(yōu)良的Hamilton性，師海忠提出兩個(gè)猜想：猜想1：Mobius立方體網(wǎng)絡(luò)MQn是Hamilton可分解的；猜想2：當(dāng)n=2k（k≥2）時(shí)，MQ，，是邊不交的z（1≤i≤k）個(gè)Hamilton圈和”-2z個(gè)完美匹配的并；當(dāng)n=2k+l （k>l）時(shí)，MQn是邊不交的i（1≤i≤k）個(gè)Hamilton圈和n-2i個(gè)完美匹配的并。當(dāng)i=k時(shí)，猜想2即為猜想1。本文將對(duì)n=3，4，5時(shí)，證明猜想1和猜想2是正確的，當(dāng)n=6；i=1，2時(shí)，猜想2是成立的。

關(guān)鍵詞：Mobius立方體；Hamilton圈；完美匹配；互連網(wǎng)絡(luò)；超級(jí)計(jì)算機(jī)

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A DOI： 10.3969/j.issn.1003-6970.2015.10.023

引言

互連網(wǎng)絡(luò)是超級(jí)計(jì)算機(jī)的重要組成部分，其拓?fù)浣Y(jié)構(gòu)可以模型化為一個(gè)圖，互連網(wǎng)絡(luò)的設(shè)計(jì)及其性質(zhì)的研究是超級(jí)計(jì)算機(jī)的一個(gè)重要課題。

超立方體網(wǎng)絡(luò)是現(xiàn)今典型的，最有效的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，Mobius立方體是超立方體的一種變形，由Cull和Larson于1995年首次文獻(xiàn)中提出，被證明與含有相同數(shù)目點(diǎn)的超立方體相比具有更好的性能。和超立方體一樣，Mobius立方體也是可擴(kuò)展的，也有簡(jiǎn)單的路由算法和高容錯(cuò)性，而且它的直徑只有大約超立方體直徑的1/2，平均距離只有超立方體的2/3，其中具有Hamilton性是設(shè)計(jì)網(wǎng)絡(luò)時(shí)最基本也是最重要的要求之一，在文獻(xiàn)中，師海忠提出如下猜想：

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

師海忠進(jìn)一步給出一個(gè)更強(qiáng)的猜想：

猜想2：當(dāng)n 2k（k≥2）時(shí)，MQn是邊不交的i（1≤i≤k）個(gè)Hamilton圈和n-2i個(gè)完美匹配的并；當(dāng)n=2k+l（k>1）時(shí)，MQn是邊不交的i（1≤i≤k）個(gè)Hamilton圈和n-2i個(gè)完美匹配的并。

當(dāng)i=k時(shí)，猜想2即為猜想1。

本文證明n=3，4，5時(shí)，Mobius立方體是Hamilton可分解的，即當(dāng)n=3，4，5時(shí)猜想l和猜想2是正確的，當(dāng)n 6；i=1，2時(shí)，猜想2是成立的。

本文其余結(jié)構(gòu)如下：第2節(jié)，概念及其基本性質(zhì)；第3節(jié)，MQn（n=3，4，5，6）的Hamilton分解；第4節(jié)，結(jié)束語(yǔ)。

1 概念及基本性質(zhì)

本文所考慮的圖都是有限的簡(jiǎn)單無(wú)向圖，也就是說(shuō)所考慮的無(wú)向圖都有有限的頂點(diǎn)集和邊集，并且既不包含環(huán)，也沒(méi)有兩條連接同一對(duì)頂點(diǎn)的邊。下面介紹文中用到的概念，記號(hào)以及一些基本性質(zhì)。

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

定義2圖G中一個(gè)點(diǎn)邊接續(xù)交替J葉J現(xiàn)的序列稱為圖G的一條途徑，其中和Vik分別稱為途徑w的起點(diǎn)和終點(diǎn)，w上其余頂點(diǎn)稱為中途點(diǎn)；圖G中邊不重復(fù)出現(xiàn)的途徑稱為跡，起點(diǎn)和終點(diǎn)相同的途徑稱為閉途徑，邊不重復(fù)出現(xiàn)的閉途徑稱為閉跡，中途點(diǎn)不重復(fù)出現(xiàn)的閉跡稱為圈；經(jīng)過(guò)圖G的每個(gè)頂點(diǎn)一次的圈稱為一個(gè)Hamilton圈，記為HC。

定義3設(shè)G是一個(gè)圖，由G中一些不相鄰的邊組成的集合M稱為G的一個(gè)匹配，對(duì)匹配M中每條邊e=uv，其兩端點(diǎn)u和v被稱為匹配M所匹配，而u和v都稱為是M飽和的。如果圖G中每個(gè)頂點(diǎn)都是M飽和的，則稱M是G的完美匹配。圖G的含邊數(shù)最多的匹配稱為G的最大匹配，可見(jiàn)圖G的完美匹配也是它的最大匹配。

定義4n維Mobius立方體，記為且MQn是無(wú)向圖，它的頂點(diǎn)集與超立方體Qn一樣，頂點(diǎn)X=X1X2.…Xn連到另外n個(gè)頂點(diǎn)Yi（1≤i≤n）

x與Yi之間是否有邊確定，于是，當(dāng)xo=0時(shí)，該網(wǎng)絡(luò)稱為O-Mobius立方體；當(dāng)Xo=1時(shí)，該網(wǎng)絡(luò)稱為l-Mobius立方體，分別表示為0- MQn和1-MQn。

定義5設(shè)G是正則圖，E（G）是G的邊集，我們稱G是Hamilton可分解的，如果

要么（a）d（G）=2k且E能被劃分成k個(gè)邊不交的Hamilton圈；

要么（b）d（G）=2k+1且E（G）能被劃分成k個(gè)邊不交的Hamilton圈和一個(gè)完美匹配。

MQn的主要性質(zhì)：

（a）MQn是n正則的，有個(gè)2n頂點(diǎn)和n2n-1條邊，MQ有連通度n；

（b）o-MQn有直徑有直徑平均距離滿足：

互連網(wǎng)絡(luò)在發(fā)生某些鏈接故障時(shí)，各處理器能否保持通信，是結(jié)構(gòu)設(shè)計(jì)中的一個(gè)重要問(wèn)題，其中路和圈的嵌入是衡量其性能的重要指標(biāo)，而Hamilton圈作為互連網(wǎng)絡(luò)中最長(zhǎng)的圈，引起設(shè)計(jì)者的很多關(guān)注。本節(jié)將證明MQn（n=3，4，5）是Hamilton可分解的，MQ6可分解成兩個(gè)邊不交的Hamilton圈和兩個(gè)完美匹配，從而找出MQn（n=3，4，5，6）相應(yīng)的Hamilton圈和相應(yīng)的完美匹配，具體見(jiàn)定理1-4。

定理l MQ3是一個(gè)Hamilton圈和一個(gè)完美匹配的并，即當(dāng)n=3時(shí)，猜想l和猜想2是正確的。

證明：如圖l，MQ3是3正則圖，共有8個(gè)頂點(diǎn)

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：

所以當(dāng)n=3時(shí)猜想l是正確的，猜想2中i=k=l即為猜想l，也是正確的，定理l得證。定理2（1）MQ4是兩個(gè)邊不交的Hamilton圈的并，即n=4時(shí)猜想l和/=k=2時(shí)猜想2是正確的；（2） MQ4是一個(gè)Hamilton圈和兩個(gè)完美匹配的并，即i=1時(shí)猜想2是正確的。

證明：如圖2，MQ4是4正則圖，共有16個(gè)頂點(diǎn)

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：

所以當(dāng)n=4時(shí)猜想l是正確的，當(dāng)i=k=2時(shí)猜想2即為猜想l，也是正確的，（1）成立；對(duì)于（2），由（1）的證明知MQ4中有兩個(gè)邊不交的Hamilton圈，對(duì)0-MQ4不妨取HC2：0000-0010--1010-1101--0101-0001--1001-1000--1111-1110--0110-0111--

0011-1011--1100-0100--0000；其中一連接的表示完美匹配l，--連接的表示完美匹配2，所以對(duì)0-MQ4，i=1時(shí)猜想2是正確的；同理可證1-MQ4，i=1時(shí)猜想2是正確的，（2）成立，定理2得證。

定理3（1） MQ5是兩個(gè)邊不交的Hamilton圈和一個(gè)完美匹配的并，即n=5時(shí)猜想l和i=k=2時(shí)猜想2是正確的；（2） MQs是一個(gè)Hamilton圈和三個(gè)完美匹配的并，即i=1時(shí)猜想2是正確的。

證明：如圖3，MQ5是5正則圖，共有32個(gè)頂點(diǎn)

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；

所以當(dāng)n=5時(shí)猜想l是正確的，當(dāng)i=k=2時(shí)猜想2即為猜想l，也是正確的，（1）成立。對(duì)于（2）利用定理2中（2）的證明方法可證（2）成立，定理3得證。

定理4（1）MQ6是兩個(gè)邊不交的Hamilton圈和兩個(gè)完美匹配的并，即對(duì)MQ6來(lái)說(shuō)，i=2時(shí)猜想2是正確的；（2） MQ6是一個(gè)Hamilton圈和四個(gè)完美匹配的并，即對(duì)于MQ6來(lái)說(shuō)，i=1時(shí)猜想2是正確的。

證明：如圖4，圖5，MQ6是6正則圖，共有64個(gè)頂點(diǎn)

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；

所以對(duì)于MQ6來(lái)說(shuō)，i=2時(shí)猜想2是正確的，即定理中（1）成立；利用定理2中（2）的證明方法可證（2）成立，定理4得證。3結(jié)束語(yǔ)

本文對(duì)n=3，4，5，6時(shí)，Mobius立方體網(wǎng)絡(luò)MQn，的Hamilton性進(jìn)行了研究，由文獻(xiàn)知MQn是Hamilton的。在這篇文章中證明了當(dāng)n=3，4，5時(shí)猜想l和猜想2是正確的，當(dāng)n= 6；i=1，2時(shí)猜想2是成立的。對(duì)于MQn（n≥7），我們可以找到一個(gè)Hamilton圈，對(duì)MQn，（n≥7），猜想l和猜想2是否成立還有待進(jìn)一步的研究。