用 1 种颜色对图表进行部分着色

Question

我刚刚开始阅读图论，并且正在阅读有关图着色的内容。我的脑海中浮现出这个问题：

我们必须仅用一种颜色对无向图（不完全）进行着色，以便使彩色节点的数量最大化。我们需要找到这个最大数量。我能够制定一种非循环图的方法：

我的方法：首先，我们将图划分为独立的组件，并对每个组件执行此操作。我们创建一个 dfs 树，并在遍历它时创建 2 个 dp 数组，以便根位于最后：

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表示有色。

但这对于循环图不起作用，因为我假设没有访问过的孩子是连接的。

有人可以指导我如何解决循环图的这个问题（而不是通过暴力）的正确方向吗？是否可以修改我的方法或者我们是否需要提出不同的方法？像为具有最少边缘的节点着色这样的贪婪方法会起作用吗？

Answer 1

这个问题也是NP-Hard问题，被称为最大独立集问题。

如果图中的每两个顶点都没有边，S<=V则称集合为独立集合。u,vS(u,v)

的最大尺寸S（即您正在寻找的数字）称为图的独立数，不幸的是找到它是NP-Hard。

因此，除非 P=NP，否则您的算法对于通用图会失败。

证明它相当简单，给定一个图G=(V,E)，创建互补图，G'=(V,E')其中(u,v)is inE'当且仅当(u,v)is NOT in E。

现在，给定一个图G，存在一个大小为 的团k当且仅当k中存在一个独立的大小集合，使用相同的顶点（因为如果 (u,v) 是独立集合的两个顶点，则在 中G'没有边(u,v)E'，根据定义， 中存在一条边E。对独立集中的所有顶点重复上述操作，您就得到了G) 中的一个团。

由于派系问题是 NP-Hard 问题，因此这一问题也是如此。