树的毁度的算法

摘要：

图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]).文章给出了树的毁度的一个递归算法.

关键词：毁度、树、递归算法

所属期刊栏目：42

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金10101021

在线出版日期：2006-10-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共2页

页码：52-53