图的匹配

在有限无向图中，匹配是若干条两两没有公共端点的边。若每个顶点都恰好落在一条匹配边上，便是完美匹配；若只要求被覆盖的顶点数尽可能多，便是最大匹配。这里“最大”指边数在所有匹配中最大，“极大匹配”却只表示不能再直接添一条边，两者不等价。比如路径 $a - b - c - d$ ：只选中间边 $b c$ 已无法添其他边，是极大匹配；选 $a b, c d$ 才是大小为 2 的最大匹配。

三人三任务的指派

考虑二分图左侧三人 $L = {a, b, c}$ 、右侧三任务 $R = {1, 2, 3}$ ，允许的边为 $a 1, a 2, b 1, c 2, c 3$ 。先选 $M = {a 1, c 2}$ ，大小为 2；这时 $b$ 与任务 $3$ 都未匹配。直接加入 $b 1$ 会与 $a 1$ 冲突，但可以沿 $b - 1 - a - 2 - c - 3$ 走：第一条边 $b 1$ 未被选，下一条 $1 a$ 已被选，此后交替。把这条路上的“未选边”改为选中，把原“已选边”删去，得到 ${b 1, a 2, c 3}$ ，大小为 3，三人全部获分任务。这条起终点均未匹配、边在“未选—已选”之间交替的路，称为增广路。

左侧人物a、b、c与右侧任务1、2、3；金色和青色实线是最终匹配b1、a2、c3，虚线是可用但未选的a1、c2 — 沿 b—1—a—2—c—3 翻转后，三条实线覆盖了两侧全部顶点；图上交叉处并没有顶点。

图中虚线 $a 1, c 2$ 是原来的两条匹配边，翻转后退出；实线 $b 1, a 2, c 3$ 是新加入的三条边。两条实线在纸面上交叉的地方并没有画出顶点，因此它们不共端点。把“画线相交”误当作图的“共同顶点”，会把这组有效匹配误判为冲突；图论判断以标出的顶点与边为准。

增广路判据

沿增广路翻转边的归属，会比原匹配多选一条边，所以有增广路的匹配一定不是最大匹配。反过来，若 $M$ 不是最大匹配，取边数更多的匹配 $N$ ，只看属于二者之一而非二者共有的边，形成对称差图。由于每个顶点在 $M$ 和 $N$ 中各至多接一条边，该图分解成相互独立的交替路径与偶环。偶环两类边数相等，而 $| N | > | M |$ ，某条交替路径必有比 $M$ 多一条的 $N$ 边；它两端在 $M$ 中未匹配，正是相对于 $M$ 的增广路。故匹配最大，当且仅当不存在增广路。这给出一个可检验的最优性条件，而非只靠局部“再也添不上边”的直觉。

全覆盖的条件

对二分图，要让左侧每个顶点都获得一个不同的右侧伙伴，必须对任意 $S \subseteq L$ 有 $| N (S) | \geq | S |$ ，其中 $N (S)$ 是 $S$ 在右侧的所有邻点： $k$ 个人若合起来只认识 $k - 1$ 个任务，不可能人人得到不同任务。Hall 定理说明这一条件也充分。

充分性的思路是反证。假设已有一个最大匹配却留有未匹配的左侧顶点，从它们沿未匹配边向右、再沿匹配边向左，寻找所有能到达的点。若到达某个未匹配右点，就存在增广路，与最大性冲突；因此所有到达的右点都已匹配。设到达的左点集合为 $S$ ，右点集合为 $N (S)$ ；每个到达的右点沿其匹配边又能到达左点，而 $S$ 还包含至少一个最初未匹配的左点，所以 $| S | > | N (S) |$ ，违背条件。于是最大匹配必须覆盖全部左侧顶点。

如果 $| L | = | R |$ ，全覆盖左侧也覆盖右侧，成为完美匹配；若两侧人数不同，“覆盖左侧”与“完美匹配”应明确区分。实际指派问题还可能带费用、容量或优先顺序，那需要在是否存在匹配之外另设优化目标。

可以用四个左顶点、三个右顶点自行检查 Hall 条件：取 $S = L$ ，邻点无论怎样添加边，至多只有三个，必有 $| N (S) | \leq 3 < 4 = | S |$ ，所以不能覆盖全部左点。但反方向不能只看全集：若左侧三个顶点中 $a, b$ 都只连向任务 1，第三个 $c$ 连向任务 2 和 3，全集的邻点数是 3，看似够用；取子集 $S = {a, b}$ 时却只有 $N (S) = {1}$ ，立刻暴露瓶颈。因此定理要求对每个子集检查，不是只比较左右总人数。

参考资料