0004: 图匹配和增广路的定义与性质简述

· · 算法·理论

0004: 图匹配和增广路的定义与性质简述

本篇为图匹配系列的第 1 篇, 关于本系列详见0000: 博客目录.

1. 图的匹配

匹配, 又称独立边集, 是指一张无向图中不具有公共点的边的集合. 在本篇中我们给出图匹配以及与之有关的增广路 (不是网络流中的增广路) 的相关定义, 也给出增广路定理的相关说明.

在无向图 G=(V,E)中, V 是点集, E 是边集. 我们称 M 是 G 的一个匹配, 当且仅当 M\subseteq E 且 M 中的任意两条边均没有公共点. 我们称匹配 M 的大小 |M| 为 M 中边的数量, 而且有 |M|\le\frac{|V|}2 (抽屉原理).

对于边 \langle u,v\rangle\in M, 我们称 \langle u,v\rangle 为匹配边, 反之为未匹配边. 我们称点 u, v 为匹配点, 反之为未匹配点.

1.1 特殊的匹配

一张二分图上的匹配称为二分匹配.

1.2.1 二分图的完美匹配

设 G=\langle V_1, V_2, E \rangle 为二分图, |V_1| \leq |V_2|, M 为 G 中一个最大匹配, 且 |M|=|V_1|, 则称 M 为 V_1 到 V_2 的完美匹配.

定理4.1 霍尔定理 Hall marriage theorem

设二分图 G=\langle V_1, V_2, E \rangle, |V_1| \leq |V_2|, 则 G 中存在 V_1 到 V_2 的完美匹配当且仅当对于任意的 S \subseteq V_1 , 均有 |S|\leq|N(S)|. 其中 N(S)=\cup_{v_i \in S}{N(v_i)} 是 S 的邻域, N(v_i) 指 v_i 的相邻点, 所以有 N(S)\subseteq V_2 (二分图的定义).

证明

先证必要性: 若对于任意的 S \subseteq V_1, 均有 |S|\leq|N(S)|, 则 G 中存在 V_1 到 V_2 的完美匹配.

我们使用数学归纳法证明.

对于 |V_1|=1 的二分图显然成立.

对于 |V_1|=n 的二分图, 我们设所有 |V_1|<n 的二分图均已被证明. 然后, 我们设点 u\in V_1 与点 v\in V_2 匹配, 也就相当于在 G 上删除点 u 和 v, 从而得到新的二分图 G'=\langle V_1-\{u\},V_2-\{v\},E-\{\langle u',v'\rangle|\langle u',v'\rangle\in E,u'=u\text{或}v'=v\}\rangle, 设图 G 上点 i 的相邻点为 N'(i). 我们发现 |V_1-\{u\}|<n, 所以如果我们能证明对于任意的 S\subseteq V_1-\{u\} 均有 |S|\le|N'(S)| 成立, 则霍尔定理的必要性得证.

令 \displaystyle D=\cup_{S\subseteq V_1-\{u\},|S|=|N(S)|}S, 则 v 不能属于 N(D), 否则会出现 |S|=|N(S)|>|N(S)-\{v\}|=|N'(S)| 的情况. 相反的, 若 v\notin N(D), 则对于任意的 S\subseteq V 且 v\in N(S), 一定有 |S|<|N(S)|=|N(S)-\{v\}|+1\Rightarrow|S|\le|N(S)-\{v\}|.

那会不会出现 N(u)\subseteq N(D) 的情况? 我们可以发现一定有 |D|=|N(D)|(见下方引理4.2的证明), 所以若 N(u)\subseteq D, 则 |D\cup\{u\}|>|D|=|N(D)|=|N(D\cup\{u\})|, 形成矛盾, 从而证毕.

再证充分性: 若 G 中存在 V_1 到 V_2 的完美匹配, 则对于任意的 S \subseteq V_1, 均有 |S|\leq|N(S)|.

反证: 设 G 中存在 V_1 到 V_2 的完美匹配 M, 且存在 S\subseteq V_1 有 |S|>|N(S)|.

根据反证假设, M 中包含 S 中的点的边定然有 |S| 条, 而这 |S| 条边的端点都在 N(S) 中. 根据鸽巢原理, N(S) 中定然有点为匹配中两条以上边的公共端点, 与反证假设矛盾.

引理4.2 张三引理

对于二分图 G=\langle V_1, V_2, E \rangle, |V_1| \leq |V_2|, 且对于任意的 S \subseteq V_1 , 均有 |S|\leq|N(S)|. 则对于 S_1,S_2\subseteq V_1, 若 |S_1|=|N(S_1)| 且 |S_2|=|N(S_2)|, 则 |S_1\cup S_2|=|N(S_1\cup S_2)|.

证明

因为 |S_1\cup S_2|=|S_1|+|S_2|-|S_1\cap S_2|, 又有 |N(S_1\cup S_2)|\le|N(S_1)|+|N(S_2)|-|N(S_1\cap S_2)|\le|S_1|+|S_2|-|S_1\cap S_2|, 将式子连起来, 有 |S_1\cup S_2|\ge|N(S_1\cup S_2)|, 而这个式子只能取等, 得证.

