n維超立方體Qn中邊不交的生成樹

高太平，陳荷花

（1.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006；2.山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，山西 太原 030006；3.太原大學(xué)外語師范學(xué)院，山西 太原 030012）

0 引言

并行計(jì)算機(jī)互連網(wǎng)絡(luò)是高性能計(jì)算機(jī)的研究重點(diǎn)之一。國(guó)內(nèi)外現(xiàn)已對(duì)一些主要的并行計(jì)算機(jī)互連網(wǎng)絡(luò)如Ring（環(huán)）、Tree（樹）、Mesh（網(wǎng)格）、Torus（環(huán)繞）、Petersen（彼特森圖）、Hypercube（超立方體）等進(jìn)行了深入研究，并根據(jù)它們的拓?fù)浣Y(jié)構(gòu)研制出了相應(yīng)的商用或研究用的并行計(jì)算機(jī)系統(tǒng)。由于超立方體互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)具有正則性、對(duì)稱性、短直徑性、可擴(kuò)展性、可嵌入性、強(qiáng)容錯(cuò)性等性質(zhì)，因此，一直深受研究者和應(yīng)用開發(fā)者的偏愛，是最為重要和最具吸引力的并行計(jì)算機(jī)互連網(wǎng)絡(luò)之一。近年來，不少學(xué)者已對(duì)它從不同方面進(jìn)行了深入研究。

2007年，R.Cahalant等研究了超立方體中生成多路徑問題［1］；2008年，P.Greger等研究了超立方體中路徑分解問題［2］；2009年，X－B.Chen研究了超立方體中 many－to－many邊不交路徑問題［3］；2010年，Di liu等研究了n維超立方體中many－to－many路徑覆蓋問題［4］。2013年，Xie－Bin Chen和Shinhaeng Jo等分別研究了正常超立方體和帶故障超立方體中配對(duì)many－to－many不相交路徑全覆蓋問題［5－6］。這些都是圍繞超立方體互連網(wǎng)絡(luò)中并行單播或組播路由問題所展開的理論研究，關(guān)于超立方體中并行廣播路由的理論問題研究較少。

本文主要討論超立方體互連網(wǎng)絡(luò)Qn中邊不交生成樹數(shù)量的上界和下界，為進(jìn)一步設(shè)計(jì)超立方體Qn中并行廣播路由算法提供理論依據(jù)。因此，本文對(duì)并行計(jì)算機(jī)互連網(wǎng)絡(luò)的研究與發(fā)展具有一定的理論意義和應(yīng)用價(jià)值。

1 預(yù)備知識(shí)

圖G是指一個(gè)有序的二元組（V（G），E（G）），其中V（G）是G的頂點(diǎn)集，V（G）中元素稱為G的頂點(diǎn)或者節(jié)點(diǎn)；E（G）稱為G的邊集，E（G）中的元素稱為G的邊。設(shè)G是無向圖，x∈V（G），EG（x）表示G中與x關(guān)聯(lián)的邊集；dG（x）＝｜EG（x）｜稱為節(jié)點(diǎn)x的度；若圖G中的每個(gè)節(jié)點(diǎn)的度都為k，則稱圖G為k正則的；在簡(jiǎn)單圖中，可以用節(jié)點(diǎn)序列P＝（v1，v2，…，vn）來表示路P，或簡(jiǎn)記為P（v1，vn），其中v1和vn稱為路P 的起點(diǎn)和終點(diǎn)，若v1＝vn，則稱P為圈；包含G中的每個(gè)節(jié)點(diǎn)的路稱為Hamilton路，包含G中的每個(gè)節(jié)點(diǎn)的圈稱為Hamilton圈，包含Hamilton圈的圖稱為Hamilton圖；設(shè)R為圖G的一個(gè)子圖，則稱G－E（R）為R的補(bǔ)圖，若V（R）＝V（G），則稱R為圖G 的生成子圖；圖G的連通分支數(shù)記為ω（G）；對(duì)圖G1，G2，記G1＋G2＝（V（G1）∪V（G2），E（G1）∪（E（G2））。文中未定義的記號(hào)和術(shù)語，請(qǐng)參見文獻(xiàn)［7］。

