|
|||||
|
|
| 团剖分问题的复杂性 | |
| 引用本文： | 吴举林.团剖分问题的复杂性[J].应用数学,1990(3):91-92. |
| 作者姓名： | 吴举林 |
| 作者单位： | 青岛大学数学系 |
| 摘 要： | 本文考虑分离图和树的平方图上团剖分问题的复杂性.文中的图均为无向简单图,团是指完备子图.分离图是指其点集可剖分为一个团和一个独立集之并的图.图 G 的团剖分是一组边不相重的团,它们包含了 G 的每条边.成员最少的团剖分叫做最小团部分.这个最小成员数叫做团剖分数,记为 CP(G).图的团剖分问题是 NP—完全的.本文的一个结果是证明了分离图上的团剖分问题仍保持,NP—完全性. |
| 关 键 词： | 无向简单图 团剖分问题 复杂性 |
| 本文献已被 CNKI 维普 等数据库收录！ | |