用一种颜色对图形进行部分着色
Partially coloring a graph with 1 color
我刚开始阅读图论，并且正在阅读有关图着色的内容。这个问题突然出现在我的脑海中：
我们必须只用一种颜色为无向图（不完全）着色，以使着色节点的数量最大化。我们需要找到这个最大数量。我能够为非循环图制定一种方法：
我的方法：首先，我们将图形划分为独立的组件，并对每个组件执行此操作。我们创建一个 dfs 树并在遍历它时创建 2 个 dp 数组，以便 root 排在最后：
dp[0][u]=sum(dp[1][visited children])
dp[1][u]=sum(dp[0][visited children])
ans=max(dp[1][root],dp[0][root])
dp[0][i] , dp[1][i] are initialized to 0,1 respectively.
此处0表示未着色，1表示着色。
但这不适用于循环图，因为我假设没有访问过的子节点是连接的。
有人可以指导我如何解决循环图的这个问题（不是蛮力）吗？是否可以修改我的方法，或者我们是否需要想出不同的方法？像给边缘最少的节点着色这样的贪婪方法是否可行？
这个问题也是 NP-Hard，被称为 maximum independent set problem。
一个集合S<=V在图中被称为独立集合，如果对于S中的每两个顶点u,v，有无边(u,v).
S的最大尺寸（就是你要找的数）被称为图的独立数，不幸的是找到它是NP-Hard .
因此，除非 P=NP，否则您的算法无法用于通用图形。
证明它相当简单，给定一个图 G=(V,E)，创建互补图 G'=(V,E') 其中 (u,v) 在 E' 中当且仅当 (u,v) 不在 E.
中
现在，给定一个图 G，当且仅当 G' 中存在一个大小为 k 的独立集合时，才会有一个大小为 k 的团，使用相同的顶点（因为如果 (u,v) 是独立集的两个顶点，则 E' 中没有边 (u,v)，并且根据定义 E 中有边。重复对于独立集中的所有顶点，您在 G).
中得到了一个团
因为 clique problem 是 NP-Hard，所以这也是 NP-Hard。
我刚开始阅读图论，并且正在阅读有关图着色的内容。这个问题突然出现在我的脑海中：
我们必须只用一种颜色为无向图（不完全）着色，以使着色节点的数量最大化。我们需要找到这个最大数量。我能够为非循环图制定一种方法：
我的方法：首先，我们将图形划分为独立的组件，并对每个组件执行此操作。我们创建一个 dfs 树并在遍历它时创建 2 个 dp 数组，以便 root 排在最后：
dp[0][u]=sum(dp[1][visited children])
dp[1][u]=sum(dp[0][visited children])
ans=max(dp[1][root],dp[0][root])
dp[0][i] , dp[1][i] are initialized to 0,1 respectively.
此处0表示未着色，1表示着色。
但这不适用于循环图，因为我假设没有访问过的子节点是连接的。
有人可以指导我如何解决循环图的这个问题（不是蛮力）吗？是否可以修改我的方法，或者我们是否需要想出不同的方法？像给边缘最少的节点着色这样的贪婪方法是否可行？
这个问题也是 NP-Hard，被称为 maximum independent set problem。
一个集合S<=V在图中被称为独立集合，如果对于S中的每两个顶点u,v，有无边(u,v).
S的最大尺寸（就是你要找的数）被称为图的独立数，不幸的是找到它是NP-Hard .
因此，除非 P=NP，否则您的算法无法用于通用图形。
证明它相当简单，给定一个图 G=(V,E)，创建互补图 G'=(V,E') 其中 (u,v) 在 E' 中当且仅当 (u,v) 不在 E.
现在，给定一个图 G，当且仅当 G' 中存在一个大小为 k 的独立集合时，才会有一个大小为 k 的团，使用相同的顶点（因为如果 (u,v) 是独立集的两个顶点，则 E' 中没有边 (u,v)，并且根据定义 E 中有边。重复对于独立集中的所有顶点，您在 G).
因为 clique problem 是 NP-Hard，所以这也是 NP-Hard。