从配对到图
假设每名学生最多选一个项目,每个项目最多接收一名学生,边表示允许的配对。允许的边很多,并不意味着人人都能配对:几名学生可能只能选同一个项目。以下假设有限二分图 的每条边都连接左、右两侧。
定义 2.2.1
(匹配)
的匹配是一组互不共用端点的边 。若 中有边与某顶点相接,称该顶点已匹配,否则称未匹配。大小 最大的匹配称为最大匹配。
我们要让匹配大小最大,而不是仅找一个不能再直接加入单条边的匹配。
常见错误
(极大不等于最大)
不能再加入任何边的匹配称为极大匹配,但它未必是最大匹配。对边 ,匹配 是极大的,因为 和 都与它共用端点;然而 更大。贪心地逐条加边只会停在极大匹配;要达到最大匹配,可能必须撤回先前的选择,正如第一个例题所示。
建立流网络
加入源点 和汇点 。对每个 加入容量为一的 ;对每条边 加入容量为一的 ;对每个 加入容量为一的 。
命题 2.2.2
(最大匹配就是最大整数流)
在这个网络中,最大流值等于 的最大匹配大小。更精确地说,匹配与同值的可行整数流一一对应。
证明
(双向转换)
每条匹配边沿 传送一单位,得到值等于匹配大小的可行整数流。
反过来,对任意可行整数流,单位容量使每条边流量只能为零或一。由流量守恒和两端的单位容量,流量为一的中间边不共用左右端点,故组成同样大小的匹配。整数最大流定理保证存在整数最大流,因此最大流值等于最大匹配大小。
整数条件不可省略:一般分数可行流本身并不指定一组匹配。
例题 2.2.3
(反向边如何修订配对)
假设 可选项目 或 , 只能选 。若先把 配给 ,流在 上有一单位,残量网络便包含反向边 。残量路径 用上这条边。沿路径增广一单位会取消 –,再加入 – 和 –。
最终流值为 ,只包含允许的正向配对 。两名学生都已获配,所以不存在更大的匹配。原先的局部极大单边配对 并非最大。
另一种证书:覆盖所有边
定义 2.2.4
(顶点覆盖)
的顶点覆盖是顶点集合 ,使 的每条边至少有一个端点在 中。
引理 2.2.5
(匹配不会大于覆盖)
在任何有限图中,若 是匹配而 是顶点覆盖,则 。
证明
(为每条匹配边指定一个覆盖顶点)
的每条边都有端点在 中,任选其一。 中两条不同的边没有公共端点,所以分到不同的顶点。这给出由 到 的单射。
只有找到大小相同的匹配和覆盖时,这个引理才给出可核验的最优证书。
定理 2.2.6
(二分图中的匹配与覆盖等式)
有限二分图的最大匹配大小等于最小顶点覆盖大小。
证明
(由交替可达性构造覆盖)
取最大匹配 。从所有未匹配左顶点开始走交替路径:由左向右走未匹配边,由右向左走匹配边。令到达的左右顶点集合为 。到达的右顶点不可能未匹配,否则该交替路径可增广 。
令 。它覆盖每条边:若 且 ,规则会到达 ;若 ,已到达且有匹配的左顶点必经其匹配的右端点到达,故 也已到达。(未匹配左顶点没有匹配边。)因此左端不在 的边,其右端必在 。
每条匹配边恰有一个端点在 :左端到达时右端也到达;左端未到达时右端也不能到达,否则会沿匹配边到达左端。 中每个顶点均已匹配,因为未匹配左顶点都是起点; 中每个顶点也已匹配,因为不存在增广路径。因此 。由引理即得二者分别最优。
证明使用二分性与最大匹配,不能无条件套用到任意图。
证明透视
两个假设各在哪里起作用
的最大性只用了一次:保证每个到达的右顶点都已匹配。若对非最大匹配进行同样构造,可能到达未匹配的右顶点; 仍是覆盖,但该顶点不对应 的任何边,于是 ,什么也证明不了。
二分性体现在搜索的形状上。每条边两端分属两侧,所以搜索在两侧之间交替,覆盖才可取为左侧未到达的顶点加上右侧已到达的顶点。
关键一步: 或 单独都不是小的覆盖;这个覆盖混合两侧,恰好在交替可达性停止之处转换侧别。
如何收尾:证明从未直接说明 是最小覆盖,而是证明 ;引理对每个覆盖和每个匹配都成立,于是二者同时最优。
常见错误
(把到达的顶点当作覆盖)
覆盖是 :左侧取未到达的,右侧取已到达的。取全部到达顶点 是错的。在下面的瓶颈例子中,对匹配 ,这会得到 ,漏掉了边 和 。
瓶颈例子
例题 2.2.7
(两名学生争一个项目)
令 、、。匹配 大小为二;顶点覆盖 覆盖全部四条边,大小也为二,所以不存在大小为三的匹配。直接看, 都只能选项目 ,不能同时获配。
另一个匹配 同样最优:证书确定最优值,不一定确定唯一配对。
例题 2.2.8
(完美匹配令搜索没有起点)
令 、、,匹配为 。每个左顶点都已匹配,所以交替搜索没有起点:。构造给出 。
验证: 覆盖 和 , 覆盖 。因此 是大小为 的覆盖,二者均最优。在这个退化情形中,覆盖就是整个左侧;只要 匹配了 的全部顶点,情况必定如此。
反例模式
没有二分性时匹配与覆盖等式不成立
或许有人以为任何图的最大匹配与最小覆盖都相等。取顶点为 的三角形。三条边中任意两条都共用顶点,所以最大匹配大小为一。单个顶点只覆盖与它相接的两条边,漏掉对边,所以每个覆盖至少有两个顶点; 是大小为二的覆盖。二者为 。引理 在任何图都成立;等号则需要二分假设。
练习
快速检查
(对边 ,给出可改善匹配 的交替路径和所得匹配。)
从未匹配的左顶点 出发。
解答 · 答案
交替路径 把 换成 ,得到两条匹配边。
快速检查
(在瓶颈例子中,验证 是覆盖,并解释它如何给出匹配上界。)
逐一检查四条边。
解答 · 答案
由顶点 覆盖, 由 覆盖。匹配的不同边不能共用覆盖顶点,故最多选两条。
快速检查
(在瓶颈例子中,从匹配 的未匹配左顶点 出发,求 和构造出的覆盖。)
由左向右走未匹配边,由右向左走匹配边。
解答 · 答案
从 到达 ,再沿匹配边到达 ;没有其他可到达顶点。因此 、,覆盖为 。
快速检查
(为何值为 的分数可行流不能直接描述大小为 的匹配?什么定理另行保证存在整数最优流?)
比较匹配是什么,与流量分配的是什么。
解答 · 答案
匹配是集合,其大小为整数;分数边值不一定是一组所选边。整数容量和整数最大流定理保证存在整数最大流。