Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (26): 38-39.DOI: 10.3778/j.issn.1002-8331.2010.26.013
• 研究、探讨 • Previous Articles Next Articles
LI Yin-kui
Received:
Revised:
Online:
Published:
Contact:
李银奎
通讯作者:
Abstract: The rupture degree of a noncomplete connected graph G is defined as r(G)=max{ω(G-X)-|X|-m(G-X):X?V(G),ω(G-X)>1},where ω(G-X) is the number of components of G-Xand[m(G-X) is the order of a largest component of G-X.As to the complete graph，its rupture degree is defined as n.An algorithm for computing the rupture degree of unicycle graphs is presented.
Key words: 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问题。将单圈图的毁度计算问题转化为树或圈的计算问题，从而提供了一个单圈图毁度的计算方法。
关键词: 毁度, 单圈图, 递归算法
CLC Number:
O157.5
LI Yin-kui. Algorithm for computing rupture degree of unicycle graphs[J]. Computer Engineering and Applications, 2010, 46(26): 38-39.
李银奎. 单圈图毁度的一个算法[J]. 计算机工程与应用, 2010, 46(26): 38-39.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://cea.ceaj.org/EN/10.3778/j.issn.1002-8331.2010.26.013
http://cea.ceaj.org/EN/Y2010/V46/I26/38
