求解网络连通度问题的新算法  

New algorithm for solving connectivity of networks

作　　者：孙小军[1] 刘三阳[2] 王志强 

机构地区：[1]宝鸡文理学院数学系,陕西宝鸡721013 [2]西安电子科技大学理学院,西安710071 [3]总装备部驻天水地区军事代表室,陕西宝鸡721006

出　　处：《计算机工程与应用》2009年第34期82-84,共3页Computer Engineering and Applications

基　　金：国家自然科学基金No.60674108;No.60574075;宝鸡文理学院院级科研项目(No.ZK0829)~~

摘　　要：连通度是评价网络系统连通状况及抗毁性的重要指标,也是网络结构的重要特征。针对现有算法在求解网络连通度时需要将原有网络转化为容量网络或进行其他变换的不足,受交通网络瘫痪事例的启发,提出了一种求解网络连通度的新算法。该算法通过引入点影响度和网络影响度来刻画各顶点在网络中的重要程度,不仅能求解网络连通度,同时还可以确定网络的最小点割,算法步骤简单、易于实现。最后算法分析和仿真实验表明了新算法的有效性。Connectivity is not only an index to evaluate the status of network connectivity and survivability,but also an important feature of the network structure.Regarding the deficiency of the present algorithm for solving the connectivity of networks,which needs to change existing network to capacity network,a new algorithm is proposed in this paper,basing on inspiration of the paralysis of transportation network.By introducing two influencing degree-vector to stress the importance of the point in network,it shows that the new algorithm can not only solve network connectivity and determine the minimum vertex-cut,but also simple and easy to implement.Finally,the effectiveness is proved through simulation experiment and example.

关 键 词：网络 可靠性 影响度 最小点割 连通度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]