摘要
进一步研究发现,“图的色数问题研究”一文中的“算法”,实际上是构造图的着色方案的一种算法,也可能得到图的色数,也可能是一种近优值。为了完善该算法,在对不同的最大独立点集进行比较分析后,归纳出存在有多个最大独立点集时,从中选取色数分块的选优准则。并对最大独立点集的有关性质定理作了证明,从而使图的色数算法得以完善。
Through further research it was discovered that algorithm which was supplied in The color Number Problem Research of The Graph(that is reference 1)was actually an algo- rithm of constructing graph color scheme.It was possible to obtain color number of the graph,and maybe it was an approximate optimum value too.In order to improve algorithm, after analysis to different maxindependent node sets,optimum seeking standard of color number separate piece from several maxindependent node sets was induced.And this paper proved theorem to maxindependent node sets.So the color algorithm of the graph can be im- proved.
出处
《北京机械工业学院学报》
1998年第2期29-36,41,共8页
Journal of Beijing Institute of Machinery
关键词
点着色
点色数
独立点集
图论
node color
node color number
independent node set.
