摘要
本文介绍简单连通图着色问题的一个近似算法,就是借助于图的一个最小支配集,将图划分成若干个子图,分别对这些子图着色,再合并起来,便得到整个问题的解。着重介绍了应用代数运算寻找图的一个最小支配集的算法。此外,本文还论证了该近似算法的渐近时间复杂性是 O(n^3)。
An approximate algorithm for colouring the simple connected graph is intro- duced.With the aid of the minimal governing set of the graph,the graph is di- vided into several subgraphs.These subgraphs are coloured separately and the merged into a whole.Thus the solution to the problem is obtained.The algorithm for seeking the minimal governing set by algebraic operation is emphatically des- cribed.In addition,the worst-case time complexity of the algorithm is proved to be O(n^3)。
