一个计算无圈有向网络可靠度的有效算法

来源期刊：东北大学学报(自然科学版)2004年第11期

论文作者：孙艳蕊 张祥德

文章页码：1038 - 1041

关键词：点划分;极小割集;容斥原理;网络可靠度;算法;

摘    要：研究了无圈有向网络结点集合的两部分划分(点化分)与极小割集之间的关系·通过对网络结点集合的满足一定条件的两部分点划分,直接得到了网络的极小割集·根据点划分对应结点集合之间的包含关系,提出并证明了网络可靠度的容斥原理表达式中项的几个相消原则;在此基础上建立了一个基于割集的计算无圈有向网络可靠度的容斥原理公式及算法,算法直接给出了容斥原理公式中的所有不相消项;最后,通过例子说明了算法的有效性·