论文部分内容阅读
图G的毁度定义为r（G）=max{ω（G—X）-｜X｜—m（G—X）：X∈V（G），ω（G-X）〉1}，其中ω（G—X）表示G—X的连通分支数，m（G-X）表示G-X的最大连通分支的阶，此参数很好地刻画了网络图的脆弱性（见文[2]）。若G为一般图，其毁度的计算为NPC问题（见文[3]）。文章给出了树的毁度的一个递归算法。