一个岗位最多安排一人，冲突的两项任务不能同时选择。这两类限制都能用图表达，但一个问题要选边，另一个问题要选点。

本文用二分图匹配与独立集学习图建模、局部调整以及“最大”和“极大”的区别。需要了解顶点、边与邻接关系及问题的约束与目标。

上一篇：动态规划。下一篇：计算复杂性。

1. 二分图匹配：选择互不争抢端点的边

1.1 把“能不能分配”表示成边

二分图把顶点分成两侧 $L,R$，每条边连接不同侧的顶点。例如左边是求职者，右边是岗位，边表示具备对应资格。

匹配 $M\subseteq E$ 是一个边集合，其中任意两条边都没有公共端点：一个人最多拿到一个岗位，一个岗位最多给一个人。

课件第29页展示的一个匹配为：

$$ M=\{(A,1),(B,2),(C,4),(D,3),(E,5)\} $$

所有边都存在，而且没有重复使用任何端点，大小为5。左右两侧各只有5个顶点，任何匹配都不可能超过5条边，所以这个匹配已经达到上界，是最大匹配。

1.2 被占用的岗位，不一定永远不能再考虑

考虑一个更小的二分图：A 可以匹配岗位1或2，B只能匹配岗位1。

如果先选 A-1，B 就无岗位可选。直接停止只能得到1条边，但可以先把 A 调整到2，再把1分配给 B。

二分图中的增广路：撤销A到1，再加入B到1和A到2，使匹配数从1增加到2

路径 B → 1 → A → 2 上，未选边、已选边、未选边交替出现。把这条路径上的选择状态全部翻转，会删掉1条已选边、增加2条未选边，匹配数净增1。

这叫增广路。它说明“没有一条边能直接加进去”，不等于“不能通过重新安排得到更大的匹配”。

不断搜索并翻转增广路，可以逐步增大匹配；下面的代码聚焦候选解检查和一条已知路径的翻转。Hopcroft–Karp将多条最短增广路分阶段处理，是后续完整匹配算法的学习主题。

课件第29页的目标是无权最大匹配，第32页汇总又提到了带权匹配。两者目标不同：一个最大化边数，一个最大化边权总和。算法名称和复杂度也需要跟具体版本对应，不能把汇总中的简略复杂度直接当作所有匹配算法的统一界限。

1.3 把“最大”与“极大”分开

最大匹配在所有合法匹配中边数最多；极大匹配则不能直接再增加一条边。极大只排除了直接添加，允许重新安排时仍可能增大。

A只能去1或2、B只能去1的例子中，单边A-1是极大的，因为剩余边都争抢一个端点；它不是最大的，因为A-2与B-1构成两条边。

对于前面5人5岗位的实例，可将允许关系列为：

人 可分配岗位
A 1、3
B 1、2
C 2、3、4
D 2、3
E 3、4、5

前面给出的五条匹配边都在此表中，且达到两侧顶点数的上界。这个上界直接证明了该实例的最大性。

2. 独立集：选择互不相邻的顶点

2.1 独立集要求选中的顶点之间没有边

给定无向简单图 $G=(V,E)$，独立集是满足下式的顶点集合 $S\subseteq V$：

$$ \forall u,v\in S,\ u\ne v\Longrightarrow\{u,v\}\notin E $$

如果顶点代表任务，边代表冲突，那么独立集就是一组两两不冲突的任务。

沿用课件第30页的图，其边为：

1-2, 1-3, 2-3, 2-4, 2-5, 3-6, 4-7, 5-7, 6-7

其中 $S=\{1,4,5,6\}$ 是大小为4的独立集。

同一个图中的最大独立集与极大但非最大的独立集

为什么不可能选5个？顶点1、2、3构成三角形，最多选1个；剩下只有4、5、6、7，其中7与另外三个都有边，最多选3个。因此任何独立集大小最多是 $1+3=4$，上述方案达到上界。

2.2 最大与极大，差一个字但不是一回事

  • 最大独立集：在所有独立集中，顶点数量最多。
  • 极大独立集：在当前独立集基础上，不能再直接加入其他顶点。

本图中的 $\{2,7\}$ 是极大独立集：其余每个顶点都与2或7相邻，所以不能直接添加。但是它只有2个顶点，不是最大独立集。

与匹配中的重新安排类似，局部“加不进去”不代表全局最优。

3. 边的选择、点的选择与特殊结构

可以把每个区间当作一个顶点，有重叠的区间之间连边。于是无权区间调度对应这个冲突图上的最大独立集，带权调度对应最大权独立集。

关键区别在于：区间之间形成的是具有特殊结构的区间图，而不是任意图。时间轴的顺序结构支持贪心区间调度和带权动态规划。

一个问题在某种特殊图上容易，不代表推广到一般图后仍然容易；反过来，一般图上的困难性，也不妨碍特殊图上的高效算法。

