DFS 贪心色数

Question

我在学校学到计算任意图的色数是NP-Complete。我明白为什么 greddy 算法不起作用，但是 DFS/Greedy 算法呢？主要思想是对所有尚未着色的顶点进行 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;
}

Answer 1

答案是，有时您会有一个顶点有 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 种。

Answer 2

这是一个具体的反例：petersen graph。你的算法计算出 4，不管你从哪里开始（我认为），但图表的色指数是 3.

petersen 图是许多图问题贪婪尝试的经典反例，也是图论中的猜想。

DFS 贪心色数

DFS Greedy Chromatic Number

algorithm

graph

depth-first-search

greedy