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

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

New algorithm for solving connectivity of networks

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.