论文部分内容阅读
图G的毁度定义为r（G）=max{w（G—X）-｜X｜-m（G—X）X∪→V（G），w（G—X）〉1}，其中w（G—X）表示G—X的连通分支数，m（G—X）表示G—X的最大连通分支的阶。对于一般图G，其毁度的计算为NPC问题。将单圈图的毁度计算问题转化为树或圈的计算问题，从而提供了一个单圈图毁度的计算方法。