基于三角环的顶点着色问题解法  

A Solution of Vertices Coloring Problem Based on Triangle Clique

作　　者：龚卫华[1] 王元珍[1] 

机构地区：[1]华中科技大学计算机学院,武汉430074

出　　处：《计算机科学》2005年第4期77-78,93,共3页Computer Science

摘　　要：图的着色问题是一个NP难问题,本文着重探讨无向图的顶点的三色问题,提出了用构造三角环的极大独立集方法判断并尝试给出顶点三色问题的可行解,解决了顶点三色的可满足性问题,克服了以前图遍历过程中的回溯问题,以及由此推论顶点四色和五色问题的极大独立集。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.

关 键 词：顶点着色 三角 极大独立集 题解 可满足性问题 NP难问题 着色问题 三色 无向图 可行解 图遍历 

分 类 号：O157.5[理学—数学] G633.6[理学—基础数学]