匹配与独立集都选择一个子集，候选对象与冲突规则却不同：

项目 匹配 独立集
选择对象 边 顶点
合法条件 任意两条边无公共端点 任意两个已选顶点之间无边
最大 边数最多 顶点数最多
极大 不能直接增加边 不能直接增加顶点

对半开活动区间，只有实际占用时间重叠时连冲突边，端点相接不连边。这里的区间图采用这一冲突约定；时间轴结构支持专门的算法。一般图上的独立集判定与优化困难性，见计算复杂性篇。

4. Python检查候选解与已知增广路

先用代码把“合法”与“大小”分开检查：

def is_matching(left, right, allowed, pairs):
    left, right, allowed = set(left), set(right), set(allowed)
    pairs = list(pairs)
    return (
        len(pairs) == len(set(pairs))
        and all(u in left and v in right and (u, v) in allowed
                for u, v in pairs)
        and len({u for u, _ in pairs}) == len(pairs)
        and len({v for _, v in pairs}) == len(pairs)
    )


def is_independent(vertices, edges, selected):
    vertices, selected = set(vertices), set(selected)
    return selected <= vertices and all(
        not (u in selected and v in selected) for u, v in edges
    )


allowed = {("A", 1), ("A", 2), ("B", 1)}
initial = {("A", 1)}
path_edges = {("B", 1), ("A", 1), ("A", 2)}
augmented = initial ^ path_edges

assert is_matching({"A", "B"}, {1, 2}, allowed, initial)
assert augmented == {("A", 2), ("B", 1)}
assert is_matching({"A", "B"}, {1, 2}, allowed, augmented)
assert not is_matching({"A", "B"}, {1, 2}, allowed,
                       [("A", 1), ("B", 1)])

vertices = set(range(1, 8))
edges = [(1, 2), (1, 3), (2, 3), (2, 4), (2, 5),
         (3, 6), (4, 7), (5, 7), (6, 7)]
assert is_independent(vertices, edges, {1, 4, 5, 6})
assert is_independent(vertices, edges, {2, 7})
assert not is_independent(vertices, edges, {1, 2})
print(len(initial), len(augmented))

输出1 2。集合的对称差^删除路径上原有的匹配边，加入原来没有的边。路径需要连接两个未匹配端点、边状态交替，才能得到这里的增广效果；任意一组边的对称差未必仍是匹配。

在哈希集合平均常数时间操作的模型下，匹配检查遍历允许边与候选边，独立集检查遍历顶点和边，均为输入长度的线性量级。检查候选集合是否合法，与证明它全局最大，是不同任务。前面的最大性证明还使用了顶点数量上界或图的结构上界。

5. 易错点

极大只表示当前方案不能直接扩充，最大才比较全部合法方案。匹配的一条边有两个端点，约束检查要覆盖两侧。增广路允许先撤销旧边再重新安排；独立集的“当前加不进去”同样不等于最大。

特殊图中的高效方法依赖结构。把区间冲突改成任意图后，原有的排序与前驱就可能不再表达全部约束。

6. 练习

练习1：是否为二分图

三角形1-2-3-1能否将顶点分成两侧、使每条边跨侧？四顶点环1-2-3-4-1呢？

练习2：匹配是否合法

允许边A-1、A-2、B-1，集合{A-1,B-1}是否合法？{A-2,B-1}呢？

练习3：手找增广路

当前只有A-1，写出增广路径和翻转后结果。当前匹配是否极大、是否最大？

练习4：独立集检查

对本文七顶点图，{1,4,6}是独立集吗？能否直接再加入一个点？

练习5：极大与最大

{2,7}为什么极大却非最大？{1,4,5,6}的最大性怎样由上界证明？

7. 参考答案

  1. 三角形不能：假设1在左侧，2和3都需在右侧，但2-3又要求跨侧，矛盾。四环可以取{1,3}与{2,4}。
  2. 第一组重复使用岗位1，不合法。第二组边均存在，两侧端点互不重复，合法。
  3. 路径B→1→A→2，删A-1，增B-1与A-2，净增1。原匹配不能直接添加任何边，所以极大；重排可得2条，所以非最大。
  4. 是，三点之间均无边；还能加入5，因此它连极大也不是。
  5. 其他顶点都与2或7相邻，所以不能直接加入；但存在大小4的{1,4,5,6}。三角形{1,2,3}至多取1点，其余{4,5,6,7}至多取3点，上界4被达到。

8. 后续学习与资料

上一篇：动态规划；下一篇：计算复杂性入门。后续可以学习图遍历、完整增广路搜索、Hopcroft–Karp与网络流。

参考：《Design and Analysis of Algorithms》Introduction第29至30页的二分图匹配与七顶点独立集。增广路、最大与极大图例及原练习保留于本篇，候选解检查代码用于对应定义。