独立集与顶点覆盖：哨所选址的权衡

独立集与顶点覆盖：哨所选址的权衡

在一大片相互牵制的据点网络里，哪些位置可以同时驻军而互不接壤？又该在哪些路口设卡，才能用最少的哨所监视全部道路？两个问题看似风马牛，实则是一枚硬币的两面：前者求最大独立集（两两不邻的顶点最多取几个），后者求最小顶点覆盖（触到每条边的顶点最少取几个）。本章收尾攻坚的最后一节由它们担纲：本节讲清两者"补集互为答案"的对偶关系、与团问题及着色问题的家族谱系，给出精确与近似两套求解打法，并把第 7 章 König 定理的另一半收拢归档。

两个定义与一条互补定理

先立定义。独立集：顶点集的子集，内部任何两点不相邻；最大独立集是规模最大者，其规模记为独立数。顶点覆盖：顶点集的子集，每条边至少有一端落在其中；最小顶点覆盖是规模最小者。两者由一条一句话定理锁死：S 是独立集，当且仅当它的补集是顶点覆盖。两个方向各一行论证——若 S 独立，任何边的两端不能同时落在 S 外（否则该边内部两点都进了补集，与 S 独立矛盾），故补集触到每条边；反向同理。立刻得到规模等式：独立数加最小覆盖数等于顶点总数。求最大独立集与求最小顶点覆盖由此完全等价，解一个等于解两个。

再把家族谱系补齐两笔。其一，补图翻译：图 G 的独立集对应补图（边与 G 恰好互补的图）中的团（两两相邻的顶点集），故"G 的最大独立集"与"补图的最大团"是同一道题的两个名字。其二，着色打包：上一节说过每种颜色的内部是一个独立集，着色即"把顶点切成最少几个独立集"。至此，独立集、团、顶点覆盖、着色四个问题在谱系图上互相通达——而它们在一般图上都属于"精确求解极难"的一族，谱系的每条边都是一把归约的钥匙：任何一个被快速破解，全族同时崩塌。

 顶点集 V 的极值子集家族（n 为顶点总数）

   独立集 ──补集──→ 顶点覆盖       规模和恒为 n
      │                              │
      │ 取补图                        │ 取补图
      ▼                              ▼
    团 ←──(规模=n-覆盖数 的补集)──  独立集（补图上）

   着色 = 把 V 切成最少几个独立集（"打包出售"）
​

精确求解：从穷举到分支限界

小规模实例上，穷举是最诚实的起点——遍历顶点集的全部子集，检查独立性与覆盖性：

import itertools
import networkx as nx

def brute_mis(G):
    """穷举最大独立集（仅教学用，指数规模）"""
    best = []
    for k in range(len(G.nodes), 0, -1):
        for subset in itertools.combinations(G.nodes, k):
            if all(not G.has_edge(u, v) for u, v in itertools.combinations(subset, 2)):
                return list(subset)          # 从大到小，首个命中即最大
    return best

def cover_from_independent(G, ind):
    """独立集的补集即顶点覆盖（互补定理的代码显形）"""
    return [v for v in G.nodes if v not in set(ind)]

posts = nx.Graph([("路口甲","路口乙"),("路口乙","路口丙"),
                  ("路口丙","路口丁"),("路口丁","路口甲"),
                  ("路口甲","路口丙")])
ind = brute_mis(posts)
print("最大独立集:", ind, "| 对应最小覆盖:", cover_from_independent(posts, ind))
print("规模验证: 独立数", len(ind), "+ 覆盖数", len(posts.nodes) - len(ind),
      "=", len(posts.nodes))
​

穷举的代价是二倍的顶点数次方量级，二十来个顶点就到极限。实战的升级版是分支限界：选一个顶点 v 分两支——"要它"则删掉它与其邻居再递归（独立集里容不下邻居同存），"不要它"则直接删掉 v；配上"上界估计"（剩余顶点数封顶）与"下界估计"（已有规模加某个乐观余量）剪枝，中小图（数十顶点）能在可接受时间出精确解：

def branch_mis(G):
    """分支限界求最大独立集规模"""
    nodes = tuple(G.nodes)
    memo = {}
    def solve(fro):
        if not fro:
            return 0
        if fro in memo:
            return memo[fro]
        v = fro[0]
        nbrs = set(G[v]) & set(fro)
        take = 1 + solve(tuple(u for u in fro if u != v and u not in nbrs))
        skip = solve(fro[1:])
        memo[fro] = max(take, skip)
        return memo[fro]
    return solve(nodes)

print("分支限界独立数:", branch_mis(posts))
​

"要它"分支里那句"删掉自己与全部邻居"值得细看——它正是独立集约束的分支形态，与团问题的"只删自己"、覆盖问题的"边两端二选一"遥相呼应。分支限界的效率全看分支树被剪掉多少，而剪枝力度高度依赖图的密度：稀疏图上邻居多、删得快，往往瞬间收敛。