定義1 n維超立方體互連網(wǎng)絡(luò)Qn是一個(gè)簡(jiǎn)單無向圖，它由2n個(gè)節(jié)點(diǎn)和n·2n－1條邊構(gòu)成。每一個(gè)節(jié)點(diǎn)可由一個(gè)n位二進(jìn)制串xn－1xn－2…x0進(jìn)行編碼，節(jié)點(diǎn)間的連接規(guī)則為：當(dāng)且僅當(dāng)其中兩個(gè)節(jié)點(diǎn)的二進(jìn)制串恰有一位不同時(shí)，兩節(jié)點(diǎn)相連。

圖1給出了一個(gè)4維超立方體互連網(wǎng)絡(luò)Q4的拓?fù)浣Y(jié)構(gòu)，圖中有24＝16個(gè)節(jié)點(diǎn)和4×24－1＝32條邊，圖中還標(biāo)識(shí)出了節(jié)點(diǎn)的編碼（分別從0000到1111）。

由定義1易知，n維超立方體Qn也可由兩個(gè)n－1維超立方體連接而成，連接方法為：對(duì)u∈V（），v∈V（），uv∈E（Qn），當(dāng)且僅當(dāng)u＝0xn－2…x0，v＝1xn－2…x0。

下列圖2是4維超立方體Q4的一種同構(gòu)拓?fù)浣Y(jié)構(gòu)，它在證明過程中使用起來更為方便。

Fig.1 4－dimensional hypercube Q4圖1 4維超立方體Q4

Fig.2 A topological structure of the hypercube Q4圖2 超立方體Q4的一種同構(gòu)拓?fù)浣Y(jié)構(gòu)

為了敘述方便，我們記Hn（vo，v）為超立方體Qn中起點(diǎn)為vo，終點(diǎn)為v的Hamilton路，當(dāng)不關(guān)心終點(diǎn)時(shí)，也簡(jiǎn)記為 Hn（vo）。

定義2 若Qn中兩棵生成樹T1，T2具有相同的根節(jié)點(diǎn)，且E（T1）∩E（T2）＝φ，則稱T1，T2為超立方體Qn中兩棵邊不交的生成樹。記Γ（Qn）為超立方體Qn中以vo為根節(jié)點(diǎn)的全體邊不交生成樹的集合，或更具體地記為：

Γ（Qn，v0）＝｛Ti（v0）｜Ti（v0）為Qn中以v0為根節(jié)點(diǎn)的第i棵邊不交生成樹，i＝1，2…，k｝.為了證明我們的主要結(jié)果，還需下列引理：

引理1［8］當(dāng)n≥2時(shí)，超立方體Qn是Hamilton圖。

引理2［7］若ω（G）＝1，則圖G中一定存在生成樹。

2 主要結(jié)果

關(guān)于超立方體Qn中邊不交生成樹棵數(shù)的上界和下界，我們有下列兩個(gè)結(jié)果。

定理2 當(dāng)n≥4時(shí)，超立方體Qn中至少存在2棵邊不交的生成樹，即

為了證明定理2，先給出以下兩個(gè)斷言：

斷言1 超立方體Qn中存在以任意節(jié)點(diǎn)v0為起點(diǎn)的Hamilton路Hn（v0）。

證明 由引理1知，超立方體Qn中存在Hamilton圈，也就存在Hamilton路。在打開Hamilton圈時(shí)，可選擇節(jié)點(diǎn)v0為起點(diǎn)的Hamilton路。從而得到Hamilton路Hn（v0）。

注1：該Hamilton路Hn（v0）即可作為Qn中的一棵以v0為根節(jié)點(diǎn)的生成樹T1（v0）。

斷言2 當(dāng)n≥4時(shí)，超立方體Qn中Hamilton路Hn（v0）的補(bǔ)圖是連通的，即：

證明 用數(shù)學(xué)歸納法。

（1）當(dāng)n＝4時(shí)，Hamilton路H4（0000，0010）顯然是超立方體Q4中的一棵以0000為根節(jié)點(diǎn)的生成樹T1（v0）（見圖3），而 H4（0000，0010）在Q4中的補(bǔ)圖Q4－E（H4（v0））仍然連通（見圖4），即ω（Q4－E（H4（v0））＝1。可見結(jié)論對(duì)n＝4成立。

Fig.3 A Hamilton path H4（0000，0010）in Q4圖3 Q4中的一條 Hamilton路H4（0000，0010）

