计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2010年
26期
38-39
,共2页
毁度%单圈图%递归算法
燬度%單圈圖%遞歸算法
훼도%단권도%체귀산법
图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问题.将单圈图的毁度计算问题转化为树或圈的计算问题,从而提供了一个单圈图毁度的计算方法.
圖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問題.將單圈圖的燬度計算問題轉化為樹或圈的計算問題,從而提供瞭一箇單圈圖燬度的計算方法.
도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문제.장단권도적훼도계산문제전화위수혹권적계산문제,종이제공료일개단권도훼도적계산방법.
