董張卓，羅 輝，齊 洋

(1.西安石油大學(xué) 電子工程學(xué)院，陜西 西安 710065； 2.西安科技大學(xué) 電氣與控制工程學(xué)院，陜西 西安 710054)

引 言

在電力[1-2]、通信、管網(wǎng)、公路網(wǎng)、醫(yī)療[3-4]等實(shí)際問題以及優(yōu)化設(shè)計(jì)中，通過(guò)一定方法將問題等效成一個(gè)平面圖，用不包括環(huán)路能達(dá)到每一個(gè)節(jié)點(diǎn)的連通圖，即對(duì)圖的生成樹的求解[5]，得到工程問題的可行解是一個(gè)典型的方法。

此類問題均可歸為針對(duì)無(wú)向圖和有向圖求生成樹的問題，求解該類問題目前有數(shù)種方法。第一種方法是BST算法[6]，用子樹集的概念從空集出發(fā)，按節(jié)點(diǎn)的編號(hào)順序，逐一向集合中添加至少在有向圖G的一顆以r為根的生成樹上的支路，直至得到該圖的某個(gè)生成樹為止。第二種方法是在G-M算法[7]的基礎(chǔ)上，從根出發(fā)，找到以r為根的圖G的每棵生成樹中都存在的支路e，確定搜索時(shí)間和搜索空間后，采用基于深度優(yōu)先搜索方法[8]得到生成樹，提高方法的運(yùn)行效率。第三種方法是給有向圖賦權(quán)后以權(quán)值為參考生成最小生成樹[1]。

以上算法僅適用于求解節(jié)點(diǎn)數(shù)和支路數(shù)較少的圖的生成樹，且隨著圖的規(guī)模增大，求解效率逐漸變低，同時(shí)，這些算法一般應(yīng)用于求解一棵生成樹，并不適合于求解一組生成樹。為此，本文提出一種基于簡(jiǎn)化圖的生成樹算法。為了減小問題的規(guī)模，首先定義簡(jiǎn)化規(guī)則將圖進(jìn)行簡(jiǎn)化，在簡(jiǎn)化圖的基礎(chǔ)上，提出一種隨機(jī)生成樹組求解算法得到生成樹的集合，即建立一種通過(guò)對(duì)原圖和對(duì)應(yīng)的樹圖通過(guò)輪盤賭的方式隨機(jī)選擇支路進(jìn)行遷移的算法，生成連通圖。通過(guò)多次應(yīng)用生成樹計(jì)算方法，生成不同的樹，得到生成樹組。

1 生成樹計(jì)算模型

定義1 大規(guī)模復(fù)雜連通圖GF∷=，其中BF為支路集合，NF為節(jié)點(diǎn)集合。

計(jì)算連通圖GF的生成樹組時(shí)，為了減小生成樹的計(jì)算量，首先對(duì)不涉及到生成樹的支路圖部分進(jìn)行簡(jiǎn)化得到簡(jiǎn)化圖，針對(duì)簡(jiǎn)化圖G計(jì)算得到的生成樹組加上簡(jiǎn)化的部分即為原連通圖的樹組。不失一般性，在圖的簡(jiǎn)化過(guò)程中，只給出簡(jiǎn)化方法；計(jì)算過(guò)程中，只針對(duì)簡(jiǎn)化圖進(jìn)行計(jì)算。

1.1 復(fù)雜連通圖的簡(jiǎn)化

為了減小復(fù)雜圖的規(guī)模，對(duì)其進(jìn)行簡(jiǎn)化得到簡(jiǎn)化圖。將圖中不涉及環(huán)路的輻射支路、節(jié)點(diǎn)以及直接串聯(lián)的支路進(jìn)行化簡(jiǎn)。為此給出以下概念的定義：

定義2 輻射通路，不包含在任何環(huán)路中的通路稱為輻射通路；

定義3 互斥支路，由度為2的節(jié)點(diǎn)連接的兩條支路稱為互斥支路。

定義4 互斥支路集，集合{bi|i=1,2，…，nb}，若bi和bi+1互斥，且bi+1和bi+2互斥，i=1,2，…，nb-2，稱集合為互斥支路集

