| 图的导出森林2-划分 |
| |
| 引用本文： | 吴永旗,原晋江,赵永成.图的导出森林2-划分[J].数学研究,1996,29(1):1-6. |
| |
| 作者姓名： | 吴永旗 原晋江 赵永成 |
| |
| 作者单位： | 郑州高炮学院数学教研室，郑州大学数学系 |
| |
| 摘 要： | 对一个给定的简单图Ｇ，是否存在Ｖ（Ｇ）的一个２－划分（Ｖ１，Ｖ２）使得每个导出子图Ｇ［Ｖｉ］为森林？称该问题为导出森林２－划分问题．本文证明了对最大度为５的图该问题是ＮＰ－完全的，而对最大度≤４的图该问题多项式时间可解．
|
| 关 键 词： | 图，森林，划分，NP－完全 |
Partition a Graph into Two Induced Forests |
| |
| Wu Yongqi.Partition a Graph into Two Induced Forests[J].Journal of Mathematical Study,1996,29(1):1-6. |
| |
| Authors: | Wu Yongqi |
| |
| Abstract: | Is there a 2-partiton (V1,V2) of V(G) for a given simplc graph G such that each induced subgraph GVi] is a forest? ms problem is called induced forest 2-partition problem. This paper shows that this problem is NP-complete for graphs with maximum degree 5, and polynomially solvable for graphs with maximum degree at most 4. |
| |
| Keywords: | graph forest partition NP-complete |
| 本文献已被 CNKI 维普 等数据库收录！ |
