由网友(陪你沦陷)分享简介：我无法理解图着色的NP完全性。I am having trouble understanding the NP completeness of graph coloring.如果我认为一个贪婪的着色策略（ http://en.wikipedia.org/wiki/ Graph_coloring＃Greedy_col...

我无法理解图着色的NP完全性。

I am having trouble understanding the NP completeness of graph coloring.

如果我认为一个贪婪的着色策略（ http://en.wikipedia.org/wiki/ Graph_coloring＃Greedy_coloring ）与DFS，然后我似乎能够以最佳彩色图形。谁能帮我一个反例？

If I assume a greedy coloring strategy (http://en.wikipedia.org/wiki/Graph_coloring#Greedy_coloring) with DFS, then I seem to be able to color graphs optimally. Could anyone help me with a counter example?

需要明确的是，让所有节点进行着色-1。颜色开始节点1.继续在DFS遍历着色与尚未分配给它的邻居的最小整数的每个节点。当将这种无法以最佳彩色图？

To be clear, let all nodes be colored -1. Color the start node 1. Proceed in a DFS traversal coloring every node with the minimum integer that is not already assigned to its neighbors. When would this fail to optimally color the graph?

推荐答案

DFS贪婪的色彩肯定会在一些图表失败。拿出一个反例的方法是尝试写一个证明，DFS将色彩最优化。证明你不能完全得到工作的部分是用于提示想出一个反例。

DFS greedy coloring will certainly fail on some graphs. The way to come up with a counterexample is to try to write a proof that DFS will color optimally. The part of the proof that you can't quite get to work is the hint for coming up with a counterexample.