摘要
连通度是评价网络系统连通状况及抗毁性的重要指标,也是网络结构的重要特征。针对现有算法在求解网络连通度时需要将原有网络转化为容量网络或进行其他变换的不足,受交通网络瘫痪事例的启发,提出了一种求解网络连通度的新算法。该算法通过引入点影响度和网络影响度来刻画各顶点在网络中的重要程度,不仅能求解网络连通度,同时还可以确定网络的最小点割,算法步骤简单、易于实现。最后算法分析和仿真实验表明了新算法的有效性。
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.
出处
《计算机工程与应用》
CSCD
北大核心
2009年第34期82-84,共3页
Computer Engineering and Applications
基金
国家自然科学基金No.60674108
No.60574075
宝鸡文理学院院级科研项目(No.ZK0829)~~
关键词
网络
可靠性
影响度
最小点割
连通度
networks
invulnerability
influence
minimum vertex-cut
connectivity
