9.2 边覆盖集与匹配

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【定义9.2.1:边覆盖】设无向简单图 无孤立点。边集 若使每个顶点至少关联一条 中的边,称边覆盖。不能再删边者称极小边覆盖;边数全局最少者称最小边覆盖,其大小为 。若存在孤立点,无论选多少边都覆盖不了它,所以不存在边覆盖,不可把此时的边覆盖数误记为0。

e1e2e3e4e5e6e7
图9.2.1(a):六点七边,边号e1至e7分别保留

图(a)中 与 都是极小边覆盖,前三边组成的集合最小,。大小3的下界来自一条边最多覆盖两个顶点,六点至少要3边。

e1e2e3e4e5e6e7e8
图9.2.1(b):五点八边,右端顶点仍须被覆盖

图(b)中 、 都是最小边覆盖,;五点不可能只用两条边全部覆盖。

【定义9.2.2:匹配与边独立数】边集 中任意两条边都没有共同端点,称匹配,也称边独立集。再加入任一其他边都会破坏条件,称极大匹配;全图所有匹配中边数最多者称最大匹配,其大小为 。极大匹配可能通过同时移去和加入多条边而得到更大的匹配,所以“不能直接再加一条边”并不等于最大。

图(a)的 都极大,最后一集最大,。图(b)的 都是最大匹配,,因为五点不可能容纳三条互不共端点的边。

【定义9.2.3:饱和、完美与增广】匹配中的边称匹配边,其余为非匹配边。匹配边的端点称饱和点,其余点称非饱和点。所有顶点均饱和的匹配称完美匹配,必有 。沿路径的边交替属于和不属于 ,称交错路径;若两个不同端点都非饱和,则称增广路径。交替出现匹配边和非匹配边的圈称交错圈。

图(a)的 完美,也为最小边覆盖。图(b)的 最大但不完美,右端一点未饱和,分别加 中任一条,就得到一个最小边覆盖。反过来,最小边覆盖 中,删去 或 后都得到大小2的最大匹配。

【定理9.2.1:最小边覆盖与最大匹配】无孤立点的 阶图满足以下三点。

第一,从任一最大匹配 出发,为每个非饱和点选一条关联边,加入后得到最小边覆盖。第二,从任一最小边覆盖出发,反复删除相邻边中的一条,直到剩下的边两两不相邻,得到最大匹配。这里要一直做至无相邻边,不能把“一般只删一条”当成算法。第三,

补全证明:最大匹配的任意两个非饱和点之间都没有边,否则可直接增大匹配。因此为不同非饱和点选取的边互不相同,也不属于 ,所构造边覆盖的大小为 。

再取最小边覆盖 。若其中某条边的两端各自还关联 的其他边,则可删除该边而仍覆盖所有顶点,矛盾。所以由 组成的子图,每个连通分支都是至少含一条边的星;不可能含圈或长度3的路径。设星分支数为 ,每个分支边数比顶点数少1,故 。每个星中反复删除相邻边,最后恰留一边,得到大小 的匹配,因此 ,从而

各项相等,第一种构造达到最小值,第二种构造达到最大值,并得到恒等式。对照两例,图(a)有 ,图(b)有 。

【推论9.2.1】任一匹配 和任一边覆盖 都满足 。因为 、。若两者相等,则 为偶数,两者大小都等于 ,故 完美, 最小。此处比较的是一组边的基数,不是要求 。

e1e2e3e4e5e6e7e8
图9.2.2(a):六点八边的原图
e1e2e3e4e5e6e7e8
图9.2.2(b):实线匹配M1={e3,e7},其他边为虚线
e1e2e3e4e5e6e7e8
图9.2.2(c):沿增广路径翻转后,实线M2={e2,e4,e6}

图中的 不是最大匹配。增广路径依次经过 ,以非匹配边开始和结束,含3条非匹配边、2条匹配边。翻转后得到 ,比原来多1条边,并覆盖全部六点。边 不在这条增广路径上,不参加翻转。

【定理9.2.2:增广路径判据】匹配 最大,当且仅当不存在关于 的增广路径。若存在增广路径 ,对其边作对称差

仍为匹配,且 ,故原匹配不最大。

反过来,若有更大匹配 ,考虑由 中的边组成的子图。每个顶点度至多2,非平凡分支是交错路径或偶交错圈。圈上两种匹配边数相同;路径上至多相差1。由于 ,至少一条路径上的 边比 边多1,该路径的两个端点对 均未饱和,正是 的增广路径,矛盾。这里取的是边集生成的子图,不是把这些端点间原图的其他边也一并添进来。