近似与特款：工程的两条出路

精确求解在一般图上无望，工程实践分两条路走。

第一条是近似算法。最小顶点覆盖有个教科书级的近似：任取一个极大匹配，把匹配里每条边的两端都收进覆盖。极大匹配触到的边已全覆盖（任何未触边可与匹配边组成更大匹配，与极大性矛盾），而最优覆盖每条匹配边至少要收一端，故近似解规模至多是最优的两倍——"两倍近似"由此得名，且证明五行写完。

def approx_cover(G):
    """两倍近似最小顶点覆盖：极大匹配两端全收"""
    cover = set()
    edges = list(G.edges())
    while edges:
        u, v = edges.pop()
        cover.update((u, v))                  # 收两端
        edges = [e for e in edges if u not in e and v not in e]
    return cover

print("近似覆盖:", sorted(approx_cover(posts)),
      "| 规模:", len(approx_cover(posts)))
​

第二条是特款特解。二分图上，第 7 章的 König 定理承诺"最大匹配数等于最小顶点覆盖数"——多项式时间精确可解，匈牙利算法跑完，最小覆盖从增广结构里直接读出（证明细节不再展开，但结论在此归档：二分图上，独立数 = 顶点总数 − 最大匹配数，一族极值问题全部速解）。一般图与二分图之间的复杂度鸿沟，正是这个问题家族最深刻的风景：同样的问题定义，换一个图类，命运天差地别。

def bipartite_min_cover(G):
    """二分图最小顶点覆盖：最大匹配 + 增广结构读出"""
    left = {v for v in G.nodes if G.nodes[v].get("bipartite") == 0}
    match_r = {}
    def try_aug(u, visited):
        for v in G[u]:
            if v in visited:
                continue
            visited.add(v)
            if v not in match_r or try_aug(match_r[v], visited):
                match_r[v] = u
                return True
        return False
    for u in left:
        try_aug(u, set())
    # 从未匹配的左顶点出发沿交替路标记可达集 Z：
    # 左侧任意边可走，右侧只沿匹配边回走（König 构造）
    unmatched = {u for u in left if u not in match_r.values()}
    Z, stack = set(unmatched), list(unmatched)
    while stack:
        u = stack.pop()
        for v in G[u]:                        # 左→右：任意边
            if v not in Z:
                Z.add(v)
                w = match_r.get(v)            # 右→左：仅匹配边
                if w is not None and w not in Z:
                    Z.add(w)
                    stack.append(w)
    left_part = {u for u in left if u not in Z}
    right_part = {v for v in G.nodes
                  if G.nodes[v].get("bipartite") == 1 and v in Z}
    return left_part | right_part

B = nx.Graph()
B.add_nodes_from(["任务甲","任务乙","任务丙"], bipartite=0)
B.add_nodes_from(["员一","员二"], bipartite=1)
B.add_edges_from([("任务甲","员一"),("任务甲","员二"),
                  ("任务乙","员二"),("任务丙","员一")])
print("二分图最小覆盖:", sorted(bipartite_min_cover(B), key=str))
​

König 构造的读法：从未匹配的左顶点沿交替路标记可达集，"左半未标记 + 右半已标记"恰是最小覆盖——这行构造把对偶定理从陈述变成了可执行的产出。

应用与复杂度侧写

应用侧的版图辽阔。设施选址：电台布点求独立集（同频干扰即相邻约束）；哨所布防求覆盖（每条道路须被监视）。编码理论：纠错码的最大码字集合可转译为特定图上的独立集。调度冲突：排课、排赛的"最多不冲突活动"是区间图上的独立集（区间图这类特殊图类上有多项式精确解——又一处"特款特解"的胜利）。生物信息：基因调控网络的关键节点筛选、蛋白质相互作用网络的保守模块搜索都以极值子集问题为内核。复杂度侧只补一句收官：这一族问题的"判定版是否存在大小不超过某值的解"在最一般图上极难，但每个特图类、每种近似保证、每个参数化视角都在源源产出算法研究的成果——难解不是终点，而是分型的起点。

⚠️ 常见坑：把"极大独立集"（不能再添顶点）当成"最大独立集"（规模最大）。贪心一路添到添不动，得到的是前者——局部到顶，不保证全局最大；一字之差，答案可能差得很远。

💡 关键直觉：独立集与顶点覆盖是同一张地图的攻防两读——选"在哪驻军"（独立）还是选"在哪设卡"（覆盖），补集关系让两个视角共享全部解法。加上补图翻译与着色打包，极值子集家族四题一线，学好一个等于批发四个。

收尾攻坚至此收官。下一章远征队整理行囊，把沿途见过又放过的特殊图类——一笔画的欧拉图、绕全城的哈密顿图、不交叉的平面图、掷骰子的随机图——逐一归档立卷。