动机
假设若干工作必须分配给互不相同的工人,且每项工作都有一份可接受的工人名单。贪心地选取一名可用的工人,可能会堵住后面的工作,即使完整的分配方案其实存在。增广路可以修正先前的选择:它在未使用的边与已使用的边之间交替,把这些边的状态整体翻转后,分配数恰好增加一。
对于二分图,同样的搜索在无法继续改进时还会给出一份证书。顶点覆盖证明某个匹配是最大的,而一组有亏缺的工作则说明为什么不存在完整的分配。这些见证把算法给出的答案变成可以独立检验的结论。
定义
定义 3.10.1
(二分图、匹配与已匹配顶点)
设 为有限简单二分图,其左、右顶点集不相交,且每条边都连接两侧各一个顶点。匹配 中任意两条边都没有公共端点。与 中某条边关联的顶点称为已匹配顶点,否则称为未匹配顶点。匹配的大小是其所含边的条数。
定义 3.10.2
(增广路)
对于 ,增广路是一条简单路径:它从 中的一个未匹配顶点出发,终止于 中的一个未匹配顶点,并且在 之外的边与 中的边之间交替。它的第一条边和最后一条边都不在 中。翻转路径上每条边的状态,就是删去路径上属于匹配的边,并加入其余的边。
定义 3.10.3
(顶点覆盖与邻域)
顶点覆盖是与每条边都相交的顶点集合。对于 ,其邻域 是与 中至少一个成员相邻的顶点的集合。空图与空匹配都是允许的;若 为空,则覆盖 全部顶点的匹配平凡地存在。
定理
定理 3.10.4
(增广路判据)
一个匹配是最大匹配,当且仅当它不存在增广路。翻转一条增广路会得到一个多一条边的匹配。
定理 3.10.5
(Hall 证书与匹配-覆盖证书)
覆盖 中每个顶点的匹配存在,当且仅当对每个 都有 。此外,每个有限二分图都有一个顶点覆盖,其大小等于最大匹配的大小。
证明
翻转为何有效
证明
(翻转增广路使匹配增大)
增广路以未匹配边开始并以未匹配边结束,且两种边交替出现,因此它含有的 之外的边比 中的边恰好多一条。在内部顶点处,路径上恰有一条边属于匹配、一条边不属于匹配,翻转就是把两者互换。在每个端点处,新加入的边是唯一的匹配边,因为该端点原先是未匹配的。路径之外的顶点保持原来的状态。所以翻转后的边集是一个大小为 的匹配。
证明
(没有增广路即为最大匹配)
最大匹配不可能有增广路,因为翻转会使它变大。对于反方向,把 与任意一个更大的匹配 比较。构造它们的对称差:保留恰好属于其中一个匹配的边。在对称差中每个顶点的度至多为二,且与它关联的边在 与 之间交替。每个连通分支要么是交替路径,要么是交替圈,要么是孤立顶点。圈中两个匹配的边数相等。路径中一个匹配的边数至多比另一个多一。
因为 ,所以某个分支路径中 的边比 的边多一条。它两端的边都属于 ,因此其端点在 下是未匹配的。在二分图中,这条奇数长度的路径两个端点分别位于两侧;把它从 到 定向,它就是 的一条增广路。因此,若不存在增广路,则不存在更大的匹配。
证明透视
通过对称差比较两个匹配
这个证明只有一个想法:通过两个匹配不一致的边来比较它们。每个顶点至多关联 的一条边和 的一条边,所以它在对称差中的度至多为二,连通分支因此只能是路径或圈。沿着路径或圈,边在 与 之间交替,所以圈中两个匹配的边数相等,不可能解释 的盈余。盈余只能出现在路径上,而一条路径至多多出一条边。多出一条 边的路径,两端的边都属于 。 中没有边可以与它的端点相交:这样的边若不同时属于 ,便是该端点的第二条 边;若同时属于两个匹配,它就不在对称差之中。所以两个端点在 下都是自由的。二分性只在最后一步使用,用来说明奇数长度的路径两端分属两侧。若没有 这个假设,对称差可以只由圈和两边平衡的路径组成,也就不能保证存在改进。
搜索与最优性证书
从任意匹配出发,把每条未匹配边定向为从 到 ,把每条匹配边定向为从 到 。从所有未匹配的左顶点出发搜索这个有向图。若到达某个未匹配的右顶点,则由前驱指针给出一条增广路。翻转它,然后重复。每次翻转都使匹配的大小增加,因此至多发生 次翻转。使用邻接表时,一次搜索需要 时间,于是包括最后一次搜索在内的总时间为 。
证明
(失败的搜索给出同样大小的覆盖)
设最后一次搜索没有找到未匹配的右顶点。令 与 分别为两侧被到达的顶点。定义
这是一个顶点覆盖。考虑边 。若 ,则其左端点属于 。若 且该边是未匹配的,则有向搜索会到达 。若该边是匹配边,则被到达的已匹配左顶点必定是沿着它唯一的匹配边从它的配偶 到达的;未匹配的根没有与之关联的匹配边。因此无论哪种情形都有 ,该边被覆盖。
中的每个顶点都是已匹配的,因为到达未匹配的右顶点就会给出一条增广路。它的配偶位于 中。反过来,由同样的搜索论证, 中每个已匹配顶点的配偶都位于 中。一条匹配边要么两个端点都被到达,要么都没有被到达。因此覆盖 恰好含有 中每条边的一个端点,并且不含任何未匹配顶点:它的大小恰好是 。
任何顶点覆盖的大小都不小于任何匹配的大小,因为不同的匹配边需要不同的覆盖顶点。于是 与 互相证明对方的最优性。这就在不预先假定的情况下证明了定理中的匹配-覆盖部分。
反例模式
贪心分配可能卡住
设 ,,边为 。贪心地选取 会使 未匹配。交替路径 翻转旧边 ,并加入 ,得到大小为二的匹配。
阅读证书
最后一次搜索有两种可能的用途。若它到达某个未匹配的右顶点,则前驱链接给出一串具体的边变更。若没有到达,则被到达的集合给出一个覆盖,并且当某个左根仍未匹配时,还给出一个有亏缺的邻域。这是同一次探索的不同结果。验证者不必信任搜索的实现:他可以直接根据图检验匹配、覆盖和邻域的断言。
概念视角算法
把匹配看作整数单位流
最大匹配也可以由单位容量的流构造得到:把源点连到每个左顶点,把每条原有的边从左向右定向,并把每个右顶点连到汇点。一个整数的单位流选出一条边,两端的单位容量则防止两条被选出的边共享一个顶点。上面的交替路径正是这个特定网络中的残量增广路。这里的直接证明额外提供了 Hall 见证,并使先前分配的撤销清晰可见。
定义 3.10.6
(极大匹配)
极大匹配是指没有任何边可以直接加入而仍保持匹配性质的匹配。每个最大匹配都是极大的,但反过来不成立,贪心的例子就说明了这一点: 是极大的,因为其余两条边都碰到已匹配的端点,然而翻转一条交替路径却得到两条边。因此,对单条边的局部检查不能代替增广路判据。
反例模式
覆盖等式不能去掉二分性
在一般图中,最大匹配与最小顶点覆盖的大小可以不同。取以 为顶点、边为 的三角形。其中任意两条边都有公共顶点,所以匹配至多含一条边。单独一个顶点只与三条边中的两条相交: 没有覆盖 , 与 同理。因此每个覆盖至少需要两个顶点,而 就是一个覆盖。最大匹配的大小为一,最小覆盖的大小为二。三角形含有奇圈,不是二分图,定理中的等式在这里不成立。
Hall 条件的证明
证明
(由失败的搜索得出 Hall 条件)
若某个匹配覆盖 ,则任意 中的不同顶点被匹配到 中不同的顶点。因此 是必要的。
对于充分性,取一个最大匹配,并假设它使某个左顶点未匹配。运行最后一次交替搜索。集合 至少含有一个未匹配的根。被到达的左顶点的每个邻点在右侧都被到达:未匹配边沿正向被遍历,而被到达的已匹配左顶点的匹配边通向已经被到达的、发现它的那个右顶点。反过来,每个被到达的右顶点都是从 中的某个左邻点到达的。因此 。
的所有顶点都被匹配到 中互不相同的顶点。被到达的左侧还至少含有一个未匹配的根,所以 。这是对 Hall 条件的明确违反。其逆否命题证明了充分性,并且每当不存在覆盖左侧的匹配时,都给出一个可检验的亏缺集合。
证明透视
最大性只用来使搜索失败
充分性只用了一次最大匹配:它保证最后一次搜索会失败。失败表示没有到达未匹配的右顶点,所以 中每个顶点都有配对对象,而这个对象也被到达。于是 中已匹配的顶点与 的顶点一一对应,再加上未匹配的起点,便得 。搜索对遍历封闭,故 ,这一计数即成为对明确集合 的 。违反条件的集合是从失败的搜索读出的,而不是靠枚举找到。
该条件适用于 的每个子集,而不仅仅是单个顶点。每项工作至少有一名可接受的工人,并不保证所有工作能同时得到分配。一组工作合起来可能可选的工人太少。
例题详解
例题 3.10.7
(修复一个贪心匹配)
对于 , 以及边 ,从 开始。从未匹配的 出发搜索:沿正向遍历 ,沿反向遍历匹配边 ,再沿正向遍历 。顶点 是未匹配的。翻转后得到 ,它覆盖了两个左顶点。
例题 3.10.8
(一个 Hall 障碍)
设 ,,其中 和 只与 相邻, 与 和 相邻。每个左顶点都有邻点,但 的 。因为 ,所以不存在覆盖 的匹配。匹配 是大小为二的最大匹配。
例题 3.10.9
(覆盖证明最大大小)
对于上一个图, 覆盖所有边,大小为二。匹配 的大小也是二。任何匹配的边数都不可能超过顶点覆盖的顶点数,因此无需枚举所有可能的匹配,两者都是最优的。
例题 3.10.10
(某一侧可以为空)
若 而 是任意有限集合,则空匹配覆盖 的每个顶点。Hall 条件只有子集 ,此时 。空的顶点覆盖也是最优的,因为没有边。
常见错误
常见错误
(交替不等于增广)
交替路径并不自动是增广路:它的两个端点都必须是未匹配的,这样才会含有比已使用的边多一条的未使用边。在贪心例子中取 ,路径 是交替的,但它的端点 是已匹配的。翻转后 被 取代,大小仍是一。同样,翻转交替圈只会改变被选中的边,不会使匹配变大。
常见错误
(大小相等本身不构成最优性证书)
只有当所提出的集合确实与每条边都相交时,匹配-覆盖证书才成立。在边为 的图中,集合 与匹配 大小相同,却漏掉了 ,所以它不是覆盖。应当先验证该边集是匹配,再检验覆盖性质,最后才比较大小。
常见错误
(Hall 条件针对子集,而不是单个顶点)
只检查每个左顶点都有邻点,会遗漏不同左顶点之间的冲突。在同一个图中,、、 各自都有邻点,但 的 。当最大匹配没有覆盖左侧时,交替搜索会给出一个具体的违反条件的子集;要得到这份证书,无需枚举所有子集。
总结
增广路提供局部改进,而对称差证明了此类路径的缺失在全局上是决定性的。最后一次交替搜索给出与匹配大小相同的顶点覆盖。若某个左顶点仍未匹配,则被到达的左集合的邻点太少,从而给出 Hall 障碍。这些证书既解释了分配的成功,也解释了它的失败。
练习
快速检查
(在贪心的例子中,写出翻转路径 之前和之后各条边的状态。)
把 、、 三条边逐条列出。
解答 · 答案
起初 是已匹配的,而 与 是未匹配的。翻转后删去 ,并加入 与 ,所以之后 未匹配, 与 已匹配。结果是大小为二而不是一的匹配。
快速检查
(设三个左顶点都只与两个右顶点相邻。给出一个 Hall 障碍,并给出匹配大小的一个上界。)
试取 为整个左侧。
解答 · 答案
取 为全部三个左顶点。它的邻域至多有两个顶点,因此 。匹配的每条边使用不同的右端点,所以匹配的大小至多为二。
练习 3.10.11
(同一个图中的匹配 与顶点覆盖 满足 。证明 是最大匹配, 是最小顶点覆盖。)
核心证明
两个集合都在同一个图中,只知道它们的大小。
提示(1)
匹配中不同的边没有公共端点,所以覆盖要为每条匹配边各用一个不同的顶点。
解答(3)
- 1
比较任意匹配与任意覆盖
关键一步
对图中任意匹配 与任意顶点覆盖 ,
依据: 不同的匹配边没有公共端点,而每条边都需要一个覆盖顶点。
- 2
给每个覆盖一个下界
取 ,得到对每个覆盖 都有 。由于 ,覆盖 的大小已是最小可能值。
- 3
给每个匹配一个上界
∎取 ,得到对每个匹配 都有 。由于 ,匹配 是最大匹配,而 是最小顶点覆盖。
快速检查
(若一个匹配覆盖 的所有顶点,解释为什么每个子集 至少有 个邻点,包括 的情形。)
把 的每个顶点送到它的配偶。
解答 · 答案
该匹配把 的每个顶点送到不同的右邻点,给出从 到 的单射。因此 。对于空集,这是成立的不等式 。