| 基于三角环的顶点着色问题解法 |
| |
| 引用本文： | 龚卫华,王元珍.基于三角环的顶点着色问题解法[J].计算机科学,2005,32(4):77-78. |
| |
| 作者姓名： | 龚卫华 王元珍 |
| |
| 作者单位： | 华中科技大学计算机学院,武汉,430074;华中科技大学计算机学院,武汉,430074 |
| |
| 摘 要： | 图的着色问题是一个NP难问题，本文着重探讨无向图的顶点的三色问题，提出了用构造三角环的极大独立集方法判断并尝试给出顶点三色问题的可行解，解决了顶点三色的可满足性问题，克服了以前图遍历过程中的回溯问题，以及由此推论顶点四色和五色问题的极大独立集。
|
| 关 键 词： | NP完全问题 三角环 极大独立集 |
A Solution of Vertices Coloring Problem Based on Triangle Clique |
| |
| GONG Wei-Hua,WANG Yuan-Zhen.A Solution of Vertices Coloring Problem Based on Triangle Clique[J].Computer Science,2005,32(4):77-78. |
| |
| Authors: | GONG Wei-Hua WANG Yuan-Zhen |
| |
| Affiliation: | GONG Wei-Hua,WANG Yuan-Zhen School of Computer Science & Technology,HuaZhong University of Science and Technology,Wuhan 430074 |
| |
| Abstract: | The coloring problem of graph is a NP-hardness problem. This paper mainly discussed the vertices 3-color- ing problem of undirected graph. Proposed a method of using the maximum independent set of constructed triangle clique to judge and present the feasible resolution of the vertices problem. Solved the Satifiability of the vertices 3-col- oring problem. Overcomed the previously recursive problem during travelling graph. And deduced the maximum inde- pendent set of four-colorable and five-colorable problems from above. |
| |
| Keywords: | NP-completeness problem Triangle clique Maximum independent set |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
