计算机应用研究
計算機應用研究
계산궤응용연구
APPLICATION RESEARCH OF COMPUTERS
2011年
11期
4270-4273
,共4页
李振%孙新利%姬国勋%刘好杰%刘志勇
李振%孫新利%姬國勛%劉好傑%劉誌勇
리진%손신리%희국훈%류호걸%류지용
多状态网络%随机流量网络%d-最小割集%d-最小路集%可靠度
多狀態網絡%隨機流量網絡%d-最小割集%d-最小路集%可靠度
다상태망락%수궤류량망락%d-최소할집%d-최소로집%가고도
为寻求计算多状态网络系统可靠度更为简明的方法,提出了一种d-最小割、路集转换算法.该算法在已知d-最小割(路)集的基础上,基于逻辑代数理论,通过展开和之积表达式获得d-最小路(割)集,再基于两者中数量较少的一个运用容斥原理,得到网络可靠度.同时,分别利用容量未取最大和不为0的边及对应取值组成的集合对表示d-最小割(路),基于集合之间的隶属关系及将集合运算中正常的先取逆再合并的运算顺序变为先合并再取逆的思想,提出相关引理,简化算法.通过复杂度分析,证明算法有效.算例证明了算法的有效性和适用性.
為尋求計算多狀態網絡繫統可靠度更為簡明的方法,提齣瞭一種d-最小割、路集轉換算法.該算法在已知d-最小割(路)集的基礎上,基于邏輯代數理論,通過展開和之積錶達式穫得d-最小路(割)集,再基于兩者中數量較少的一箇運用容斥原理,得到網絡可靠度.同時,分彆利用容量未取最大和不為0的邊及對應取值組成的集閤對錶示d-最小割(路),基于集閤之間的隸屬關繫及將集閤運算中正常的先取逆再閤併的運算順序變為先閤併再取逆的思想,提齣相關引理,簡化算法.通過複雜度分析,證明算法有效.算例證明瞭算法的有效性和適用性.
위심구계산다상태망락계통가고도경위간명적방법,제출료일충d-최소할、로집전환산법.해산법재이지d-최소할(로)집적기출상,기우라집대수이론,통과전개화지적표체식획득d-최소로(할)집,재기우량자중수량교소적일개운용용척원리,득도망락가고도.동시,분별이용용량미취최대화불위0적변급대응취치조성적집합대표시d-최소할(로),기우집합지간적대속관계급장집합운산중정상적선취역재합병적운산순서변위선합병재취역적사상,제출상관인리,간화산법.통과복잡도분석,증명산법유효.산예증명료산법적유효성화괄용성.
