形式陈述
设 G = ( V , E ) 是有限简单无向图 理路 有限简单无向图 Graph · Finite simple undirected graph · 图 由有限顶点集与无序二元顶点子集组成的边集所确定的简单无向图。 。边集的子集 理路 子集 Subset · Set inclusion A 的每个元素都属于 B 时成立的包含关系;它在集合之间形成偏序。 M ⊆ E 称为一个匹配 ,若任意两条不同的 e , f ∈ M 没有公共端点。属于某条匹配边的顶点称为被 M 饱和 ,其余顶点称为未饱和或暴露顶点。
匹配有三种常被混淆的最优性:
M 是极大匹配 ,若不存在严格包含 M 的匹配;
M 是最大匹配 ,若 | M | 在所有匹配中最大;
M 是完美匹配 ,若每个顶点都被 M 饱和。
最大匹配的大小记为
是 匹 配 ν ( G ) = max { | M | : M ⊆ E 是匹配 } . 最大匹配一定极大,完美匹配一定最大;两个反向命题一般都不成立。完美匹配含 | V | / 2 条边,所以它只能出现在偶数阶图中,但偶数阶并不保证存在完美匹配。
相对于匹配 M ,边在 E ∖ M 与 M 之间交替、长度为正且两个不同端点均未饱和的路径 理路 路与圈 Path and cycle in a graph 用相邻顶点序列刻画图中的行走、简单路径与首尾闭合的简单圈。 称为 M -增广路。单个未饱和顶点不能充当增广路。若 P 是增广路,则
M ′ = M △ E ( P ) 仍是匹配,而且 | M ′ | = | M | + 1 。Berge 定理进一步断言:M 最大,当且仅当不存在 M -增广路。
证明反方向时,把 M 与一个更大匹配 N 作对称差 理路 集合运算 Set operations · Union, intersection, difference 用逻辑条件逐元素定义并、交、差、补与对称差,并扩展到集合族。 。所得子图中每个顶点度数至多为二,因而分解成交替圈与交替路径;由于 N 边总数更多,至少一个路径分量含有比 M 边多一条的 N 边,它正是一条 M -增广路。
直觉
匹配选择若干条互不争用端点的边,每个顶点最多参与一次配对。直接添加一条边只会检测当前还有没有两个同时空闲的端点,这对应极大性;增广路允许先解除部分旧配对、再沿交替链重新安排,因而能发现被局部选择遮住的全局改进。
对称差翻转为何保持可行,可以逐点查看。增广路内部每个顶点失去一条旧匹配边,同时获得一条新匹配边;两个端点原本未饱和,各自只获得一条边。冲突没有增加,匹配规模却净增一。
例子与边界
在四点路径 v 1 v 2 v 3 v 4 中,单边集合 { v 2 v 3 } 已经极大:剩余两条边都碰到它的端点。但它不是最大,路径
v 1 , v 2 , v 3 , v 4 相对于该匹配交替且两端未饱和。翻转后得到 { v 1 v 2 , v 3 v 4 } ,这是大小为二的完美匹配。
任取一个极大匹配 M ,其规模至少为最大匹配的一半。设 M ⋆ 最大;极大性保证 M ⋆ 中每条边至少碰到一条 M 边,否则还可直接加入。每条 M 边只有两个端点,至多被两条 M ⋆ 边这样归属,所以
| M ⋆ | ≤ 2 | M | . 四点路径的中间边达到这个界,说明“随便取极大匹配”只保证二分之一近似,不能冒充精确算法。
空集总是匹配。孤立点不妨碍普通匹配,却会阻止完美匹配。最大匹配可能有多个,ν ( G ) 只记录共同的最优大小。若边带收益,最大权与最大基数不再相同:给四点路径的中间边权重 10 、两条外边各权重 4 ,最大权匹配只选中间边,权重为 10 ;最大基数匹配选两条外边,权重只有 8 。因此“先最大化边数,再最大化权重”也是另一个目标,必须另行说明。
普通匹配要求每个顶点容量为一。任务可由多台相同机器承接时需要 b -matching;医院—住院医问题还包含容量与偏好顺序;指派问题通常要求二分、带权并饱和两侧。它们都从配对出发,却不是删几个形容词便可互换的同一问题。
推论与应用
增广路 理路 增广路 Augmenting path 相对于当前匹配,边在未匹配与已匹配之间交替且两个端点均未匹配的路径。 把最大性转化为可搜索的证书。二分图的交替搜索没有奇圈干扰,Hopcroft–Karp 算法 理路 Hopcroft–Karp 算法 Hopcroft-Karp algorithm 按阶段同时增广一族顶点不交的最短增广路,以包含孤立点读取成本的 O(V+E√V) 时间求二分图最大匹配。 可按最短增广路分层并批量推进;一般图中的奇交替圈需要Edmonds blossom 算法 理路 Edmonds blossom 算法 Edmonds' blossom algorithm · Blossom algorithm 通过识别并收缩奇交替环,在一般图中保持增广路存在性并求最大匹配的算法。 收缩后再展开。
另一条代数路线是Tutte矩阵 理路 Tutte矩阵 Tutte matrix · 图匹配的Tutte矩阵 以反对称边变量矩阵编码一般图完美匹配,证明随机行列式判定,并用隔离权与二进阶主子式提取可验真匹配。 :为每条无向边放入一个反对称变量,形式行列式非零当且仅当存在完美匹配;随机代入后的非零值给存在性证据。配合隔离引理 理路 隔离引理 Isolation lemma · Isolating lemma · MVV isolation lemma 给固定集合族的元素独立赋小整数权,以元素阈值和并集界保证唯一最小解,并区分隔离存在性与求解能力。 及整数二幂代入,可由删两端点的主子式筛出实际边集,再逐端点验真;随机失败不等于确定不存在,也没有替代本页的一般最大匹配目标。
在二分图 理路 二分图 Bipartite graph 顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。 中,Hall 定理 理路 Hall 婚配定理 Hall's marriage theorem 有限二分图存在饱和一侧的匹配,当且仅当每个该侧顶点子集的邻集至少同样大。 刻画饱和指定一侧的匹配何时存在,Kőnig 定理 理路 Kőnig 二分图定理 Kőnig's theorem for bipartite graphs 二分图中最大匹配大小等于最小顶点覆盖大小。 给出
ν ( G ) = τ ( G ) , 其中 τ ( G ) 是最小顶点覆盖 理路 顶点覆盖 Vertex cover 与图中每条边至少一个端点相交、从而覆盖全部边的顶点子集。 大小。一般图始终只有 ν ( G ) ≤ τ ( G ) ;三角形以 1 < 2 说明二分假设不可省略。
二分匹配的网络流归约 理路 经由网络流的二分图匹配 Bipartite matching via maximum flow 用单位容量流求二分图匹配,并从终态搜索同时提取 Hall 障碍、等值割和最小顶点覆盖。 把每条可选配对设为单位容量弧,适合无权最大基数目标。匈牙利算法 理路 匈牙利算法 Hungarian algorithm 通过对偶标号和增广结构求解赋权二分图完美匹配的算法。 处理带成本的二分指派,并利用对偶势寻找最优完美匹配;它求解的是带权完美指派这一分支,不能直接替代本页的一般最大基数目标。
匹配还为顶点覆盖给出下界,并为边覆盖、路径覆盖与拟阵交提供交换结构。把应用归约到匹配之前,应先确认端点容量、图是否二分、是否要求完美以及目标是基数还是权重。
参考资料
Reinhard Diestel, Graph Theory , 5th ed., Springer, 2017, §2.1.
Douglas B. West, Introduction to Graph Theory , 2nd ed., Prentice Hall, 2001, Chapter 3.
László Lovász and Michael D. Plummer, Matching Theory , AMS Chelsea, 2009, Chapter 1.