多狀態(tài)網(wǎng)絡(luò)可靠度的d-最小割(路)集轉(zhuǎn)換算法

摘要：為尋求計(jì)算多狀態(tài)網(wǎng)絡(luò)系統(tǒng)可靠度更為簡(jiǎn)明的方法，提出了一種d－最小割、路集轉(zhuǎn)換算法。該算法在已知d－最小割(路)集的基礎(chǔ)上，基于邏輯代數(shù)理論，通過(guò)展開(kāi)和之積表達(dá)式獲得d一最小路(割)集，再基于兩者中數(shù)量較少的一個(gè)運(yùn)用容斥原理，得到網(wǎng)絡(luò)可靠度。同時(shí)，分別利用容量未取最大和不為0的邊及對(duì)應(yīng)取值組成的集合對(duì)表示d－最小割(路)，基于集合之間的隸屬關(guān)系及將集合運(yùn)算中正常的先取逆再合并的運(yùn)算順序變?yōu)橄群喜⒃偃∧娴乃枷耄岢鱿嚓P(guān)引理，簡(jiǎn)化算法。通過(guò)復(fù)雜度分析，證明算法有效。算例證明了算法的有效性和適用性。

關(guān)鍵詞：多狀態(tài)網(wǎng)絡(luò)；隨機(jī)流量網(wǎng)絡(luò)；d－最小割集；d－最小路集；可靠度

中圖分類(lèi)號(hào)：TP202.1；TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001—3695(2011)11—4270—04