图的弱毁裂度与网络抗毁性

The Weak Rupture Degree of Graphs and the Network Invulnerability

图的弱毁裂度是刻画网络抗毁性的一个重要参数,它将破坏网络的难易程度和网络被破坏的严重程度相结合,并在剩余子图中考虑了边数的因素.为了揭示该参数与网络结构的内在关系,更加精确地量化网络抗毁性,本文首先研究并给出弱毁裂度的若干基本性质.在此基础上,用组合优化和类比的方法研究了该参数与图的若干重要参数之间的关系.这些关系以弱毁裂度的上、下界形式给出,本质上反映了弱毁裂度意义下的网络结构特征,即抗毁性.所得结果表明,弱毁裂度在刻画某些网络抗毁性上具有明显的优势.文中使用的方法对网络抗毁性分析研究具有重要借鉴作用,所得结论对网络抗毁性设计有一定推广与应用价值.

Weak rupture degree is an important parameter for measuring the invulnerability of networks.It combines the difficulty of destroying a network and the severity of the network being destroyed,and considers the number of edges in the remaining subgraph.In order to reveal the internal relationship between the weak rupture degree and the network structure,so as to accurately quantify networks’invulnerability,we initially give some basic properties of the weak rupture degree.Based on this,the relationship between this parameter and several important graphic parameters is studied by combinatorial optimization and analogy methods.These relationships are given in the form of the upper and lower bounds of weak rupture degree,which essentially reflect the characteristics of the network structure in the sense of the weak rupture degree,or invulnerability.These results show that weak rupture degree has obvious advantages in measuring the invulnerability of certain networks.The methods used in this paper have important guidence for network invulnerability analysis,and the obtained results have certain promotion and application value for network invulnerability design.