匹配是整体分配问题
定义 3.3.1
(二分图、匹配与邻域)
令 为有限二分图,每条边连接一个左顶点和一个右顶点。匹配 中任意两条边都不共用端点。没有与匹配边相接的顶点称为未匹配。若每个左顶点都被匹配,称匹配饱和 。对 ,以 表示与 中至少一个顶点相邻的所有右顶点。
局部选择可能阻碍另一顶点匹配,即使存在更好的分配也一样。交替路径可以修正这些选择;找不到路径时,搜索本身亦可证明无法得到更大的匹配。本节承接网络流的残量路径,直接证明匹配问题的证书。
交替搜索与增广
定义 3.3.2
(增广路径)
增广路径由未匹配的左顶点出发,到未匹配的右顶点结束,路径上的非匹配边与匹配边交替出现。首尾两条边都不在 中。翻转路径指用路径与 的对称差替换 :移除路径上的旧匹配边,加入原来未使用的路径边。
定理 3.3.3
(增广步骤)
翻转 的一条增广路径,得到大小为 的匹配。
证明
(翻转增广路径使匹配多一条边)
路径的每个内部顶点失去一条匹配边,同时得到一条,所以它仍恰与一条匹配边相接。两个端点原本未匹配,各得到一条匹配边。路径以外的顶点不受影响。因此所得为匹配。路径上不在 中的边比在 中的边多一条,所以新的大小为 。
要找这样的路径,从所有未匹配左顶点同时开始图搜索。从已到达的左顶点,沿不在 中的边走到右方;从已到达的右顶点,如有匹配边,便沿该边走回左方。只在首次到达顶点时记录前驱。这些指针构成搜索森林:由已到达的未匹配右顶点沿前驱回溯,便得到通往未匹配左起点的简单路径,且符合所需的交替方式;否则搜索结束时,已到达的集合分别记为 和 。已访问标记可防止出现环;增广后匹配已改变,应重新搜索。
最大匹配与最小覆盖
定义 3.3.4
(顶点覆盖)
顶点覆盖是与每条边至少有一个端点相接的顶点集合。
定理 3.3.5
(Kőnig 定理)
对任何匹配 ,每个顶点覆盖的大小至少是 。在有限二分图中,匹配的最大大小等于顶点覆盖的最小大小,而且交替搜索同时给出两者。
证明
(失败的搜索给出同样大小的覆盖)
对任何匹配 ,每个覆盖的大小至少是 :每条匹配边都需要一个覆盖顶点,而不同匹配边没有共同端点。
假设交替搜索找不到增广路径,则 中每个顶点都已匹配,否则已到达的未匹配右顶点会构成增广路径。此外 :从已到达左顶点出发的每条非匹配边都被遍历;若它有匹配边,该匹配右顶点早在左顶点之前已到达。反过来,每个已到达右顶点都是从左邻点走到的。
定义
每条边都被覆盖:若左端点不在 ,它就在 ;若左端点在 ,右端点就在 。每条匹配边恰有一个端点在 ,因为其两端要么均已到达,要么均未到达。 中每个顶点均已匹配:未匹配左顶点是搜索起点,未匹配右顶点不可能已到达。因此 。匹配与覆盖提供相等的下界及上界证书,所以 最大、 最小。这证明了 Kőnig 定理。
证明透视
为何失败的搜索是完整的证书
证明从停止条件读出两个事实。没有到达未匹配的右顶点,所以 中每个顶点都有配偶,而配偶位于 。搜索沿 中每条非匹配边和 中每条匹配边走遍,所以它是封闭的,由此得到 ,并说明没有匹配边恰有一个端点被到达。这两点合起来使 成为覆盖,每条匹配边恰有一个端点在 中,而且不含未匹配顶点,所以 ,再由弱界完成论证。二分性出现在覆盖的检验中:每条边的左端点要么不在 ,要么在 ;在后一情形,搜索的封闭性使它的右端点属于 。含有奇圈的图没有这样的左右划分,下面的反例正是利用这一点。
从空匹配开始反复增广,大小每次增加一,且不超过 ,故必定终止。最后一次失败的搜索给出上述证书,无须假设贪心选择永远不改便可证明算法正确。采用邻接表时,一次搜索成本为 ;最多 次成功搜索加一次最后失败搜索,总时间为 。这只是简单上界,不声称是最佳算法。
反例模式
Kőnig 等式需要二分性
考虑这样的说法:在每个图中,匹配的最大大小都等于顶点覆盖的最小大小。取以 为顶点、边为 的三角形。其中任意两条边都有公共顶点,所以每个匹配至多含一条边。没有单独一个顶点与三条边都相交,因为 没有覆盖 , 与 同理。而 是一个覆盖。所以最大匹配的大小为一,最小覆盖的大小为二。三角形含有奇圈,不是二分图,搜索所用的左右划分并不存在。修正后的说法把等式限于二分图;对一般图,只有不等式 仍然成立。
由搜索推出 Hall 条件
定理 3.3.6
(Hall 定理)
有限二分图存在饱和 的匹配,当且仅当每个 都满足 。
证明
(由失败的搜索得出 Hall 条件)
必要性直接成立:匹配把 的不同顶点送往不同邻点。为证充分性,执行增广算法至最大匹配。若仍有未匹配左顶点,失败搜索中的 至少有一个未匹配起点。每个已到达右顶点都与不同的已到达左顶点匹配,而每个已到达且已匹配的左顶点的匹配对象都在 。因此 。由 ,集合 违反 Hall 条件。逆否命题完成证明。算法不必直接检查全部子集:若有阻碍,失败搜索便产生一个违反条件的集合。
概念视角代数
把 Kőnig 定理看成 0 与 1 的表格
把 记成一个表格:每个左顶点对应一行,每个右顶点对应一列,当且仅当 时,位置 写 。匹配就是一组 ,其中任何两个都不在同一行或同一列;顶点覆盖就是一组行和列,使每个 都落在其中某一行或某一列上。Kőnig 定理说:互相独立的 最多有多少个,恰等于覆盖所有 的行与列至少要多少条。在下面的例题中,三列 已含所有 ,并且存在三个互相独立的 。
例题:两个证书
例题 3.3.7
(四个顶点的两次搜索)
取 、,边为 –、–、–、–、– 和 –。从 开始。 和 都未匹配;搜索可选增广路径 ,得到 。
重新从唯一未匹配左顶点 搜索。交替可达性依次为
由左到右的箭头使用非匹配边,由右到左则使用匹配边。所有右顶点都已到达且已匹配,所以没有剩余增广路径。此处 、,而 是大小三的覆盖,等于匹配大小。同时 有四个顶点却只有三个邻点,展示了饱和 的 Hall 障碍。追踪采用一种特定搜索次序;证书并不依赖扫描边的次序。
例题 3.3.8
(孤立的左顶点)
取 、,只有一条边 –,所以 没有邻点。从空匹配开始,从两个未匹配的左顶点同时搜索。顶点 到达未匹配的右顶点 ,所以 – 是增广路径,得 。第二次搜索只从 出发,没有到达其他顶点:、。于是 覆盖唯一的边,大小为一,等于 。违反条件的集合是 ,其 ,所以 。有亏缺的集合可以只是一个没有任何邻点的顶点。
例题 3.3.9
(改道修正先前的选择)
取 、,边为 –、–、–,并设局部选择得到匹配 。唯一未匹配的左顶点是 。搜索先沿非匹配边 ,再沿匹配边 ,然后沿非匹配边 。右顶点 未匹配,所以 是增广路径。翻转它,删去 –,加入 – 和 –,得到大小为二、饱和 的匹配。先前选择的 – 被撤销,而不是保留。
常见错误
常见错误
(Hall 条件针对子集,而不是单个顶点)
只检查每个左顶点都有邻点并不足够,因为不同的左顶点可能争夺同样的右顶点。在边为 –、–、– 的图中,每个左顶点都有邻点,但 的 ,不存在饱和 的匹配。失败的搜索会产生这样的子集,所以无需枚举所有子集。
常见错误
(大小相等并不构成证书)
只有当顶点集合确实是覆盖时,大小相等的匹配与顶点集合才证明最优性。取边 –、–、–、–。匹配 与集合 的大小都是二,但 漏掉了边 –,所以它不是覆盖,什么也证明不了。应先逐条边检验覆盖性质,再比较大小。
练习
快速检查
(取 、,边为 –、–、–。给出最大匹配、大小相同的覆盖,以及违反 Hall 条件的子集。)
找出两个只共用一个邻点的左顶点。
解答 · 答案
匹配 的大小为二。集合 与每条边相交,大小也是二,所以两者都是最优的。子集 的 ,所以 ,不存在饱和 的匹配。
快速检查
(解释为何翻转增广路径使匹配大小恰增加一,包括端点发生了什么。)
数一数路径上属于 和不属于 的边各有多少条。
解答 · 答案
路径上不在 中的边比在 中的边多一条,所以翻转加入的边比移除的多一条。每个内部顶点以一条匹配边换另一条,仍恰匹配一次。每个端点原本未匹配,得到一条新的匹配边,因而匹配一次。
快速检查
(若交替搜索尚未遍历所有可达顶点便过早停止,为何所得匹配与所提出的覆盖可能无法证明两者的最优大小相等?)
已到达的集合对遍历规则是否封闭?
解答 · 答案
此时 与 对遍历规则并不封闭。某个已到达的左顶点可能有一条非匹配边通向尚未属于 的右顶点。这条边的两个端点都不在 中,所以 未必是覆盖。未到达的右顶点也可能是未匹配的,这时增广路径仍然存在, 并不是最大的。只有搜索完成之后,两个性质才同时成立。