陳荷花

(太原學(xué)院,山西 太原 030024)

0 引言

樹是圖論中的一個(gè)基礎(chǔ)概念，它是所有圖中極為重要的一種，其中包含著圖中所有的節(jié)點(diǎn)，而權(quán)值和又最小的樹就稱為這個(gè)圖的最小生成樹，它是帶權(quán)無向連通圖的極小連通子圖.最小生成樹的理論和算法在信息的并行傳輸、安全分發(fā)，以及通信網(wǎng)絡(luò)構(gòu)建、高速路鋪設(shè)、配電網(wǎng)重構(gòu)等領(lǐng)域發(fā)揮著重要的作用.

2015年Costas Panagiotakisa，和Georgios Tziritas關(guān)于微聚集問題(microaggregation)提出了一個(gè)HTEP算法(the hierarchical tree equi-partition algorithm)，應(yīng)用于由數(shù)據(jù)定義圖表網(wǎng)絡(luò)，解決了在MST搜索空間的多元微聚集問題[1].M.Singh and L.C.Lau研究了最小生成樹有界度問題[2]，在成本最優(yōu)的情況下提出的一種多項(xiàng)式算法.P.Tewarie等人研究了最小生成樹在腦網(wǎng)絡(luò)分析中的應(yīng)用[3]，Jianshe Wu等人研究了最小生成樹在社區(qū)檢測(cè)中的應(yīng)用[4]，Xiebin Chen在折疊超立方體中給出了構(gòu)建最佳獨(dú)立生成樹算法[5].薛瑞等人針對(duì)賦權(quán)連通圖，提出了當(dāng)圖中存在權(quán)值相同的多條邊時(shí)，求解最小生成樹的改進(jìn)算法[6].

生成樹算法盡管已經(jīng)比較普遍，各位學(xué)者研究的角度各不相同，目前還找不到基于超立方體Qn節(jié)點(diǎn)編碼的算法.本文針對(duì)Qn的拓?fù)浣Y(jié)構(gòu)，基于其節(jié)點(diǎn)編碼的特點(diǎn)，利用避圈法，依據(jù)廣度優(yōu)先的策略，給出了Qn中一種新的尋找最小生成樹的算法.這一算法為超立方體中找最小生成樹打開了新的視野，也為Qn中設(shè)計(jì)相應(yīng)的路由算法提供了強(qiáng)有力的理論支撐.

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

給定一網(wǎng)絡(luò)圖G=(V，E，w),V是非空頂點(diǎn)集，E是邊集，w是每條邊的權(quán).一個(gè)n維超立方體互連網(wǎng)絡(luò)Qn是一個(gè)簡單無向連通圖，由2n個(gè)節(jié)點(diǎn)和n2n-1條邊構(gòu)成(詳細(xì)定義參見文獻(xiàn)1).由于文中研究內(nèi)容是在Qn中每條邊的權(quán)值相等時(shí)進(jìn)行的，因此圖中權(quán)參數(shù)w將不影響最小生成樹的構(gòu)成，于是我們記Qn=(V，E),其中V是Qn頂點(diǎn)集，E是Qn中不與V相交的邊集.

圖1是一個(gè)4維超立方體互連網(wǎng)絡(luò)Q4的拓?fù)浣Y(jié)構(gòu)，有24=16個(gè)節(jié)點(diǎn)和4×24-1=32條邊，從0000～1111是Q4中各個(gè)節(jié)點(diǎn)的編碼.

兩個(gè)恒等的圖可以用同一個(gè)圖形來表示，但不恒等的圖也可能具有實(shí)質(zhì)上相同的圖形，即兩圖同構(gòu)(用符號(hào)?來表示).當(dāng)圖G?G′,頂點(diǎn)s，t∈V(G),頂點(diǎn)s′，t′∈V(G′),且s′與s對(duì)應(yīng)，t′與t對(duì)應(yīng)，如果圖G中頂點(diǎn)s到t有路，那么圖G′中頂點(diǎn)s′到t′也一定有路，不僅長度相同，而且唯一對(duì)應(yīng)[10].一棵樹是一連通的無圈圖，當(dāng)圖G中相關(guān)的路連成樹T時(shí)，圖G′中必有一棵與之唯一對(duì)應(yīng)的樹T′生成.

為了研究的方便，文中借用了超立方體的同構(gòu)拓?fù)浣Y(jié)構(gòu).下面圖2是圖1所給4維超立方體Q4的一種同構(gòu)拓?fù)浣Y(jié)構(gòu).

圖1 4維超立方體Q4圖2 4維超立方體Q4的一種同構(gòu)拓?fù)浣Y(jié)構(gòu)

文中涉及的記號(hào)術(shù)語(下面未給出特別定義的)，請(qǐng)參見文獻(xiàn)[11].

當(dāng)節(jié)點(diǎn)s，t之間的漢明距離dH(s，t)=h時(shí)，si、ti中就會(huì)存在h個(gè)不同分量(h≤n).若Qn中兩節(jié)點(diǎn)s，t相鄰，則s，t之間的漢明距離等于1，即s，t相鄰當(dāng)且僅當(dāng)dH(s，t)=1.

