团剖分问题的复杂性  

作　　者：吴举林[1] 

机构地区：[1]青岛大学数学系

出　　处：《应用数学》1990年第3期91-92,共2页Mathematica Applicata

摘　　要：本文考虑分离图和树的平方图上团剖分问题的复杂性.文中的图均为无向简单图,团是指完备子图.分离图是指其点集可剖分为一个团和一个独立集之并的图.图 G 的团剖分是一组边不相重的团,它们包含了 G 的每条边.成员最少的团剖分叫做最小团部分.这个最小成员数叫做团剖分数,记为 CP(G).图的团剖分问题是 NP—完全的.本文的一个结果是证明了分离图上的团剖分问题仍保持,NP—完全性.

关 键 词：无向简单图 团剖分问题 复杂性 

分 类 号：O157.5[理学—数学]