我已经完成了实现Brélaz算法,尝试用最少的颜色来着色一个图。事实上,到目前为止,我为它运行的所有测试都成功地用所需的最小颜色对它进行了着色。但是我已经读过好几次Brélaz,但是作为一个好的算法并不一定能实现图的最小着色。
有人能证实这一点,并给我一个图表的例子来证明吗?
发布于 2014-07-23 12:07:03
Brélaz是一种从70年代开始的顶点着色的启发式算法,也称为DSATUR (饱和度)。它特别擅长于Erd s-Rényi图(均匀随机),并在努力和紧密之间取得了很好的折衷。
然而,这只是一个启发,不能证明一个最优。
还可以在完整枚举方案中使用Brélaz,如[兰德尔-布朗72]中所述,但我想这不是您已经实现的。
与DSATUR相比,也有一些改进,主要是关于断线。
https://stackoverflow.com/questions/20903003
复制相似问题