一种基于拓扑势值排序的DSATUR图顶点着色方法

摘要

本发明提出了一种基于拓扑势值排序的DSATUR图顶点着色方法，该方法能够在选择顶点着色时充分考虑顶点在整个图中的重要程度，相比DSATUR原始算法中考虑顶点度的方法，本发明每次选择当前饱和度最大的顶点进行着色，当出现多个饱和度最大的顶点时，则从中选择拓扑势最大的顶点，若又存在多个拓扑势最大的顶点，则按照字典顺序从中选择；本发明能够更恰当的选择顶点，优先选择图中最重要的顶点进行着色，在较少的搜索次数中取得最优解，对于大规模的图顶点着色问题，本发明提出的方法也能在指定的时间内达到更优解。