单圈图毁度的一个算法

作者：李银奎

来源：计算机工程与应用, 2010, (26): 38-39.

• 毁度
• 单圈图
• 递归算法 the rupture degree
• unicycle graphs
• recursive algorithm

图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的最大连通分支的阶。对于一般图G,其毁度的计算为NPC问题。将单圈图的毁度计算问题转化为树或圈的计算问题,从而提供了一个单圈图毁度的计算方法。

• 单位
  青海民族大学