我刚开始读图论，正在读关于图的着色我突然想到这个问题：
我们必须用1色来着色我们的无向图（不是完全），使得着色节点的数目最大化。我们需要找到这个最大的数字。我能够为非循环图制定一种方法：
我的方法：首先我们将图划分为独立的组件，并对每个组件执行此操作。我们生成一个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表示着色。
但这对循环图不起作用，因为我假设没有访问的子图是连接的。
有人能指导我正确的方向，如何解决这个问题的循环图（不是暴力）是否可以修改我的方法，或者我们需要提出不同的方法像用最少的边着色一个节点这样的贪婪方法是否有效？
最佳答案
这个问题也是np难的，称为maximum independent set problem。
一个集合S<=V称为图中的独立集合，如果对于u,v中的每两个顶点S，没有边(u,v)。
（即你所寻找的数字）的最大大小称为图的独立数，不幸的是发现它是NP-难的。
因此，除非P=NP，否则对于一般用途的图，您的算法将失败。
证明它是相当简单的，给定一个图S，创建互补图G=(V,E)，其中G'=(V,E')在(u,v)当且仅当E'不在(u,v)中时。
现在，给定一个图，当且仅当E中有一个独立的大小集G时，存在一个大小为k的团，使用相同的顶点（因为如果（u，v）是两个独立的顶点集，那么k中没有边G'，并且根据定义(u,v)中有边。对独立集合中的所有顶点重复此操作，就会在E'中得到一个团。
因为clique problem是np难的，所以这也使得这一个成为np难。