首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >Brélaz最小着色

问Brélaz最小着色
EN

Stack Overflow用户
提问于 2014-01-03 11:50:16
回答 1查看 1.9K关注 0票数 0

我已经完成了实现Brélaz算法,尝试用最少的颜色来着色一个图。事实上,到目前为止,我为它运行的所有测试都成功地用所需的最小颜色对它进行了着色。但是我已经读过好几次Brélaz,但是作为一个好的算法并不一定能实现图的最小着色。

有人能证实这一点,并给我一个图表的例子来证明吗?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2014-07-23 12:07:03

Brélaz是一种从70年代开始的顶点着色的启发式算法,也称为DSATUR (饱和度)。它特别擅长于Erd s-Rényi图(均匀随机),并在努力和紧密之间取得了很好的折衷。

然而,这只是一个启发,不能证明一个最优。

还可以在完整枚举方案中使用Brélaz,如[兰德尔-布朗72]中所述,但我想这不是您已经实现的。

与DSATUR相比,也有一些改进,主要是关于断线。

  1. 塞维尔1996
  2. 算法通行证( 2012年圣塞贡多 )
票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/20903003

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档