定義2在n維超立方體Qn的所有節(jié)點(diǎn)中，到根節(jié)點(diǎn)s的漢明距離等于i的點(diǎn)的集合記為Vi,即Vi={v·dH(s，v)=i，v∈V(Qn)}.

定理[ 11 ]若T是一棵樹，則ε=v - 1(歸納法可證).即任一棵樹T中，邊數(shù)ε比頂點(diǎn)數(shù)v少一.

圖3 尋找Qn中最小生成樹的算法流程圖

2 基于Qn節(jié)點(diǎn)編碼的生成樹算法

目前，圖論中已經(jīng)有很多經(jīng)典算法可以構(gòu)造一個(gè)圖的最小生成樹，如Kruskal 算法、Prim 算法.但在超立方體中基于其節(jié)點(diǎn)編碼的最小生成樹算法還未有人研究，接下來本文將利用n維超立方體Qn的同構(gòu)拓?fù)浣Y(jié)構(gòu)，基于Qn節(jié)點(diǎn)編碼，利用避圈法，采用廣度優(yōu)先策略，給出Qn中尋找最小生成樹的算法.

2.1 算法思想

在一個(gè)n維超立方體Qn中，若要尋找以v0為根節(jié)點(diǎn)的一棵最小生成樹，首先根據(jù)定義2，可以得到Qn中的n個(gè)點(diǎn)集V1，…，Vn.然后從v0出發(fā)，在從Vi和Vi+1(i=1，2，…，i-1)選點(diǎn)添邊的過程中，對(duì)Vi中的每一個(gè)節(jié)點(diǎn)，要從其最高位開始，依次向Vi+1中的每個(gè)節(jié)點(diǎn)連邊.連邊遵循這樣的規(guī)則：取x∈Vi,y∈Vi+1,則xy∈E(T),當(dāng)且僅當(dāng)T∪xy不含圈.最終生成的最小生成樹共連2n-1條邊.

2.2 算法框圖

本算法的框圖見圖3.

2.3 算法步驟

算法 輸入：超立方體Qn,根節(jié)點(diǎn)v0=(00…0),T0=Φ,僅包含根節(jié)點(diǎn)的集合V0={v0},置：i=1，j=1，k=0.

①求Vi={v|dH(v0，v)=i，v∈V(Qn)}.

②記錄V1，V2，…，Vn.

③取ui∈Vk-1，vj∈Vk.

④若dH(ui，vj)≠1,置i= ：i+1,轉(zhuǎn)③；否則，進(jìn)入下一步.

⑤若Tk∪uivj含圈,置i= ：i+1,轉(zhuǎn)③；否則，進(jìn)入下一步.

⑥記錄Tk,置Tk= ：Tk∪uivj.

⑨若k

⑩輸出Tn,結(jié)束算法.

2.4 算法復(fù)雜度分析

算法質(zhì)量的優(yōu)劣會(huì)影響程序效率的高低，該算法完成一次總共需要執(zhí)行10步.在算法的執(zhí)行過程中，步驟①需要計(jì)算2n-1次，步驟④和⑤最多會(huì)各循環(huán)n次，而且每循環(huán)一次另需判斷n次，即這里共計(jì)算了n2+2n次，步驟⑦、⑧和⑨最多會(huì)各循環(huán)n次，于是又計(jì)算了n3次，這樣，該算法在最壞的情況下完成一次，總共會(huì)執(zhí)行2n-1+n3+n2+2n次運(yùn)算，因此該算法的時(shí)間復(fù)雜度為O(2n),其中n代表Qn中的節(jié)點(diǎn)數(shù).

3 實(shí)例驗(yàn)證

例 請(qǐng)?jiān)诔⒎襟wQ3和Q4中各找出一棵最小生成樹.

解 這里采用超立方體Q3和Q4的同構(gòu)拓?fù)浣Y(jié)構(gòu)，利用新提出的算法，找到了超立方體Q3和Q4中各自存在的一棵最小生成樹，見下圖4、圖5.

圖4 超立方體Q3中的一棵最小生成樹圖5 超立方體Q4中的一棵最小生成樹

4 結(jié)束語

超立方體互連網(wǎng)絡(luò)之所以長期受到各層次研究者們的喜愛，是因?yàn)樗陨碓S多獨(dú)特的優(yōu)良性質(zhì)吸引著大家.本文利用n維超立方體的正則性和高度對(duì)稱性，基于Qn節(jié)點(diǎn)編碼的特點(diǎn)，在Qn的同構(gòu)拓?fù)浣Y(jié)構(gòu)中，找到了一種新的最小生成樹算法，這為Qn中設(shè)計(jì)相應(yīng)路由算法提供了依據(jù)，為超立方體互連網(wǎng)絡(luò)的并行廣播路由算法打開了新的視角.但該算法的不足之處是它的時(shí)間復(fù)雜度為O(2n),不夠理想，有待進(jìn)一步優(yōu)化.