独立集：在图G=(V, E)中存在子集V'∈V，任意u，v∈V'，(u, v)∉E（或图G的任意边至多有一个端点在计划V'中），集合V'就是图G的一个独立集。这样的最大集合V'称图G的最大独立集。独立集的大小为这样的点个数。
独立集问题的NPC证明
Ⅰ. 3-SAT ≤p Independent Set
已知3-SAT是一个NP难问题，可在多项式时间内将3-SAT归约到独立集问题，那么说明独立集问题也是一个NP难问题。需要证明，给定的一个有k个句子的3-SAT问题实例Ф，构造一个图，当且仅当Ф被满足时，该图具有大小为k的独立集。
第一步 构造一个3-SAT问题的实例
这里构造了3个句子（k=3），每个句子包含三个变量的是/非形式。
第二步 构造图
- 每个句子由三个相连的顶点表示
-
连接每个变量的是和非取值，如x1和!x1
根据3-SAT实例构造独立集问题的图
Claim: G具有大小为k的独立集，当且仅当Ф被满足。（Ф有k个句子）
第三步 证明
规约的正确性，需双向证明，即独立集存在，则Ф被满足；Ф被满足，则独立集存在。
=>
图G存在大小为k的独立集，那么各三角形中必然有一点在独立集中（三角形内的点均相邻，不独立）；
将这k个点（变量）的值设为true，那么其余所有点的取值均可确定下来；
因为这k个点在k个不同的句子中，则Ф能被满足，得证。
<=
Ф被满足，在k个句子中选取三个变量设为true，它们对应图G中k个三角形中的k个点；
这k个点刚好构成图G大小为k的独立集（因为互反的变量不会同时为true，即不会同时在k个点中），得证。
Ⅱ. Vertex Cover ≡p Independent Set
Vertex cover(点覆盖)：在图G=(V, E)中存在子集V'∈V，任意边（u,v）∈E，有u∈V或v∈U（图G中的任一边至少有一个端点在集合V'中），则集合V'就是图G的一个点覆盖。这样的最小集合V'称图G的最小点覆盖。
证明
S是图G=(V, E)的独立集，当且仅当V-S是一个点覆盖。（独立集和点覆盖互为补集）
=>
S是图G的任一独立集
则任意边(u,v)∈E，有u ∉ S或v ∉ S；那么u∈V-S或v∈V-S
所以图的任意边至少有一个端点在集合V-S中，集合V-S是一个点覆盖
<=
V-S是图G的任一点覆盖
则任意边(u,v)∈E，有u∈V-S或v∈V-S；那么u ∉ S或v ∉ S
所以图的任意边至少有一个端点不在集合S中，集合S是一个独立集
得证。
独立集问题和团问题
团：在图G=(V, E)中存在子集V''∈V，任意u，v∈V''，(u, v)∈E，集合V''就是图G的一个团（即完全子图）。这样的最大集合V''，称图G的最大团，点的个数即团的大小。
在一个图G(V, E)中，若存在最大独立集V'，则最大团是最大独立集的补集V-V'。
因此，可以用同样的方法证明团问题也是一个NP难问题，根据3-SAT构造的图是上图的补图。
Claim: G包含一个规模为k的团，当且仅当Ф是可满足的。
根据3-SAT构造团问题的图
Independent Set ≤p Clique
图G=(V, E)中存在独立集S，当且仅当在G的补图G'=(V, E')中，S是一个团。（补图：点不变，边取补）
=>
图G中有独立集S，则任意u, v∈S，有(u, v) ∉ E;
那么(u, v)∈E'，即在图G'，S集合中任意两点均有相连的边；所以S是图G'的团。
<=
图G'中有团S，则任意u, v∈S，有(u, v)∈E'；
那么(u, v) ∉ E，即在图G，S集合中任意两点均不相连；所以S是图G的独立集。
Q
等价问题（≡p）是如何证明的
网友评论