最大独立集问题

最大独立集问题（maximum independent set problem）是在一个图中选出尽可能多的顶点，同时保证所选顶点之间没有边。若边表示两项任务不能同时执行，独立集就表示一组互不冲突的任务；“最大”要求数量最多，而不只是已经无法继续加入顶点。

冲突关系与可行选择

设 $G=(V,E)$ 是有限、无自环、无重边的无向图。集合 $I\subseteq V$ 为独立集，是指每条边 $\{u,v\}\in E$ 的两个端点不同时属于 $I$。最大独立集的大小记为 $$\alpha (G)=max\{|I|:I\subseteq V,I\text{ 为独立集}\}.$$ 有限图至少有空独立集，因此最大值存在。极大独立集则只要求不能再加入任何一个顶点；这里比较的是包含关系，未必比较了所有集合的大小。

例如五个顶点组成星形图，中心为 $0$，叶子为 $1,2,3,4$，只有边 $\{0,i\}$。选中心后，任何叶子都不能再选，所以 $\{0\}$ 是极大的；但四个叶子彼此不相邻，可以全部选择。任何包含中心的独立集只有一个顶点，任何不含中心的独立集至多包含四个叶子，故 $\alpha (G)=4$。

左侧选择已无法扩充，但右侧选择的数量更大。实心圆表示被选顶点。

取或不取一个顶点

记 $N(v)$ 为与 $v$ 相邻的顶点集合，$N[v]=N(v)\cup \{v\}$；$G-S$ 表示删去集合 $S$ 及其相关边后的诱导子图。对非空图任取顶点 $v$，有递推式 $$\alpha (G)=max\{\alpha (G-\{v\}),1+\alpha (G-N[v])\}.$$

证明。 一个独立集或者不含 $v$，或者含有 $v$。第一种情形正是 $G-\{v\}$ 中的独立集。第二种情形必须排除全部邻居；去掉 $v$ 后，剩余顶点构成 $G-N[v]$ 的独立集。反过来，这两个子图中的独立集分别直接使用、或加上 $v$，都得到原图的独立集。两类既穷尽可行解，又各自可达到对应的最优大小，故取两者最大值。

在星形图上以中心分支：不取中心留下四个孤立点，答案为四；取中心则删除全部五点，答案为 $1+0=1$。递推的边界是 $\alpha (\varnothing )=0$。每次都减少顶点数，因此可以用归纳法同时证明算法终止和返回值正确。

将每个顶点是否入选记作 $x_v\in \{0,1\}$，还能写成整数规划： $$max\sum _{v\in V}{x}_v,x_u+x_v\le 1(\{u,v\}\in E).$$ 每条约束恰好排除一对冲突选择。把二元限制改成 $0\le x_v\le 1$ 仅得到松弛；在三角形上，三个变量都取 $1/2$ 满足边约束，目标为 $3/2$，而真实最大独立集只有一个顶点。

与顶点覆盖的对应

集合 $I$ 为独立集，当且仅当补集 $V\setminus I$ 是顶点覆盖：没有边的两个端点都在 $I$，恰好意味着每条边至少一个端点在补集中。故若最小顶点覆盖大小为 $\tau (G)$，则 $$\alpha (G)+\tau (G)=|V|.$$ 这给出精确解之间的转换。它不把顶点覆盖的近似比例原样转换成独立集的近似比例，因为转换时做了减法。

一般图的独立集判定问题是 NP 完全问题；下面的枚举分支适合小图，并不提供多项式时间的一般解法。树、二分图等具有额外结构的情形可以使用专门算法，不能仅凭一般情形困难，就认定每个具体实例都难。

可运行的精确分支程序

下面的输入为顶点数 $0\le n\le 24$ 及端点编号在 $0,\dots ,n-1$ 内的边；自环被拒绝，重复边不影响结果。返回一个最大独立集的编号元组，不改写输入。程序用整数的二进制位表示当前剩余顶点，并记住已经求过的子问题。并列时保留“不取当前顶点”分支，结果确定。

Python 3

from functools import lru_cache

def maximum_independent_set(n, edges):
    if type(n) is not int or not 0 <= n <= 24:
        raise ValueError("require integer 0 <= n <= 24")
    neighbours = [0] * n
    for u, v in edges:
        if type(u) is not int or type(v) is not int:
            raise ValueError("vertex labels must be integers")
        if not (0 <= u < n and 0 <= v < n) or u == v:
            raise ValueError("require distinct vertices in range")
        neighbours[u] |= 1 << v
        neighbours[v] |= 1 << u

    @lru_cache(None)
    def solve(mask):
        if mask == 0:
            return 0
        bit = mask & -mask
        v = bit.bit_length() - 1
        skip = solve(mask & ~bit)
        take = bit | solve(mask & ~(bit | neighbours[v]))
        return take if take.bit_count() > skip.bit_count() else skip

    answer = solve((1 << n) - 1)
    return tuple(v for v in range(n) if answer & (1 << v))

star = [(0, 1), (0, 2), (0, 3), (0, 4)]
print(maximum_independent_set(5, star))  # (1, 2, 3, 4)
print(maximum_independent_set(0, []))    # ()

每个掩码对应一个诱导子图，最多有 $2^n$ 个掩码。按一个机器字能容纳当前掩码的计算约定，记忆化递推的最坏时间、空间均为 $O(2^n+n+|E|)$；空间还包括最多 $n$ 层递归。若不把整数位运算视作常数，还应计入随位数增长的成本。二十四只是教学实现的输入上限，不能保证所有该规模实例都轻松运行。

可自行核对变式：五点路径的边为 $01,12,23,34$，集合 $\{0,2,4\}$ 大小为三；边 $01$、$23$ 各限制至多选一个，剩余顶点 $4$ 至多再贡献一个，故三已是上界。程序返回的某个三点集合必须同时满足这两项检查：数量为三，且没有一条边的两个端点都被选中。