图匹配
2026-08-12
定义
设 G=(V,E) 是一张无向图,如果一组边 M⊆E 不包含自环,且两两之间没有公共点,则称边集 M 为图 G 的一个匹配或独立边集,M 中的边称为匹配边,不在 M 中的边称为非匹配边,为匹配边端点的点称为匹配点,否则称为非匹配点。
对于一个匹配 M,若 ∣M∣ 最大,则称 M 为最大匹配(最大匹配不一定唯一)。
如果基于 M 不能再增加匹配边,则称 M 为极大匹配(不一定最大)。
如果 G 中的每个点都是匹配点,则称 M 为完美匹配。
对于 G 和他的匹配 M,我们可以定义如下两种路径:
- 交错路:有匹配边和非匹配边交错而成。
- 增广路:起始于非匹配点终止于非匹配点的交错路。
不难发现,增广路中非匹配点个数总是比匹配点个数多 1,如果我们让匹配点变成非匹配点,非匹配点变成匹配点,其仍是交错路,并且 ∣M∣ 会增加 1,我们称这个过程为增广。
对于两个匹配 A 和 B,定义其对称差为 A⊕B=(A∪B)\(A∩B),即两个匹配的不同部分。
Berge 引理
Berge 引理的内容如下:
对于图 G=(V,E) 和他的一个匹配 M,匹配 M 为最大匹配,当且仅当不存在相对于 M 的增广路。
证明
假设现在有两个匹配 M,M′,使得 M′>M,考虑证明一定存在增广路。
观察 M⊕M′ 的构成:由于一个点度数最多为 2,所以只能由 M 和 M′ 的边构成路径或者环。
对于环,它对 M 和 M′ 贡献相同,不考虑,同样的,我们也不考虑头尾点不同的路径。
现在只剩下两种路径:两头都是 M 的和两头都是 M′ 的。
由于 M′>M,一定存在一个路径两头都是 M′,容易发现,这个路径就是 M 的一个增广路。
