动机
在二部图中,Hall 条件把选定的顶点集与其在另一侧的邻点集进行比较。一般图没有固定的两侧,奇圈使这种语言不再适用。一个奇分支不可能完全在其内部完成匹配。若要使其中不留下未匹配的顶点,它必须经由一条边与被删除的边界集相连。
这一观察给出完美匹配的一个必要条件。其充分性则远不那么直接:也许多个不同的奇分支障碍会相互作用。我们利用一个边极大的、没有完美匹配的图来证明不存在其他障碍。两条假想的额外边与一个交错圈论证迫使其余的分支具有非常刚性的形式。
本节在前面的二部图定理之外发展一般图的匹配理论。该证明是存在性论证;完整的多项式时间花朵(blossom)搜索算法与非二部图的加权匹配不在本节范围之内。
定义
定义 6.2.1
(完美匹配与奇分支障碍)
设 为有限简单无向图。匹配是没有公共端点的边的集合。若每个顶点都属于所选的某一条边,则称该匹配为完美匹配。空图具有空的完美匹配。以 表示最大匹配的大小,以 表示删除顶点集 后奇数阶连通分支的个数。
亏量表达式为 ,并定义
该最大值取自有限多个集合。由于空集给出非负值,所以它是非负的。所有候选值与 具有相同的奇偶性。
全邻顶点是与其他每个顶点都相邻的顶点。若一个图没有完美匹配,但添加任何一条缺失的边都会产生完美匹配,则称它是没有完美匹配的饱和图。任何没有完美匹配的图,只要在不产生完美匹配的前提下不断添加边,就能得到这样的图;有限性保证这一存在性构造会终止。
定理/命题
定理 6.2.2
(完美匹配的奇分支判别准则)
有限图具有完美匹配,当且仅当
该条件包括空集与全体原有顶点。特别地,它会强制要求阶数为偶数,而不是默默地假设阶数为偶数。
定理 6.2.3
(匹配亏量的精确公式)
对每个 阶有限图,
因此,奇分支个数超出被删顶点个数的最大值,恰好等于未匹配顶点个数的最小值,而不仅仅是一个下界。奇数阶图存在恰好漏掉一个顶点的匹配,当且仅当对每个 都有 。
定理 6.2.4
(饱和障碍的结构)
在没有完美匹配的饱和图中,设 为全邻顶点的集合。则 的每个连通分支都是完全图。如果这样的图同时满足奇分支条件,那么它的全邻顶点可以与奇分支配对,并且其余全邻顶点可以彼此配对,从而产生矛盾。
证明思路或证明
证明
(必要性、下界与奇偶性)
先证必要性。取任意一个完美匹配与任意被删除集合 。在 的每个奇分支中,并非所有顶点都能彼此匹配。至少有一条匹配边必须离开该分支。由于不同分支之间没有边,这条边的另一个端点属于 。不同的奇分支使用 中不同的顶点,因为匹配不会重复使用端点。因此奇分支的个数至多为 。
更一般地,在任何匹配中,至多有 个奇分支能向 发出一条所选的边。其余每个奇分支至少留下一个未匹配的顶点。所以每个匹配至少留下 个未匹配顶点。取最大值即得下界 。
奇偶性的结论成立,是因为各分支的阶数之和为 ,它模 2 等于奇分支的个数。因此对每个 , 与 具有相同的奇偶性。
交错圈结构引理
证明
(饱和图:全邻顶点与团)
设一个饱和图中有顶点 ,边 存在,但边 不存在。我们断言 必为全邻顶点。若不然,选取一个与 不相邻的顶点 。由于 与 相邻,这四个顶点互不相同。
添加 会产生完美匹配 ,并且它必须使用所添加的边。添加 会产生完美匹配 ,它同样必须使用所添加的边。把它们的并看作多重图,对共有的边保留两个带标记的副本。每个顶点各有来自两个匹配的一条边,所以这个并分解为偶圈,圈上的边在两个匹配之间交替出现。重复的公共边是一个两条边的圈。
如果这两条添加的边位于不同的交错圈中,则在含有 的圈上由 切换到 。这样去掉了 ,而没有引入 。 中不变的边与切换后的边都在原图中,由此得到一个被禁止的完美匹配。
因此两条添加的边位于同一个交错圈中。去掉这两条边。由于它们分属相反的匹配,圈分裂为两条路径,每条路径都有奇数个顶点。每条路径的一个端点来自 ,另一个端点来自 。特别地, 是其中一条路径的端点,而 中恰有一个是另一条路径的端点。
视情况用原有的边 或 连接这两个端点。从这两条路径中各删去被连接的端点后,每条路径剩下偶数个顶点,可沿其原有的边按相邻顺序两两配对。连同这条连接边与其他圈上的匹配边,这再次构成一个完全位于原图中的完美匹配。这一矛盾证明了断言。
现在令 为全体全邻顶点。若 的某个分支不是完全图,则该分支中两个不相邻顶点之间的最短路径一开始就有两条边 ,其端点 不相邻。它的中间顶点 不在 中,这与断言矛盾。因此每个这样的分支都是完全图。
证明透视
两条被禁止的额外边迫使出现一条可用的原有边
饱和性把每条缺失的边变成一个假想的完美匹配。它们的交错并集孤立出原图中唯一不可用的那些边。若它们位于不同的圈上,一次切换即可同时避开两者。若它们位于同一个圈上,去掉它们后得到这两条路径,而已知的两条边的构型提供一条交叉边,连接这两条路径的暴露端点。结构性结论来自对这两种情形的全面覆盖。
奇分支条件的充分性
证明
(把奇团匹配到全邻顶点集)
假设该条件成立,但不存在完美匹配。不断添加边,直到图成为没有完美匹配的饱和图。添加边保持该条件:对任何固定的删除集 ,新边要么位于某个分支内部,要么合并两个分支。合并两个奇分支使奇分支个数减少二;合并其他任意一对分支不会使其增加。
对这个扩充后的图应用结构引理。它的非全邻分支都是团。设其中有 个是奇数阶的。在全邻集合 处的条件说明 。利用全邻性,把每个奇团中的一个顶点与 中互不相同的顶点匹配。其余所有顶点在各团内部配对;偶数阶团在内部配对,不需要使用 。
该图的阶数为偶数,因为空集处的条件排除了任何奇分支。总阶数的奇偶性也就是 的奇偶性,因为只有奇团有贡献。因此 为偶数。尚未使用的全邻顶点构成一个该偶数阶的团,可以彼此配对。我们构造出了一个完美匹配,与没有完美匹配的饱和性矛盾。这就证明了充分性,从而证明了判别准则。
把障碍转化为精确亏量
证明
(添加 个全邻顶点)
令 ,添加 个新顶点,使它们彼此相邻,并与每个原有顶点相邻。把扩充后的图记为 。由已证明的奇偶性结论,其阶数 为偶数。我们对每个删除集 验证其奇分支条件。
若至少有一个新顶点保留下来,则所有保留的顶点位于同一个分支中。对非空的 ,其奇分支个数至多为一,因而至多为 。对空的 ,总阶数为偶数,故个数为零。若没有新顶点保留下来,把 写成全部 个新顶点连同原有顶点 。剩下的图是 ,而 的定义给出 。
判别准则给出 的一个完美匹配。删去其中的新顶点及其关联的所选边。至多有 个原有顶点失去伙伴,所以 中的这个匹配至多留下 个未匹配顶点。结合前面的下界,即证明了等式。当 时,同样的论证就是直接对 应用判别准则。
对于奇数阶图,每个候选亏量都是奇数,其最大值非负,故 。所述的近完美条件说明 ,因而等价于 ,由此完成该推论的证明。
存在性证明没有高效计算的内容
饱和论证需要判断每条可能添加的额外边是否产生完美匹配;它并没有给出回答这一问题的高效方法。同样,枚举每个删除集给出的是有限但指数级的检验。该等式是一个结构性的证书定理,而不是隐藏在存在性构造中的多项式时间匹配实现。
前面的二部图增广路径论证避开了部分这类困难,因为它的交错搜索具有固定的两侧结构。在一般图中,奇交错结构需要额外处理。这里的定理独立于任何此类实现来解释精确的障碍,并且提供了一种验证所给下界证书的方法:删去所列出的顶点并数出奇分支的个数。
例题详解
例题 6.2.5
(三个奇分支在偶数阶时阻碍完美匹配)
取三个互不相交的三角形与一个额外的枢纽顶点。把枢纽与每个三角形中选定的一个顶点相连,没有其他的跨边。共有十个顶点。删去枢纽后留下三个奇分支,所以条件不成立,因为三大于一。
存在大小为四的匹配:把枢纽与某个三角形中的一个顶点匹配,把该三角形的另外两个顶点配成一对,并在其余每个三角形内部各取一条边。它留下两个未匹配的顶点。删去枢纽给出亏量二,而所给出的匹配说明不可能出现更强的下界。因此最大匹配大小恰好为四,尽管每个顶点的度数至少为二。
例题 6.2.6
(奇圈恰好有一个未匹配顶点)
在按循环顺序排列的五圈顶点 上,选取 与 ,留下一个未匹配顶点。空删除集给出一个奇分支,因而亏量至少为一。匹配下界的论证同时说明,每个亏量表达式至多等于该匹配中那一个未匹配顶点。
因此 ,并且该匹配是最大的。奇数阶阻止了完美性,但并不迫使有三个或更多未匹配顶点。精确亏量定理刻画了这一区别。
例题 6.2.7
(偶数阶完全图满足每个删除检验)
在 中,删除 后留下阶数为 的团。当该阶数为正且为奇数时它有一个奇分支,否则有零个。若 为空,则个数为零;若 非空,则个数至多为一,因而至多为 。
条件成立,并且两条互不相交的边给出一个完美匹配。该图含有三角形,所以非二部性本身并不构成障碍。相关的条件涉及的是删除之后的奇分支,而不是原图中是否没有奇圈。
概念视角组合
每个奇分支都需要一个不同的边界伙伴,否则就有一个未匹配顶点
若一个奇分支的所有匹配边都留在其内部,则它有一个奇偶亏欠。一个被删除的顶点至多吸收一个这样的亏欠。在所有边界上取超出量的最大值,就得到不可避免的未匹配顶点的精确个数。充分性的证明表明,一旦所有这些奇偶性需求都得到满足,就不再有隐藏的额外亏欠。
常见错误
反例模式
总阶数为偶数并不能抵消分离的奇需求
三叶星图有四个顶点,但删去其中心后留下三个奇数阶的单点分支,而只有一个被删顶点可供它们使用。其最大匹配只有一条边,留下两个未匹配顶点。仅有偶数阶不能取代奇分支条件。
常见错误
(奇圈不是奇分支)
不要把奇圈当作奇连通分支来计数。偶数阶团含有许多奇圈,却仍有完美匹配; 通过每一个删除检验。
常见错误
(高度数或连通性不能防止亏量删除)
不要以为较高的最小度或连通的原图就能防止一个小的删除集暴露出若干彼此独立的奇需求。三个三角形接到一个中心顶点的图连通且最小度为二,但只删去中心就留下三个奇分支,迫使两个顶点未被匹配。
总结
奇分支对任何匹配给出必要的奇偶性需求。饱和障碍论证证明,满足所有这些需求对于存在完美匹配是充分的。再添加全邻顶点,就把判别准则转化为未匹配顶点个数的精确公式。这些结构性证明给出完整的证书,而高效的一般匹配搜索则留作另一个独立的算法任务。
练习
快速检查
(求两个三角形的不交并的最大匹配与精确亏量。)
利用空删除集与一个具体给出的匹配,从两侧界定同一个量。
解答 · 答案
空集暴露出两个奇分支,所以每个匹配至少留下两个未匹配顶点。在每个三角形中各选一条边,得到两条边,恰好留下两个未匹配顶点。因此 且 。在图中从概念上把这两个分支连起来会改变这个图;它们各自分离的奇需求无法共用一条并不存在的匹配边。
快速检查
(对有四片叶子的星图,求一个达到最大亏量的删除集,并解释为什么添加三个全邻顶点后,扩充图就有完美匹配。)
先把中心与某一片叶子配对,再分配其余的叶子。
解答
删去中心后留下四个奇数阶的单点分支,超出量为 。单独一条从中心到叶子的边就是最大匹配,因为所有边都共用中心,它留下三个未匹配顶点。因此最大亏量恰好为三。
添加三个全邻顶点。把中心与一片原有的叶子匹配,并把每个新顶点与一片不同的剩余叶子匹配。这四条边覆盖全部八个顶点。去掉新顶点后,恰好剩下原来的单边匹配,这说明了亏量证明,而不需要任何新顶点之间的所选边。
快速检查
(直接从完美匹配判别准则证明:奇数阶图存在漏掉一个顶点的匹配,当且仅当添加一个全邻顶点后得到完美匹配。)
考察新顶点的伙伴,并利用原图的近完美不等式验证判别准则。
解答
漏掉一个顶点的匹配,可以通过把该顶点与新的全邻顶点配对而扩充为完美匹配。反过来,从完美匹配中删去新顶点;它在原图中的那个伙伴变成未匹配的,而其他所有原有顶点仍保持匹配。
对于判别准则,设对每个原有的 都有 。在扩充图中,包含新顶点的删除集留下 ,其大小为 ,所以满足条件。若新顶点保留下来,则剩下的图是连通的;非空的删除集至多允许一个奇分支,而空的删除集留下偶数总阶数。因此每个删除集都满足判别准则,从而得到所述的完美匹配,进而得到原图的近完美匹配。