輻射通路不存在于任何環(huán)路中，所以不參與生成樹的生成過(guò)程。同時(shí)由定義3知，互斥支路集在求取開環(huán)圖時(shí)最多只需打開一條支路。因此，將互斥支路進(jìn)行合并。故根據(jù)圖論的相關(guān)概念和上述定義，給出復(fù)雜圖的簡(jiǎn)化規(guī)則：①刪除復(fù)雜圖中所有輻射通路；②將復(fù)雜圖中的互斥支路集等效為一條支路。

1.2 簡(jiǎn)化圖生成樹算法

1.2.1 過(guò)渡圖的定義

定義5 簡(jiǎn)化圖，圖G為圖GF經(jīng)過(guò)簡(jiǎn)化后得到的圖：

G∷=。

(1)

其中：B為圖中的支路集合，B={bi|i=1,2，…，nb}，bi為圖中支路的編號(hào)，nb為圖中支路個(gè)數(shù)，N為圖中的節(jié)點(diǎn)集合，N={ni|i=1,2，…，nn}，ni為圖中節(jié)點(diǎn)的編號(hào)，nn為圖中節(jié)點(diǎn)個(gè)數(shù)。

定義6 生成樹圖GT，圖G的生成樹定義為含有圖G所有節(jié)點(diǎn)連通的無(wú)環(huán)路的一個(gè)子圖：

GT∷=。

(2)

其中：BT為圖中的支路集合，BT={bTi|i=1,2，…，nTb}，bTi為支路的編號(hào)，nTb為生成樹中支路個(gè)數(shù)；NT為圖中的節(jié)點(diǎn)集合NT={nTi|i=1,2，…，nTn}，nTi為節(jié)點(diǎn)的編號(hào)，nTn為生成樹節(jié)點(diǎn)個(gè)數(shù)。

定義7 過(guò)渡圖GB，生成樹圖過(guò)程中的一個(gè)臨時(shí)圖，初始時(shí)由簡(jiǎn)化圖G生成，完全等值于簡(jiǎn)化圖G，按照算法生成樹的過(guò)程中，逐漸遷出一些支路，完成生成樹計(jì)算后，圖GB中為圖G的連支，

GB∷=。

(3)

其中：BB為圖中的支路集合；NB為圖中的節(jié)點(diǎn)集合。

1.2.2 生成樹組樹支未選中概率

為保證生成樹組計(jì)算過(guò)程中樹的多樣性，以及考慮生成樹組在后期計(jì)算過(guò)程中效率降低問題，在第一次計(jì)算完成得到第一個(gè)生成樹后，對(duì)化簡(jiǎn)圖G以及過(guò)渡圖GB的支路加入選中作為樹支的計(jì)數(shù)值iNoc_T，即某一支路在一棵生成樹中出現(xiàn)一次，該支路的計(jì)數(shù)值iNoc_T+1，當(dāng)計(jì)算完成的樹的總數(shù)為iTn_T時(shí)，某條支路作為樹支的概率為

(4)

則支路未選中作為樹支的概率

Pn_t=1-Pt。

(5)

1.2.3 隨機(jī)生成樹計(jì)算原理

一顆隨機(jī)生成樹的計(jì)算過(guò)程分為3個(gè)部分，初始化部分，支路遷移循環(huán)部分、線索支路搜索部分。

初始化部分：過(guò)渡圖GB的生成、生成樹圖GT初始化以及在生成樹計(jì)算過(guò)程中記錄當(dāng)前支路和當(dāng)前處理節(jié)點(diǎn)的變量的定義。過(guò)渡圖GB初始化為原圖G，生成樹圖GT的支路集合和節(jié)點(diǎn)集合為空集。在圖GB中用輪盤賭算法隨機(jī)選擇的一條支路bk，取支路bk關(guān)聯(lián)的節(jié)點(diǎn)j。在圖GB中移除bk,圖GT中添加支路bk及支路兩端的節(jié)點(diǎn)i,j，即圖GT的BT={bk},NT={i,j},當(dāng)前節(jié)點(diǎn)C_n=j。

支路遷移循環(huán)部分：在圖GB以當(dāng)前節(jié)點(diǎn)C_n為線索，得到其關(guān)聯(lián)的支路集Bsel={bj|j=1,2,…,nb}，用輪盤賭算法隨機(jī)從支路集Bsel中選中一條支路bk，得到其對(duì)端節(jié)點(diǎn)j,如果j?NT,C_b=bk，C_n=j,圖GB中移除C_b=bk,圖GT中添加支路C_b、節(jié)點(diǎn)C_j，重開始支路遷移部分；否則，轉(zhuǎn)執(zhí)行線索支路搜索。

