計(jì)算K-終端網(wǎng)絡(luò)可靠度的兩種算法.pdf

1、本論文研究了計(jì)算機(jī)通訊網(wǎng)絡(luò)可靠度問題。主要討論了網(wǎng)絡(luò)可靠度的計(jì)算，提出了計(jì)算K-終端網(wǎng)絡(luò)可靠度的兩種新算法。 1有序二分決策圖(OBDD)是計(jì)算網(wǎng)絡(luò)可靠度最有效的工具之一。本文討論了由一個(gè)源點(diǎn)s到一個(gè)指定的頂點(diǎn)集合K的網(wǎng)絡(luò)可靠度問題。首先提出了網(wǎng)絡(luò)門限變量的兩個(gè)化簡原則及計(jì)算網(wǎng)絡(luò)K-樹和極小K-割的算法。然后，基于具有門限變量的布爾方程和有序二分決策圖方法(OBDD)，給出計(jì)算K-終端網(wǎng)絡(luò)可靠度算法。結(jié)果表明，這種算法是有效的。

2、該算法的特點(diǎn)是結(jié)構(gòu)清晰，運(yùn)算速度快，易于實(shí)現(xiàn)。這一算法改進(jìn)并推廣了Rauzy[77]提出的算法。 2邊化簡圖法是求兩終端網(wǎng)絡(luò)割集合的一種有效方法。本文推廣并改進(jìn)了Yung-RueiChang等人[82]的算法，提出一個(gè)計(jì)算K-終端網(wǎng)絡(luò)可靠度的割算法。該算法首先基于K-終端網(wǎng)絡(luò)G構(gòu)造出｜K｜個(gè)兩終端網(wǎng)絡(luò)，然后對于每個(gè)兩終端網(wǎng)絡(luò)，采用邊化簡圖法求兩終端網(wǎng)絡(luò)割集，最后，采用計(jì)算K-終端網(wǎng)絡(luò)可靠度的一個(gè)定理和有序二分決策圖法(OBDD)