动机
一组各自可接受的分配,未必能够同时实现。若干请求可能在争夺过少的可选项。匹配记录的是没有公共端点的分配。核心问题是:一次失败的尝试,揭示的是真正的资源短缺,还是仅仅源于先前的一个不佳决定。
交错路径能够区分这两种情形。它可以撤销部分已选定的分配,同时使总分配数多出一个。如果不存在这样的改进,那么这次失败的搜索本身就会指出一个邻点过少的集合,并构造出一个最小顶点覆盖。因此,同一个论证既解释了一个算法、一个存在性定理,也解释了两个最优化问题之间的等式。
定义
定义 6.1.1
(匹配与顶点覆盖)
有限简单图中的匹配 是一个边集,其中各边的端点两两不相交。若 中有一条边与某顶点相交,则称该顶点被 饱和。最大匹配的大小是可能的最大值;极大匹配则不能通过添加单独一条边而扩大。完美匹配饱和每一个顶点。顶点覆盖是与每条边都相交的顶点集。
二部图带有指定的不相交顶点划分 ,且每条边都连接两个部分。对于 ,其邻集为 。当两部分大小不同时,饱和 的匹配不一定饱和 。
定义 6.1.2
(交错路径与增广路径)
相对于匹配 ,交错路径的边在 之外与 之内交替出现。增广路径的顶点互不相同,起点和终点都是未饱和的顶点,并且其第一条和最后一条边都不属于 。因此它含有奇数条边,且 之外的边比 之内的边多一条。
把增广路径上属于匹配的边替换为该路径上的其余边,称为增广。内部顶点仍然保持饱和,两个端点变为饱和,路径之外的顶点不变。这些局部事实说明,增广会产生另一个匹配,并且恰好大一个单位。
定理/命题
定理 6.1.3
(增广路径判据)
有限图中的一个匹配是最大匹配,当且仅当相对于它不存在增广路径。这一判据不要求图是二部图。
定理 6.1.4
(Hall 条件)
部分为 的有限二部图存在饱和 的匹配,当且仅当对每个子集 都有 。空子集也包括在内,且自动满足该不等式。
定理 6.1.5
(König 匹配–覆盖等式)
在有限二部图中,匹配的最大大小等于顶点覆盖的最小大小。更确切地说,一个最大匹配可通过下面证明的交错可达性构造,确定一个大小相同的覆盖。
证明思路或证明
证明
(用对称差比较两个匹配)
增广路径会使匹配变大,所以最大匹配不可能有增广路径。反之,假设匹配 小于另一个匹配 。考虑边集为 的图,即恰好属于二者之一的边。每个顶点的度至多为二,每个非平凡连通分支都是边类型交替出现的路径或圈。圈中两种类型的边数目相等。由于 ,某条路径所含的 边比 边多一条,它以 边开始并以 边结束。
它的端点未被 饱和。端点不可能在对称差中还有另一条 边,因为它在对称差中是端点。它也不可能有一条 与 共有的边,因为与它相连的 边已经属于该路径,而 是匹配。因此这条路径是 增广路径,判据得证。
证明
(交错可达性给出 Hall 证据与覆盖)
对于二部图的结论,取一个最大匹配 ,并令 为 中未饱和的顶点。把每条未匹配的边从 指向 ,把每条已匹配的边从 指向 。令 分别为在两个部分中从 出发可达的顶点,并允许根处的长度为零的可达。
中没有未饱和的顶点:通向这样一个顶点的有向路径将是增广路径。因此 中每个被到达的顶点都是已匹配的,并且它的匹配伙伴在 中。反过来, 中每个顶点都是经由它的匹配边到达的,所以它的伙伴在 中。匹配在这两个集合之间建立一一对应,得到
此外 。每个被到达的右侧顶点都是从某个左侧邻点到达的。从被到达的左侧顶点出发的每条未匹配边都可以被沿用;其匹配边(若存在)通向的右侧顶点,正是到达该左侧顶点时所经过的那个右侧顶点。因此它的所有邻点都被到达。
Hall 条件的必要性是直接的:饱和 的匹配把任意 中互不相同的顶点送到互不相同的邻点。对于充分性,若 非空,则所构造的集合满足
这与 Hall 条件矛盾。因此 饱和 。
最后令 。左端点在 之外的边在该端点处被覆盖;左端点在 中的边,其右端点在 中。所以 覆盖每一条边。它的大小为
任何覆盖都至少要为每条匹配边各取一个互不相同的顶点,所以没有覆盖能比匹配更小。所构造出的等式证明了 König 定理。
证明透视
极大性与二部性在哪里进入
二部图的证明恰好只用一次 的最大性:没有被到达的右侧顶点是未饱和的,否则搜索就已找到增广路径。其余一切都来自定向。未匹配的边由 指向 ,匹配边指回来,所以被到达的右侧顶点只能沿其匹配边离开;这给出 与 之间的配偶双射,从而 。可达性的封闭性给出 ,而这一个等式一身两用。当 时,它使 成为 Hall 亏量集;读作“没有边从 通往 ”,它又使 成为覆盖。二部性使一个定向就能记录交错;在一般图中,一个顶点可以在两种奇偶性下都被到达,配偶双射便不再成立。
例题详解
例题 6.1.6
(一个可以修复的极大匹配)
令 ,,边为 。匹配 是极大的:不与已有端点共享就无法再添加任何剩余的边。然而 是一条增广路径。把 替换为 ,就得到大小为二的匹配。这一修复暂时撤销了先前的一个分配;只允许添加的规则会错过它。
例题 6.1.7
(亏量集与最小覆盖)
令 ,,边为 。集合 只有邻点 ,所以没有匹配能饱和 。取 。从根 出发做交错可达,得到 和 。所得覆盖为 ,大小为二。这既证明了 是最大匹配,也证明了该覆盖是最小的。整个左侧集合有三个邻点,所以只检查整个集合会错过这个障碍。
例题 6.1.8
(每个正度正则二部图都有完美匹配)
设一个有限非空二部图是 正则的,其中 。从两个部分分别数边,得 ,所以两部分大小相等。对任意 ,恰有 条边从 出发,且都终止于 ;而 的顶点总共至多关联 条边。因此 。由 Hall 定理,存在饱和 的匹配;两部分大小相等使它成为完美匹配。正性条件使我们能约去 ,并排除了孤立顶点导致的反例。
为什么对称差是恰当的比较方式
仅比较匹配的大小,只能说明存在改进,却无法说明如何找到或理解它。对称差去掉了两个候选匹配已经一致的边。剩下的部分具有刚性的局部结构,因为两个匹配都不会在同一顶点上使用两条边。度至多为二迫使它们成为路径和圈,而边类型的交替使得对它们大小之差的计算很简单。
含两种类型的边数目相同的路径,仅仅是交换了分配。圈也一样。只有较大匹配的边多一条的路径才能增加基数。这就是为什么一次改进可能需要多次反转,却从不需要任意分叉的重排。增广路径把比较中有用的一个分支分离了出来。
该判据在所有有限图中证明了最优性,但高效地搜索增广路径在二部图中更容易。在那里,固定的划分和边的定向使得直接的可达性搜索得以组织起来。在非二部图中,奇数交错结构可能使朴素搜索不够用。定理依然成立;需要额外假设的是简单的二部图搜索过程。
把证明变成算法
从空匹配开始。在有向交错图中,从所有未饱和的左侧顶点出发搜索。如果到达了一个未饱和的右侧顶点,就利用父指针提取出一条简单有向路径并增广。为新匹配重建定向,然后重复。每次增广使边数增加一,所以增广次数至多为较小部分的大小。
如果没有到达任何未饱和的右侧顶点,同样的可达集证明会构造出一个与当前匹配同样大小的覆盖。因此停止条件证明了最大基数;它并不仅仅是某个特定贪心选择的失败。特别地,先前的一个不佳分配可以在之后的搜索中被纠正,正如第一个例子所示。
使用邻接表时,每次搜索需要 时间,包括初始化可达性数据。重复进行就得到一个直接的界 。这是该初等算法的界,而不是二部匹配已知的最佳界。当存在许多孤立顶点时,保留顶点项是有意义的。更稠密的表示可以改变搜索成本,尽管证明并不改变。
度量必须有多少请求保持未分配
定义最大亏量为 的子集上 的最大值。它是非负的,因为空集给出零。对于任何匹配和任何这样的子集,至多只有与其邻点数相同的顶点能被匹配,所以至少有与其亏量相同数目的左侧顶点必须保持未匹配。
对于最大匹配,交错可达集达到这个下界。被到达的左侧顶点、被到达的右侧顶点与未匹配的根之间的等式表明,它的亏量恰好等于未匹配左侧顶点的数目。因此
Hall 定理恰好是亏量为零的情形。这个公式还解释了为什么失败证书可以比是或否的回答更有信息量:它量化了不可避免的短缺。不需要假设两个部分大小相等。
概念视角结构
一个可行构造与一个普遍的界相遇
匹配展示了可以共存的分配。覆盖则为每个匹配给出了上界,因为每条互不相交的边都需要各自的覆盖顶点。找到大小相同的两者,就证明了两侧的最优性。亏量子集给出另一个上界,它指出了争夺过少邻点的那些请求。这些都是可检验的证书,而不是对搜索历史的诉诸。
覆盖、独立集与二部性的作用
顶点覆盖的补集是独立集:两个端点都在覆盖之外的边将不会被覆盖。反过来,独立集的补集覆盖每一条边。因此在任何有限图中,最大独立集的大小加上最小覆盖的大小等于顶点数。与 König 定理结合,这可以由一个匹配及其覆盖算出二部图中独立集的最优值。
这一推论并不能使独立集在所有图中都变得容易。覆盖与独立集互补的等式是普遍成立的,而覆盖大小与匹配大小相等则专属于二部图。把这两个适用范围区分开,可以防止把一个有效的等式用来把某种最优化方法推广到其假设之外。
常见错误
反例模式
匹配–覆盖等式在三角形上不成立
三角形的最大匹配大小为一,因为任意两条边都共享一个顶点。它的最小顶点覆盖大小为二:一个顶点会漏掉对边,而任意两个顶点则覆盖全部三条边。因此两个最优值不同。二部性对 König 等式是必要的,尽管每个匹配仍然受每个顶点覆盖所限制。
常见错误
(整体平衡不蕴含 Hall 条件)
Hall 条件要对待饱和一侧的每个子集进行检验。两部分大小相等、边的总数足够多或没有孤立顶点,都是不充分的。第二个例子中的亏量对没有孤立顶点,而且整侧邻点计数发现不了它。
常见错误
(顶点覆盖不是边覆盖)
顶点覆盖是与每条边相交的顶点集合;边覆盖则是与每个顶点相交的边集合。两者是不同的最优化问题。在边为 的路径上, 是大小为一的最小顶点覆盖,而每个边覆盖都需要两条边,因为 只在 上, 只在 上。
总结
增广通过交换交错边来修复匹配。对称差证明了不存在增广路径刻画了最大基数。在二部图中,交错可达性同时给出了 Hall 短缺的证据和与匹配同样大小的覆盖,从而以构造性的方式建立了 Hall 定理和 König 定理。
练习
快速检查
(对于左侧顶点 和右侧顶点 ,取边 。求一个最大匹配和一个最小顶点覆盖。)
给出大小相等的可行对象,作为最优性证书。
解答 · 答案
边 构成大小为三的匹配。整个右侧 是大小为三的覆盖,所以由匹配–覆盖界,两者都是最优的。特别地,没有匹配能饱和全部四个左侧顶点。子集 只有邻点 ,这证明了亏量为一。
快速检查
(如果一个二部图有饱和 的匹配,证明:删去一个左侧顶点及其匹配的右侧顶点后,所得的图仍有饱和剩余左侧的匹配。)
不要把它与删除任意一个右侧顶点混淆。
解答 · 答案
去掉与所选左侧顶点相关联的唯一匹配边。它的右端点就是被删去的右侧顶点,并且没有其他匹配边使用这两个端点中的任何一个。因此每个其他左侧顶点在剩余的图中都保留其原来的匹配边。这就构造出了所需的饱和匹配。删除一个无关的右侧顶点可能破坏另一条必要的边,因而不一定保持饱和。
快速检查
(给出一个两部分大小相等、没有孤立顶点、且没有完美匹配的二部图。)
用一个具体的 Hall 子集来解释失败的原因。
解答 · 答案
取 ,,边为 。每个顶点的度都为正,两个部分的大小都是三。然而 ,违反了 Hall 不等式。任何匹配对 至多有一条边,对 至多有一条边,所以大小至多为二; 达到了这个界。