[科普中国]-最大独立集

当且仅当对于U 中任意点u 和v所构成的边(u , v) 不是G 的一条边时，U 定义了一个空子图。当且仅当一个子集不被包含在一个更大的点集中时，该点集是图G 的一个独立集（independent set ），同时它也定义了图G 的空子图。最大独立集是具有最大尺寸的独立集。

独立集独立集是指图 G 中两两互不相邻的顶点构成的集合。任意有关图中团的性质都能很自然的转述成独立集的性质。一般而言，寻找图的最大团是 NP 困难的，从而寻找图的最大独立集也是 N-P 困难的。但是，对于二部图的情形，有多项式时间算法找出图的最大独立集。1

最大独立集问题如果U定义了G的一个完全子图，则它也定义了的一个空子图，反之亦然。所以在G的完备子图与的独立集之间有对应关系。特别的，G的一个最大完备子图定义了的一个最大独立集。

最大完备子图问题是指寻找图G的一个最大完备子图。类似地，最大独立集问题是指寻找图G的一个最大独立集。这两个问题都是NP-复杂问题。当用算法解决其中一个问题时，也就解决了另一个问题。例如，如果有一个求解最大完备子图问题的算法，则也能解决最大独立集问题，方法是首先计算所给图的补图，然后寻找补图的最大完备子图。2

算法思想定义一个图，图中每个顶点表示一个网组。当且仅当两个顶点对应的网组交叉时，它们之间有一条边。所以该图的一个最大独立集对应于非交叉网组的一个最大尺寸的子集。当网组有一个端点在路径顶端，而另一个在底端时，非交叉网组的最大尺寸的子集能在多项式时间（实际上是O(n2)）内用动态规划算法得到。当一个网组的端点可能在平面中的任意地方时，不可能有在多项式时间内找到非交叉网组的最大尺寸子集的算法。

首先选择一点为树根，再按照深度优先遍历得到遍历序列，按照所得序列的反向序列的顺序进行贪心，对于一个即不属于支配集也不与支配集中的点相连的点来说，如果他的父节点不属于最大独立集，将其父节点加入到独立集。2

具体实现采用链式前向星存储整棵树。整形数组newpos[i]表示深度优先遍历序列的第i个点是哪个点，now表示当前深度优先遍历序列已经有多少个点了。bool形数组visit[ ]用于深度优先遍历的判重，整形pre[i]表示点i的父节点编号, bool型数组s[i]如果为true,表示第i个点被覆盖， bool型数组set[i]如果为true,表示点i属于要求的点的集合。2

#include using namespace std;const int maxn = 1000;int pre[maxn];//存储父节点bool visit[maxn];//DFS标记数组int newpos[maxn];//遍历序列int now;int n, m;int head[maxn];//链式前向星struct Node {int to; int next;};Node edge[maxn]; void DFS(int x) { newpos[now ++] = x;//记录遍历序列 for(int k = head[x]; k != -1; k = edge[k].next) { if(!visit[ edge[k].to ]) { visit[ edge[k].to ] = true; pre[edge[k].to] = x;//记录父节点 DFS(edge[k].to); } }} int MVC() { bool s[maxn] = {0}; bool set[maxn] = {0}; int ans = 0; for(int i = n - 1; i >= 1; i--) {//逆序进行贪心,排除掉其根节点 int t = newpos[i]; if(!s[t] && !s[ pre[t] ]) {//如果当前节点和其父节点都不属于顶点覆盖集合 set[ pre[t] ] = true;//把其父节点加入到顶点覆盖集合 ans ++; //集合内顶点个数加1 s[t] = true;//标记当前节点被覆盖 s[ pre[t] ] = true;//标记其父节点被覆盖 } } return ans;} int main() { /* read Graph message*/ //建图 memset(visit, false, sizeof(visit));//初始化 now = 0; visit[1] = true; pre[1] = 1; DFS(1);//从第一个根节点开始寻找遍历序列 MDS(); return 0;}本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所