2. 匹配的转换

2.1 以最大权最大匹配求最大权匹配

2.1.1 算法思路

最大权最大匹配允许负权边的存在(因为要保证匹配数最大), 而最大权匹配不允许(删掉负权边显然可以让权值和更大, 所以若所有边均为负权, 则最大权匹配为 \varnothing). 接下来我们引入匹配的完全图性质以进行求解

性质4.3 匹配的完全图性质

当图 G 为完全图且没有负边权时, 最大权最大匹配=最大权匹配.

证明

因为 G 是完全图, 所以任意一个非最大匹配均可以通过增加边变成最大匹配. 而 G 又没有负权边, 所以 G 的最大权匹配定为最大匹配或删去几条权为 0 边后的最大匹配, 否则一定可以通过增加权非 0 的边以使权值和增加.

2.1.2 算法流程

由于权值为 0 的边对最大权匹配没有影响, 所以我们可以把原图的所有负权边变为零边(反正本来也要将负权边删去), 然后用权为 0 的边将原图补为完全图, 此时用最大权最大匹配求解的结果即为原图的最大权匹配结果.

2.2 以最大权匹配求最大权最大匹配

2.2.1 算法思路

我们首先为原图的所有边加上一个数 K, 使得图上不存在负权边和零边. 再将所有边加上一个足够大的数 P, 消除原权值对匹配的大小的影响, 让匹配数小但原权值和大的匹配劣于匹配数大但原权值和小的匹配.

2.2.2 算法流程

令 K=\max\{|w(e)|:e\in E, w(e)\leq0\}+1, 若没有负边权和零边则 K=0. 然后令 P=\sum_{e\in E} w(e)+K, 最后将每条边的权值增加 K+P, 此时的最大权匹配结果就对应原图的最大权最大匹配结果.

3. 增广路

3.1 增广路定义

我们称一条由未匹配边和匹配边交错而成的路径为交错路(Alternating path).

我们称一条始于未匹配点且终于未匹配点(不是起始的未匹配点)的交错路为增广路(Augmenting path).

3.2 增广操作

我们发现增广路的第一条边和最后一条边均为未匹配边(因为起点和终点均为未匹配点), 又是由未匹配边和匹配边交错而成的, 所以其包含的边数为奇数.

我们可以将增广路上的匹配边和未匹配边反转, 从而使匹配数增加 1, 同时依然是一个合法的匹配(因为只是将增广路的起点和终点变为匹配点), 这个操作被称为增广(Augment), 这是匈牙利算法增加匹配数量的唯一方式. 操作过程如下图:

定理4.4 增广路定理 Berge's lemma

图 G=(V,E) 的匹配 M 是最大匹配当且仅当无法找到增广路.

证明

先证必要性:

反证: 设 M 是图 G 的最大匹配, 且存在一条增广路.

我们可以对这条增广路进行增广, 从而使 M 的大小增加, 与反正假设矛盾.

再证充分性:

反证: 对于匹配 M 在图 G 上找不到增广路, 且有一个更大的匹配 M', 有 |M|<|M'|.

我们构造图 H=(V,(M\cup M')-(M\cap M')), 即每条边要么属于 M, 要么属于 M', 而且每个点的度均小于等于 2.

由于每个点的度均小于等于 2, 所以 H 上的联通块只会有三种情况: 孤立点, 环和链. 如下图:

对于环, 我们发现在任意环上都是 M 中的边和 M' 中的边交替出现, 这是因为每个点只可能最多有一条 M 的边和一条 M' 中的边, 从而我们发现环上的 M 中边的数量等于 M' 中边的数量.

对于链, 由于|M|<|M'|, 所以一定会出现至少一条链, 而且链上也是两种边交替出现. 还是因为 |M|<|M'|, 一定会出现一条首尾均为 |M'|中的边的链, 而这条链就是原图上的一条增广路, 与反证假设矛盾, 从而得证.

3.3 利用增广操作求解最大匹配

根据定理4.4可知我们求最大匹配的核心思路: 枚举所有未匹配点, 找增广路径并增广, 直到找不到增广路径.

事实上, 对于每个点只要枚举一次就好.

证明

因为增广操作每次只会使得两端的未匹配点变成匹配点, 不会出现增广后有匹配点变成未匹配点的情况, 所以每个点作为未匹配点只需要增广一次.

3.4 交错树

我们将从未匹配点 r 进行 DFS 或 BFS 寻找增广路的过程中产生的树称为交错树, r 是交错树的根.

我们称偶点(黑点)为树上深度为偶数的点. 奇点(白点)为树上深度为奇数的点. 下图展示了一个二分图从未匹配点 1 开始寻找增广路时, 形成的以 1 为根的交错树.

4. 参考资料

  1. 图匹配 OI-wiki
  2. 增广路 OI-wiki
  3. 图论学习笔记（4）- 匹配 Matchings 知乎
  4. Wisdommmmmmmm 在参考资料1下的评论
  5. 图匹配学习 CSDN博客