線索支路搜索部分：遍歷GB中支路，取支路bk的對(duì)應(yīng)節(jié)點(diǎn)i,j，如果i?NT∨j?NT成立，得到C_b=bk，C_n=i?NTi:j,轉(zhuǎn)支路遷移循環(huán),否則，計(jì)算完成。

在每次計(jì)算得到新的生成樹后，更新圖G中支路計(jì)數(shù)值iNoc_T以及生成樹數(shù)目iTn_T，并在下一次生成樹的計(jì)算過(guò)程中以Pn_t為基準(zhǔn)采用輪盤賭的方式對(duì)當(dāng)前節(jié)點(diǎn)的待選支路集中的支路進(jìn)行選擇。

1.2.4 隨機(jī)生成樹組的形成

為了得到一組完全的生成樹，需多次應(yīng)用上述隨機(jī)生成樹算法形成生成樹組。將得到的生成樹存入生成樹組時(shí)，將支路按序號(hào)從小到大排序，逐一對(duì)已有生成樹方案中的支路進(jìn)行對(duì)比，判別該生成樹是否與已有的方案相同，若相同，移除該方案并重新生成新的生成樹；若不同，則存入生成樹組。

2 隨機(jī)生成樹算法實(shí)現(xiàn)

以圖1為例，包含28個(gè)節(jié)點(diǎn)和32條支路，對(duì)隨機(jī)生成樹計(jì)算過(guò)程進(jìn)行說(shuō)明，給出隨機(jī)生成樹的計(jì)算方法。

圖1 復(fù)雜無(wú)向連通圖Fig.1 Complex undirected connected graph

2.1 簡(jiǎn)化過(guò)程

按照上述簡(jiǎn)化規(guī)則對(duì)該圖進(jìn)行簡(jiǎn)化得對(duì)應(yīng)的簡(jiǎn)化圖圖2。

圖2 復(fù)雜圖對(duì)應(yīng)的簡(jiǎn)化圖Fig.2 Simplified graph corresponding to complex graph

2.2 隨機(jī)生成樹計(jì)算過(guò)程

以圖2所示化簡(jiǎn)圖為例，進(jìn)行生成樹的計(jì)算過(guò)程說(shuō)明，過(guò)程如圖3所示。

圖3 生成樹生成過(guò)程圖Fig.3 Generation process of spanning tree

2.3 算法過(guò)程中節(jié)點(diǎn)與支路的數(shù)據(jù)表示

根據(jù)圖的特點(diǎn)，使用關(guān)系表的形式描述節(jié)點(diǎn)和支路的連接關(guān)系，見表1。

表1 節(jié)點(diǎn)與支路的連接關(guān)系表Tab.1 Connection relationship between nodes and branches

數(shù)組A分3個(gè)域：A1域?yàn)楣?jié)點(diǎn)編號(hào)，A2域、A3域分別為節(jié)點(diǎn)度和節(jié)點(diǎn)連接的支路的編號(hào)序列。

將等效后的支路與等效前的支路進(jìn)行對(duì)應(yīng)，對(duì)應(yīng)關(guān)系見表2。

表2 支路與互斥支路集的對(duì)應(yīng)關(guān)系表Tab.2 Correspondence between branch and mutually exclusive branch set

B的元素分2個(gè)域：B1域?yàn)楹?jiǎn)化圖中支路編號(hào)，B2域?yàn)閺?fù)雜圖中對(duì)應(yīng)的互斥支路組中的支路編號(hào)。表3即為復(fù)雜圖1中互斥支路集與簡(jiǎn)化圖2中支路的對(duì)應(yīng)關(guān)系表。

表3 支路與互斥支路組對(duì)應(yīng)表Tab.3 Correspondence between branches and mutually exclusive branch sets

在圖GB中的支路屬性中，加入一個(gè)選中為樹支的計(jì)數(shù)器，用來(lái)記錄支路選中為樹支的次數(shù)。生成樹組的存貯采用結(jié)構(gòu)見表4。

表4 生成樹的支路對(duì)應(yīng)關(guān)系表Tab.4 Correspondence among branches of spanning tree

數(shù)組C分3個(gè)域：C1域?yàn)闃涞木幪?hào)，C2域、C3域分別為支路的編號(hào)和樹支的編號(hào)序列。

2.4 隨機(jī)生成樹組計(jì)算過(guò)程

隨機(jī)生成樹組計(jì)算步驟及流程如圖4所示。

