计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (34): 82-84.DOI: 10.3778/j.issn.1002-8331.2009.34.025

• 网络、通信、安全 • 上一篇    下一篇

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

孙小军1,刘三阳2,王志强3   

  1. 1.宝鸡文理学院 数学系,陕西 宝鸡 721013
    2.西安电子科技大学 理学院,西安 710071
    3.总装备部驻天水地区军事代表室,陕西 宝鸡 721006
  • 收稿日期:2009-07-06 修回日期:2009-08-14 出版日期:2009-12-01 发布日期:2009-12-01
  • 通讯作者: 孙小军

New algorithm for solving connectivity of networks

SUN Xiao-jun1,LIU San-yang2,WANG Zhi-qiang3   

  1. 1.Department of Mathematics,Baoji University of Arts & Science,Baoji,Shaanxi 721013,China
    2.School of Science,Xidian University,Xi’an 710071,China
    3.General Armament Department Military Representative Office in Tianshui Region,Baoji,Shaanxi 721006,China
  • Received:2009-07-06 Revised:2009-08-14 Online:2009-12-01 Published:2009-12-01
  • Contact: SUN Xiao-jun

摘要: 连通度是评价网络系统连通状况及抗毁性的重要指标,也是网络结构的重要特征。针对现有算法在求解网络连通度时需要将原有网络转化为容量网络或进行其他变换的不足,受交通网络瘫痪事例的启发,提出了一种求解网络连通度的新算法。该算法通过引入点影响度和网络影响度来刻画各顶点在网络中的重要程度,不仅能求解网络连通度,同时还可以确定网络的最小点割,算法步骤简单、易于实现。最后算法分析和仿真实验表明了新算法的有效性。

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

Abstract: 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.

Key words: networks, invulnerability, influence, minimum vertex-cut, connectivity

中图分类号: