網(wǎng)絡(luò)系統(tǒng)最小割集的一種矩陣分解

1、2007年 4月 第 30卷 第 2期 北 京 郵 電 大 學(xué) 學(xué) 報 Journal of Beijing University of Posts and Telecommunications Apr. 2007Vol. 30No. 2 文章編號 :100725321(2007 0220123204網(wǎng)絡(luò)系統(tǒng)最小割集的一種矩陣分解 余良德 , 孫新利 , 彭亞會 (第二炮兵工程學(xué)院 103教研室 , 西安 710025 摘要 :為了尋求計算雙終端網(wǎng)絡(luò)系統(tǒng)最小割集更為簡明的方法 , , 形成了廣義聯(lián)絡(luò)矩陣 的概念 , 并基于此提出了一種矩陣分解算法 , . 同時 闡述了算法的理論原理及計算步驟

2、, 并給出了冗余節(jié)點 、 算例驗證了本理論的正 確性和適應(yīng)性 . 關(guān) 鍵 詞 :網(wǎng)絡(luò)可靠度 ; 最小割集 中圖分類號 :TP20211A Matrix Decomposition Algorithm for Enumerating All Minimal Cut 2Set of a N et work YU Liang 2de , SUN Xin 2li , PEN G Ya 2hui (103Department , The Second Artillery Engineering College , Xi an 710025, China Abstract :The definition

3、of adjacent matrix was extended in order to effectively enumerate all minimal cut 2set of a terminal network. And a matrix decomposition algorithm was then proposed. The algo 2rithm is based on recursive matrix decomposition and reduction. The theoretical rationale and opera 2tional rules are given.

4、 The judgment principles and reduction rules about redundant nodes and isomorphic graphs are presented. The examples given show correctness and applicability of the algorithm. K ey w ords :network reliability ; minimal cut 2set ; adjacent matrix 收稿日期 :2006204220 作者簡介 :余良德 (1981 , 男 , 博士生 , E 2mail :

5、yu -. 0 引 言 隨著社會和科學(xué)技術(shù)的不斷發(fā)展 , 網(wǎng)絡(luò)化已經(jīng) 成為一種趨勢 , 例如輸電網(wǎng)絡(luò) 、 集成電路網(wǎng)絡(luò) 、 交通 網(wǎng)絡(luò)等 , 因此 , 網(wǎng)絡(luò)可靠性的研究在分布式系統(tǒng)中的 作用與日俱增 1, 其計算方法已成為國內(nèi)外研究熱 點 , 并取得了許多研究成果 1210. 在眾多算法中 , 網(wǎng) 絡(luò)的最小路集起著十分重要的作用 , 其求法已有聯(lián) 絡(luò)矩陣 、 布爾行列式 、 深度優(yōu)先搜索 2等許多有 效算法 . 然而 , 在一些復(fù)雜網(wǎng)絡(luò)中 , 最小路集數(shù)目 繁多 , 導(dǎo)致計算量猛增 , 使其應(yīng)用受到限制 ; 相反 , 其最小割集數(shù)目相對較少 , 這就使得最小割集的應(yīng) 用成為必然 3. 例如對于

6、一個 2 100的網(wǎng)格網(wǎng) 絡(luò) , 它有 299個 最 小 路 集 , 而 僅 有 1萬 個 最 小 割集 1, 3. 針對有向或無向網(wǎng)絡(luò) , 已有一些求最小割集的 算法 . 文獻(xiàn) 1, 4提出了一種適用于有向網(wǎng)絡(luò)的迭 代算法 ; 文獻(xiàn) 3結(jié)合組合數(shù)學(xué)和布爾代數(shù)知識 , 對 網(wǎng)絡(luò)中元件間布爾運算的結(jié)果進(jìn)行組合 , 提出了一 種有序二叉決策圖 (OBDD 算法 , 該算法能直接得 到網(wǎng)絡(luò)最小割集的不交化形式 , 但計算過程比較復(fù) 雜 ; 文獻(xiàn) 5提出了一種蒙特卡羅估計算法 , 該算法 的效率取決于對已知壽命分布網(wǎng)絡(luò)元件的抽樣方 法 ; 文獻(xiàn) 7認(rèn)為文獻(xiàn) 10的算法最有效 , 該算法能 在線性時間內(nèi)

7、求取單個最小割 , 但求最小割集的時 間復(fù)雜度仍很大 . 上述算法各有優(yōu)點 , 但不具有普 遍適用性 , 對于求解一般意義的網(wǎng)絡(luò)最小割集不是 十分有效 . 本文基于矩陣?yán)碚?, 通過擴展定義和規(guī) 定運算規(guī)則 , 提出一種計算雙終端網(wǎng)絡(luò)系統(tǒng)最小割 集的矩陣分解算法 , 最后用實例驗證了該算法的有 效性及易于在計算機上實現(xiàn)的特點 . 1 算法原理 假設(shè) G (N , E N 和邊集合 E 組成的雙終端網(wǎng)絡(luò) , e i (i 1, 2, , m 表示 E 中的 m 個邊變量 , n i (i =1, 2, , n 表示 N 中的 n 個節(jié) 點變量 ; 規(guī)定 n 1為源點 s , n n 為匯點 t.

8、 X 表示 N 的子集 , E (X 表示 E 的子集且與 X 相對應(yīng) , 則 X 和 E (X 構(gòu) 成 了 G (N , E 的 1個 子 網(wǎng) 絡(luò) G (X , E (X , 簡記為 G. 如果存在 1條從節(jié)點 n i 指向節(jié)點 n j 的有向邊 e i = n i , n j , e i E (無向邊 可用 1對平行、 方向相反的有向邊替換 , 使 n i X 且 n j /X , 則稱 n j 與 G 相鄰 . 如果 E (X 中所有邊 的失效導(dǎo)致網(wǎng)絡(luò)中源點 s 和匯點 t 不連通 , 則 E (X 構(gòu)成了網(wǎng)絡(luò) G (N , E 的 1個割 , 如果不包含其 他割 , 則 E (X 就為

9、 1個最小割 . 假設(shè) S 和 T 為 N 的 2個不相交子集 , 且 s S 、 t T. 定義 E (S , T 為連接 S 和 T 的所有邊 , 如 果 E (S , T 中所有邊均失效 , 則 s 和 t 處于不連通 狀態(tài) , 從而 E (S , T 構(gòu)成了原網(wǎng)絡(luò)的 1個割 , 如果 不包含其他割 , 則 E (S , T 就為 1個最小割 . 此外 , 由于網(wǎng)絡(luò)中與 s 相連的所有邊組成了 1個最小割 , 因此 , 如果能找到 G (N , E 的 2個連通子網(wǎng)絡(luò) G 1和 G 2, 使 s G 1、 t G 2, 且任何一個與 G 1相鄰的 節(jié)點都在 G 2中 , 則 E (G 1

10、, G 2 為 1個最小割 . 如果 G 2不連通 , 則 G 2中含有冗余節(jié)點 , 可將該冗余節(jié) 點合并到 G 1中 , 形成新的 、 連通的 G 1和 G 2. 這就 是尋求最小割集的基本出發(fā)點 . 2 廣義聯(lián)絡(luò)矩陣分解算法 211 基本定義和運算規(guī)則 擴展傳統(tǒng)聯(lián)絡(luò)矩陣的定義 , 定義廣義聯(lián)絡(luò)矩陣 C =(c ij n n 為 c ij = e l n i 和 n j 之間有邊 e l 直接相連 , i j , l =1, 2, , m 0n i 和 n j 之間沒有邊直接相連 , i j n k 節(jié)點標(biāo)號 , i =j , k =1, 2, , n 式中 n e j =e i e j e

11、 i 0=e i 0 e j =e j 0 0=0 從傳統(tǒng)意義上講 , 除了源點 s 和匯點 t 外的任 一節(jié)點 , 如果僅與另一節(jié)點相連 , 則該節(jié)點是冗余 的 . 但在本算法中 , 根據(jù)模型原理 , 如果 G 2不連通 , 則 G 2中含有冗余節(jié)點 , 即如果 1個節(jié)點與 G 1相 鄰 , 且只能通過 G 1到達(dá) t , 則該節(jié)點是冗余的 ; 也即 在廣義聯(lián)絡(luò)矩陣及其子矩陣中 , 如果矩陣中的某一 行元素除節(jié)點標(biāo)記外 , 其余均為 0, 則該節(jié)點是冗余 的 . 如果矩陣中存在冗余節(jié)點 , 則該矩陣不產(chǎn)生最 小割 , 將冗余節(jié)點所在行和列的全部元素刪除 , 并將 該節(jié)點添加到 S 中 , 形

12、成新的子矩陣 . 此外 , 由于算法是逐步構(gòu)造子網(wǎng)絡(luò)的過程 , 因 此 , 在廣義聯(lián)絡(luò)矩陣分解的過程中可能會出現(xiàn)網(wǎng)絡(luò) 子圖同構(gòu) 325. 如果 2個矩陣中 S 所對應(yīng)的節(jié)點元 素一樣 , 則它們所表示的子圖是同構(gòu)的 , 即這 2個矩 陣輸出的最小割相同 . 為此 , 在算法過程中 , 對維數(shù) 相同的矩陣需要判斷是否存在子圖同構(gòu) , 以避免重 復(fù)運算 . 212 算法步驟 廣義聯(lián)絡(luò)矩陣有效地描述了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu) , 按照一定運算規(guī)則對其逐步分解能形成滿足模型的 子網(wǎng)絡(luò) , 同時輸出相應(yīng)的最小割 . 步驟 1 根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)寫出廣義聯(lián)絡(luò)矩 陣 C , 在 C 中 c 11構(gòu)成了節(jié)點子集 S 的

13、全部元素 , 合 并第 1行其他非 0元素 , 輸出網(wǎng)絡(luò)的 1個最小割 . 步驟 2 選取 C 第 1行中不為 0的非節(jié)點元 素 , 并標(biāo)記每個元素的節(jié)點標(biāo)號 . 如果第 1行中匯 點所在列的元素不為 0, 則不對其進(jìn)行處理 . 因為該 元素不為 0意味著源點和匯點之間有邊直接相連 , 如果對該邊進(jìn)行處理 , 則源點和匯點將出現(xiàn)在同一 421北 京 郵 電 大 學(xué) 學(xué) 報 第 30卷 個節(jié)點子集中 , 這顯然與算法原理不符 . 事實上 , 如 果源點和匯點之間有邊直接相連 , 則網(wǎng)絡(luò)的任意一 個最小割均包含該邊 . 步驟 3 任意選取一個符合第 2步條件的元 素 , 不妨設(shè)其節(jié)點標(biāo)號為 n k

14、 , 即 c ii =n k (i 1 , 將 c ii 合并到 c 11中 ; 同時將第 i 行中其余元素與第 1行 相應(yīng)元素進(jìn)行 運算 , 運算結(jié)果保存在第 1行相應(yīng) 位置 , 然后刪除第 i 行和第 j 列的所有元素 , 則原來 的 n n 矩陣成為 (n -1 (n -1 矩陣 C n k (C n k 表 示合并節(jié)點 n k 后所形成的子矩陣 . 判斷 C n k 中是 否有冗余節(jié)點 , 如果有 , 則刪除該節(jié)點 , 并轉(zhuǎn)步驟 6; 如果沒有 , 則合并矩陣 C n k 第 1 元素 , 輸出原網(wǎng)絡(luò)的 1 . 步驟 4 對步驟 20元素分別按照 步驟 3的方法進(jìn)行處理 . 步驟 5

15、對步驟 3所產(chǎn)生的子矩陣再重復(fù)步驟 2和步驟 3, 直到最后得到的矩陣是 1個二維矩陣為 止 , 即網(wǎng)絡(luò)中只剩源點和匯點 . 該二維矩陣的第 1行第 2列元素構(gòu)成 1個最小割 . 步驟 6 歸并前幾步產(chǎn)生的最小割 , 最終得到 原網(wǎng)絡(luò)的最小割集 . 綜上所述 , 廣義聯(lián)絡(luò)矩陣分解算法能產(chǎn)生網(wǎng)絡(luò) 的最小割集 . 該算法的本質(zhì)是在一定運算規(guī)則下的 矩陣分解 , 易于在計算機上實現(xiàn) . 衡量一個算法是 否有效的關(guān)鍵 , 除了其自身邏輯判斷的正確性外 , 算 法要求的存儲量和所需的運行時間也是十分重要的 2個尺度 , 這就是通常所說的算法的空間和時間復(fù) 雜度 . 根據(jù)算法原理和步驟可知 , 本文算法的

16、時間 復(fù)雜度為 O (m 、 空間復(fù)雜度為 O (n 2 , 為流出 源點的邊數(shù)目 , 顯然該算法為線形時間算法 , 這在很 大程 度 上 減 小 了 文 獻(xiàn) 10算 法 的 時 間 復(fù) 雜 度 O (m +n c st (c st 為網(wǎng)絡(luò)最小割的數(shù)目 . 一般而 言 , 網(wǎng)絡(luò)的聯(lián)絡(luò)矩陣為稀疏矩陣 , 因而大型網(wǎng)絡(luò)的聯(lián) 絡(luò)矩陣需要占用很大的內(nèi)存空間 327, 為解決這個 問題 , 可以嘗試用其他數(shù)據(jù)結(jié)構(gòu) , 如鏈表來存儲聯(lián)絡(luò) 矩陣 . 3 算例分析 利用矩陣分解算法 , 求解圖 1所示的網(wǎng)絡(luò)最小 割集 . 依定義 , 網(wǎng)絡(luò)的廣義聯(lián)絡(luò)矩陣 C 為 圖 1 含 5個節(jié)點 、 7條邊的網(wǎng)絡(luò) s (n

17、 1 n 2n 3n 4t (n 5 C s (n 1 n n 4 t (n 5 s 0e 10 0300 0n 3e 4e 7 00e 5n 4e 6 0000t 由矩陣 C 的第 1行即可輸出 1個最小割 e 1e 2. C 中第 1行不為 0的非節(jié)點元素有 e 1、 e 2, 與之 對應(yīng)的節(jié)點標(biāo)號分別為 n 2、 n 4, 分別按照算法步驟 3處理可得 C n 2 = s , n 2e 3e 10 0n 3e 4e 7 0e 5n 4e 6 000 C n 4 = s , n 4e 2e 5e 6 0n 2e 30 00n 3e 7 000 由 C n 2 和 C n 4 可分別輸出最小

18、割 e 1 e 3、 e 2e 5e 6. 繼續(xù)對 C n 2 和 C n 4 分解 , 可知 C n 2 n 4 和 C n 4 n 2 將出現(xiàn)同 構(gòu) , 分別得 C n 2 n 4 =C n 4 n 2 = s , n 2, n 4e 3e 5e 6 0n 3e 7 00t C n 2 n 3 = s , n 2, n 3e 1e 4e 7 0n 4e 6 00t C n 4 n 3 = s , n 3, n 4e 2e 6e 7 0n 20 00t 根據(jù)冗余節(jié)點的判斷規(guī)則 , C n 4 n 3 中的 n 2為冗 余節(jié)點 , 故 C n 4 n 3 不輸出最小割集 . 由 C n 2 n

19、 4 和 C n 2 n 3 分別輸出最小割集 e 3e 5e 6、 e 1e 4e 7. 對 C n 2 n 4 合并節(jié)點 n 3、 C n 2 n 3 合并節(jié)點 n 4、 C n 3 n 4 521第 2期 余良德等 :網(wǎng)絡(luò)系統(tǒng)最小割集的一種矩陣分解 合并節(jié)點 n 2, 將出現(xiàn)同構(gòu) , 結(jié)果為 C n 2 n 3 n 4 = s , n 2, n 3, n 4e 6e 7 0t 輸出最小割 e 6e 7. 至此 , 矩陣分解完畢 , 最后得到網(wǎng) 絡(luò)的最小割集為 e 1e 2、 e 1e 3、 e 6e 7、 e 2e 5e 6、 e 3e 5e 6、 e 1e 4e 7. 根據(jù)算法分析 ,

20、 運用本算法該算例至多在 m = 27=14步 內(nèi) 收 斂 , 而 文 獻(xiàn) 10算 法 要 在 (m +n c st =(5+7 6=72步內(nèi)才能收斂 , 這說明 了本算法的有效性 . 4 結(jié)束語 , 絡(luò)矩陣 , . 在定義了廣 義聯(lián)絡(luò)矩陣運算規(guī)則的基礎(chǔ)上提出了一種求網(wǎng)絡(luò)最 小割集的矩陣分解算法 , 算法規(guī)則的含義直觀明確 , 易于編程實現(xiàn) , 并至多可以在 m 步內(nèi)收斂 . 參考文獻(xiàn) : 1 Chang Yung 2Ruei , Lin Hung 2Y an , Chen Ing 2Y i. A cut based algorithm for reliability analysis of

21、terminal pair network using OBDD C Proceedings of the 27th An 2 nual International Computer S oftware and Application Conference. Washington :IEEE Computer S ociety , 2003:3682373. 2 孫新利 , 陸長捷 . 工程可靠性教程 M .北京 :國防工 業(yè)出版社 , 2005:49258. Sun Xinli , Lu Changjie. Reliability engineering M . Beijing :Natio

22、nal Defense Industrial Press , 2005:49258. 3 Lin Hung 2Y au , Kuo Sy 2Y en , Y eh Fu 2Min. Minimal cut 2set enumeration and network reliability evaluation by recursive merge and BDD C Proceedings of the Eighth IEEE International Symposium on Computers and Communication (ISCC 03 . Washington :IEEE Co

23、m 2 puter S ociety , 2003:134121346. 4 Shier D R , Whited D E. Iterative algorithms for genera 2 ting minimal cut 2set in directed graphs J.Networks , 1986, 16(4 :1332147. 5 Lin J , Monte Carlo simulation to system reliability C Reliability and Maintainability Sym 2 Houston :Univ of Houston , 1993:2462250. 武小悅 . 復(fù)雜關(guān)聯(lián)系統(tǒng)的可靠性建模與分析 D .長