DFS贪婪色数
DFS贪婪色数
提问于 2016-04-14 18:14:47
在我的学校里，我学到了计算任意图的色数是NP-完全的.我理解为什么greddy算法不能工作，但是DFS/贪心算法呢？其主要思想是对所有尚未着色的顶点进行DFS，对所有邻居进行最小颜色索引。
我想不出一个反例，这个问题让我大吃一惊。谢谢你所有的回答。
伪码
Chromatic(Vertex x){
for each neighbour y of vertex x
if color(y) = -1
color(y) <- minimum color over all the neighbours of y
if(y>=numColor) numColors++;
Chromatic(y);
}
Main(){
Set the color of all vertex equal -1
Take an arbitrary vertex u and set color(u) = 0
numColors = 1;
Chromatic(u);
print numColors;
}回答 2
Stack Overflow用户
回答已采纳
发布于 2016-04-14 18:38:22
答案是，有时你会有一个顶点，有2种颜色可用，作出错误的选择将导致一个问题，一个未定的时间后。
假设你有1到9的顶点，把它们画成一个圆。然后添加边，使下列内容成为真。
1，2，3形成一个三角形。3连接到4.4，5，6形成一个三角形。5，6，7形成一个三角形。6，7，8形成一个三角形。7，8，9组成一个三角形。8，9，1形成一个三角形。9，1，2形成一个三角形。
这是很容易用3种颜色着色的。但是一个深度优先的贪婪算法有一个2种颜色的选择，它可以给顶点4。做出错误的选择，你最终需要4种颜色，而不是3种颜色。
Stack Overflow用户
发布于 2016-04-14 18:40:06
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/36630881
复制相关文章
相似问题
腾讯云开发者