步驟1：初始化圖G中各支路的未選中計(jì)數(shù)值iNoc_T=0，樹個(gè)數(shù)iTn_T=0。

步驟2：初始化建立GT

(1)建立支路和節(jié)點(diǎn)集合BT={}，NT={}；建立當(dāng)前支路變量C_b,以及當(dāng)前節(jié)點(diǎn)變量C_n。

(2)隨機(jī)選取圖GB中支路BB中的一條支路bk，得到支路兩端的節(jié)點(diǎn)i,j，圖GT中添加支路bk，及支路兩端的節(jié)點(diǎn)，即圖GT的BT={bk},NT={i,j}。

(3)從GB中將支路bk移除，BB=BB-{bk}。

(4)C_b=bk，C_n=j。

步驟3：對(duì)當(dāng)前節(jié)點(diǎn)、以及當(dāng)前支路的處理。

(1)從圖GB中，得到當(dāng)前節(jié)點(diǎn)C_n連接的支

路集合Bsel,如果Bsel=?，轉(zhuǎn)(6)。

(2)基于Pn_t采用輪盤賭的方式從Bsel中選擇一條支路bk，(a)得到bk對(duì)應(yīng)另一側(cè)節(jié)點(diǎn)j,判斷節(jié)點(diǎn)j?NT，即不為GT的節(jié)點(diǎn)，轉(zhuǎn)(3)。否則Bsel=Bsel-{bk}并隨機(jī)選取一支路bk，為空轉(zhuǎn)(6)，否則轉(zhuǎn)(a)。

(3)C_b=bk，C_n=j。

(4)GT中加入bk，即BT=BT+bk}，NT=NT+j}。

(5)GB中移除支路bk，即BB=B-{bk}，轉(zhuǎn)(1)。

(6)遍歷GB中支路，取支路bk節(jié)點(diǎn)i,j，如果i?NT∨j?NT成立，得到C_b=bk，C_n=i?NTi:j,轉(zhuǎn)(1),否則，轉(zhuǎn)步驟3。

步驟4：輸出GB,GT中支路集合BB、BT。

圖4 隨機(jī)生成樹算法流程圖Fig.4 Flow chart of random spanning tree algorithm

步驟5：判別新生成的生成樹GT成與生成樹組中已有的生成樹是否相同，相同轉(zhuǎn)步驟1，不相同則存入生成樹組，同時(shí)圖G更新支路計(jì)數(shù)值iNoc_T++；樹個(gè)數(shù)iTn_T++。

步驟6：判斷是否達(dá)到設(shè)定循環(huán)次數(shù)，即生成樹的個(gè)數(shù)iTn_T是否達(dá)到設(shè)定的值，若達(dá)到則退出運(yùn)行，否則，轉(zhuǎn)步驟2。

3 算 例

在VS2015平臺(tái)下用VC++編制了提出的生成樹算法，分別用圖1中的復(fù)雜圖和圖7中的PG & E69節(jié)點(diǎn)電力系統(tǒng)圖為例對(duì)提出的算法進(jìn)行了驗(yàn)證。

3.1 算例1

對(duì)圖1中的復(fù)雜圖簡(jiǎn)化后得簡(jiǎn)化圖2，對(duì)簡(jiǎn)化圖2中的節(jié)點(diǎn)和支路進(jìn)行分類并處理，使用文中提出的方法共生成291個(gè)簡(jiǎn)化圖對(duì)應(yīng)生成樹圖，表5為圖的生成樹連支組(僅列出10組)；生成2 227個(gè)圖1對(duì)應(yīng)生成樹，表6為復(fù)雜圖的生成樹連支組(僅列出10組)。

表5 簡(jiǎn)化圖生成樹對(duì)應(yīng)連支組Tab.5 Connected branch group corresponding to spanning tree of simplified graph

從表5結(jié)果可以看出，本文中方法可以生成簡(jiǎn)化圖對(duì)應(yīng)的生成樹圖，方法正確有效。圖5為簡(jiǎn)化圖2斷開支路集{2,4,7,8,9}得到的一個(gè)生成樹圖。

圖5 簡(jiǎn)化圖2對(duì)應(yīng)的一種生成樹圖Fig.5 A spanning tree graph corresponding to simplified graph in Fig.2

