独立集（independent set)
图中每一条边至多有一个顶点在这个集合中，也就是说不会存在一条边包含的两个顶点都在这个集合中，即集合中不存在相邻的顶点。我们希望尽可能找到更多的这样的顶点。
点覆盖（vertex cover)
图中每一条边至少有一个顶点在这个集合中，也就是说用点去覆盖整个图的所有的边，当然，我们希望找到最少的点去覆盖所有的边。
image.png
独立集和点覆盖互补
观察图，发现互补
独立集 ==p 点覆盖
注意：p代表多项式时间等价
证明
先证明独立集能在多项式时间内推导出点覆盖
-S是任意一个独立集（图为G=（V,E)）
-S中任意一条边e(u,v)
-因为S是独立集，所以u,v不能同时在S中，假设u不在S中，那么u必在V-S中，同理假设v不在S中，则ｖ必在V-S中，也有可能u,v都在V-S中，反正总而言之，V-S至少包含u,v中的一个，是不是很熟悉？没错，这就是点覆盖的定义咯！所以V-S就是点覆盖。
反过来如果已知了点覆盖，在多项式时间内推导出独立集
-V-S是任意一个点覆盖
-假设在S中有两个顶点u,v
-那么u,v一定不能构成一条边，为什么？因为假设u,v能构成一条边，那么按照点覆盖的定义，u,v中至少有一个点应该在V-S这个集合中，而不是都在集合S 里面
-因此，S中的任意两个点不能构成一条边，即不存在相邻的顶点，即S是独立集。
最大团问题
从无向图的顶点集中选出k个并且k个顶点之间任意两点之间都相邻。最大的k就是最大团。
区分最大独立集：从无向图中的顶点中选出k个并且k个顶点之间互不相邻，最大的k就是最大独立集。
性质
无向图的最大团 ==p 该无向图补图的最大独立集（补图的意思就是有边变无边，无边变有边）
证明
正向证明
-S是任意一个团（G =（V，E））
-S中的任意两点Su,v能构成一条图中的边
-现在把u,v构成的边去掉
-那么u,v中任意两点都不能构成图中的边，即两两点不相邻，则此时的S是独立集
逆向证明
-S是独立集
-那么S中的任意两点u,v均不能构成图中的边
-若u,v加上边
-则S中任意的u,v之间都有边，则S是团
最大是怎么做到的
S是最大团，那么V-S中的任意两点均不存在边，取补图的时候，无边变有边，即任意点都有相邻点，那么V-S中的所有点都不可出现在独立集中。反过来，如果S是独立集，那么V-S中所有的点都至少有一条边与它相连（独立集和点覆盖互补），那么取补图的时候，V-S中所有点都不会有边，即任意两点都没有边，那么也就是说V-S中的点必不能出现在最大团的集合中。
网友评论