马 睿 朱建冲
(海军工程大学管理工程系 武汉 430033)
图论是一门很有实用价值的学科,近年来它受计算机科学蓬勃发展的刺激,发展极其迅速,应用范围不断拓广,已渗透到诸如运筹学、逻辑学、物理学、以及数学的其它分支中[1]。特别在运筹学中,在系统效能评估[2]、故障诊断[3]、系统可靠性分析[4]、路径优化[5]等方面均扮演着重要的角色。图的连通性是图论里的一个重要问题,许多人对图的连通性算法进行了研究。陆鸣盛[6]等提出一种改进的蒙特卡罗法对图的连通性进行分析,由于蒙特卡罗法是一种随机抽样算法,其精度取决于采样的数量,当网络规模较大结构复杂时,采样数量十分庞大,并且计算精度受到影响。厉海涛[7]等总结了贝叶斯网络推理的一些方法,黄晶[8]等创造性地将贝叶斯网络应用于路网失效的评估中,尹洪英[9]等使用贝叶斯网络对公路网脆弱性路段的识别进行了研究。上述基于贝叶斯网的连通性研究具有理论上的严格性和一致性,然而也存在许多不足,如处理多连通问题方法复杂,采用条件概率数据之间存在依赖性等。本文提出一种计算图连通性的精确方法,图上各条边的连通性是相互独立的,适用于多连通问题的分析。由于是精确计算,避免了近似计算中数量庞大的采样运算,并且可以直接得出各条边不连通时整个网络连通的概率以及灵敏度分析结果。
分析有向图的连通性,首先要找到连接指定起始点的最小路集合。……