針對(duì)圖5中的生成樹圖逆用簡(jiǎn)化規(guī)則，將簡(jiǎn)化圖中斷開的支路對(duì)應(yīng)的互斥支路集任一支路打開，并將刪除得輻射式支路重新添加即可得復(fù)雜圖對(duì)應(yīng)的生成樹圖。圖6為圖1中復(fù)雜圖斷開支路集{4,12,25,23,27}得到的一個(gè)生成樹圖，表6為復(fù)雜圖1對(duì)應(yīng)生成樹的結(jié)果。

圖6 復(fù)雜圖1對(duì)應(yīng)的一種生成樹圖Fig.6 A spanning tree graph corresponding to complex graph in Fig.1

表6 復(fù)雜圖1的生成樹對(duì)應(yīng)連支組Tab.6 Connected branch group corresponding to spanning tree of complex graph in Fig.1

從表6中結(jié)果和圖6可以看出，本文中方法可以生成復(fù)雜圖對(duì)應(yīng)的生成樹，方法正確有效。

3.2 算例2

圖7為PG & E69節(jié)點(diǎn)電力系統(tǒng)圖，包含支路73條，節(jié)點(diǎn)69個(gè)。

對(duì)圖7中的圖簡(jiǎn)化后進(jìn)行生成樹組的計(jì)算，共生成6 296組對(duì)應(yīng)的生成樹圖。圖7的生成樹連支組見表7(僅列出10組)。如圖8所示，列出圖7對(duì)應(yīng)的一種生成樹圖。

表7 69節(jié)點(diǎn)系統(tǒng)生成樹對(duì)應(yīng)連支組Tab.7 Connected branch groups corresponding to 69 node system spanning tree

圖8 PG & E69節(jié)點(diǎn)系統(tǒng)圖對(duì)應(yīng)生成樹圖Fig.8 Spanning tree graph corresponding to PG & E69 node system diagram

從表7中結(jié)果和圖8可以看出，本文中方法可以正確有效地生成重構(gòu)可行解圖。

3.3 方法性能對(duì)比

在相同的連通性判斷方法下，分別采用本文中方法和文獻(xiàn)[2]的BST算法對(duì)圖1和圖7生成500棵生成樹。平均生成一棵生成樹計(jì)算時(shí)間見表8。

表8 同一算例下不同方法平均計(jì)算時(shí)間對(duì)比Tab.8 Average calculation time of the same example using different methods

從表8可知：針對(duì)包含28個(gè)節(jié)點(diǎn)和32條支路的圖1，本文方法的平均計(jì)算時(shí)間為0.57 ms，文獻(xiàn)[2]中的BST算法平均計(jì)算時(shí)間為8.43 ms,本文方法計(jì)算效率為BST算法的14.79倍。針對(duì)包含支路73條，節(jié)點(diǎn)69個(gè)的PG & E69節(jié)點(diǎn)電力系統(tǒng)圖，本文方法的平均計(jì)算時(shí)間為1.46 ms，文獻(xiàn)[2]中的BST算法平均計(jì)算時(shí)間為34.90 ms,本文方法計(jì)算效率為BST算法的23.90倍。且隨著圖的規(guī)模增加，優(yōu)勢(shì)愈發(fā)明顯。

4 結(jié) 論

本文對(duì)復(fù)雜連通圖中得到生成樹的算法進(jìn)行了研究。將復(fù)雜圖按照簡(jiǎn)化規(guī)則簡(jiǎn)化后得到簡(jiǎn)化圖。在簡(jiǎn)化圖的基礎(chǔ)上，利用提出的生成樹算法得到對(duì)應(yīng)的生成樹圖，進(jìn)而生成復(fù)雜圖對(duì)應(yīng)的生成樹圖。算例表明，方法具有以下特點(diǎn)：

(1)該方法可正確生成復(fù)雜連通圖對(duì)應(yīng)的簡(jiǎn)化圖。

(2)該方法針對(duì)簡(jiǎn)化單圖后可正確地、快速地求其所有的對(duì)應(yīng)生成樹圖。

(3)針對(duì)簡(jiǎn)化圖對(duì)應(yīng)生成樹圖，可逆向使用簡(jiǎn)化規(guī)則得到復(fù)雜圖對(duì)應(yīng)的所有生成樹圖。

(4)該方法相比其他方法，能大幅度提高復(fù)雜圖對(duì)應(yīng)生成樹搜尋過(guò)程中的速度，且隨著連通圖規(guī)模的增大，該優(yōu)勢(shì)越發(fā)明顯。