Fig.4 Complement of H4（0000，0010）in Q4圖4 H4（0000，0010）在Q4 中的補(bǔ)圖

（2）假設(shè)命題對(duì)n－1成立，即若Hn－1（v0）為n－1維超立方體Qn－1中一條以v0為起點(diǎn)的Hamilton路，則ω（Qn－1－E（Hn－1（v0）））＝1。

（3）下證命題對(duì)n成立。

設(shè)Hn－1（v0，v1）為超立方體Qn的n－1維子立方體中一條Hamilton路，Hn－1）為超立方體Qn的n－1維子立方體中與Hn－1（v0，v1）對(duì)應(yīng)的Hamilton路，不妨記

為Qn中的一條Hamilton路（如圖6中的虛線部分所示）。

下證Qn－E（Hn（v0））是連通的。

是連通的（如圖6中實(shí)線部分所示），因此Qn－E（Hn（v0））也是連通的，即

Fig.6 Illustration of the proving process for claim 2圖6 斷言2證明過程示意圖

定理2的證明 由斷言1可知，超立方體Qn中存在以任意節(jié)點(diǎn)v0為起點(diǎn)的Hamilton路Hn（v0），該Hamilton路Hn（v0）即可作為Qn中的一棵以v0為根節(jié)點(diǎn)的生成樹T1（v0）；由斷言2可知，ω（Qn－E（Hn（v0））＝1，即 H（v0）的補(bǔ)圖 Qn－E（Hn（v0））是連通的，再由引理2知，Qn－E（Hn（v0））中存在生成樹T2（v0）。由于 Hn（v0）與Qn－E（Hn（v0））互為補(bǔ)圖，因此，T1（v0）和T2（v0）即為超立方體Qn中2棵邊不交的生成樹。

3 總結(jié)與展望

本文主要討論了n維超立方體Qn中邊不交生成樹數(shù)量的上界和下界，證明了當(dāng)n≥4時(shí)，n維超立方體Qn中邊不交生成樹數(shù)量介于2和之間。這就保證了n維超立方體Qn中至少存在2棵邊不交生成樹，因而在n維超立方體Qn中至少可進(jìn)行雙任務(wù)并行廣播通信。由此可見，本文的研究結(jié)果為設(shè)計(jì)超立方體Qn中雙任務(wù)并行廣播路由算法提供了理論依據(jù)。如何設(shè)計(jì)快速有效的雙任務(wù)并行廣播路由算法，是我們進(jìn)一步要研究的課題。

另外，不難看出，隨著n的增大，n維超立方體Qn中邊不交生成樹的數(shù)量也會(huì)增多，從而｜Γ（Qn）｜的下界也會(huì)增大。｜Γ（Qn）｜與n的精確關(guān)系是什么，也有待進(jìn)一步研究。因?yàn)橹挥兄懒耍＃≦n）｜，才有可能設(shè)計(jì)出執(zhí)行｜Γ（Qn）｜（大于2）項(xiàng)任務(wù)的并行廣播路由算法。當(dāng)然，設(shè)計(jì)相應(yīng)的多任務(wù)并行廣播路由算法等相關(guān)內(nèi)容也有待進(jìn)一步研究。

［1］Cahalant R，Koubek V.Spanning Mult－paths in Hypercubes［J］.Discrete Math，2007，307：2053－2066.

［2］Greger P，Dvorak T.Path Partitions of Hypercubes［J］.Information Processing Letters，2008，108：402－406.

［3］Chen X B.Many－to－many Disjoint Paths in Faulty Hypercubes［J］.Information Sciences，2009，179：3110－3115.

［4］Liu Di，Li Jing.Many－to－many Path－covers in n－dimensional Hypercubes［J］.Information Processing Letters，2010，110：580－584.

［5］Chen Xie－bin.Paired Many－to－many Disjoint Path Covers of Hypercubes［J］.Information Sciences，2013，179：3110－3115.

［6］Jo Shinhaeng，Park Jung－Heum，Chwa Kyung－yong.Paired Many－to－many Disjoint Path Covers in Faulty Hypercubes［J］.Theoretical Computer Science，2013，10：1－24.

［7］徐俊明.圖論及其應(yīng)用［M］.合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2004.

［8］Saad Y，Schultz M H.Topological Properties of Hypercubes［J］.IEEE Transactions on Computers，1998，37（7）：867－872.