一般图最大匹配
带花树算法（Blossom Algorithm）
开花算法（Blossom Algorithm，也被称做带花树）可以解决一般图最大匹配问题（maximum cardinality matchings）．此算法由 Jack Edmonds 在 1961 年提出． 经过一些修改后也可以解决一般图最大权匹配问题． 此算法是第一个给出证明说最大匹配有多项式复杂度．
一般图匹配和二分图匹配（bipartite matching）不同的是，图可能存在奇环．
以此图为例，若直接取反（匹配边和未匹配边对调），会使得取反后的 𝑀M
不合法，某些点会出现在两条匹配上，而问题就出在奇环．
下面考虑一般图的增广算法． 从二分图的角度出发，每次枚举一个未匹配点，设出发点为根，标记为 「o」 ，接下来交错标记 「o」 和 「i」 ，不难发现 「i」 到 「o」 这段边是匹配边．
假设当前点是 𝑣v，相邻点为 𝑢u，可以分为以下两种情况：
- 𝑢u 未拜访过，当 𝑢u 是未匹配点，则找到增广路径，否则从 𝑢u 的配偶找增广路．
- 𝑢u 已拜访过，遇到标记「o」代表需要 缩花 ，否则代表遇到偶环，跳过．
遇到偶环的情况，将他视为二分图解决，故可忽略．缩花 后，再新图中继续找增广路．
设原图为 𝐺G，缩花 后的图为 𝐺′G′，我们只需要证明：
- 若 𝐺G 存在增广路，𝐺′G′ 也存在．
- 若 𝐺′G′ 存在增广路，𝐺G 也存在．
设非树边（形成环的那条边）为 (𝑢,𝑣)(u,v)，定义花根 ℎ =𝐿𝐶𝐴(𝑢,𝑣)h=LCA(u,v)． 奇环是交替的，有且仅有 ℎh 的两条邻边类型相同，都是非匹配边． 那么进入 ℎh 的树边肯定是匹配边，环上除了 ℎh 以外其他点往环外的边都是非匹配边．
观察可知，从环外的边出去有两种情况，顺时针或逆时针．
于是 缩花 与 不缩花 都不影响正确性．
实作上找到 花 以后我们不需要真的 缩花 ，可以用数组纪录每个点在以哪个点为根的那朵花中．
复杂度分析 Complexity Analysis
每次找增广路，遍历所有边，遇到 花 会维护 花 上的点，𝑂(|𝐸|2)O(|E|2)．
枚举所有未匹配点做增广路，总共 𝑂(|𝑉||𝐸|2)O(|V||E|2)．
参考代码
参考代码
---|---
[UOJ #79. 一般图最大匹配](https://uoj.ac/problem/79)
---|---
基于高斯消元的一般图匹配算法
提示
在阅读以下内容前，你可能需要先阅读「线性代数」部分中关于矩阵的内容：
这一部分将介绍一种基于高斯消元的一般图匹配算法．与传统的带花树算法相比，它的优势在于更易于理解与编写，同时便于解决「最大匹配中的必须点」等问题；缺点在于常数比较大，因为高斯消元的 𝑂(𝑛3)O(n3) 基本是跑满的，而带花树一般跑不满．
前置知识：Tutte 矩阵
定义 ：对于一张 𝑛n 个点的无向图 𝐺 =(𝑉,𝐸)G=(V,E)，其 Tutte 矩阵 ˜𝐴(𝐺)A~(G) 为一个 𝑛 ×𝑛n×n 的矩阵，其中：
˜𝐴(𝐺)𝑖,𝑗=⎧{ {⎨{ {⎩𝑥𝑖,𝑗,𝑖<𝑗,(𝑣𝑖,𝑣𝑗)∈𝐸−𝑥𝑖,𝑗,𝑖>𝑗,(𝑣𝑖,𝑣𝑗)∈𝐸0,otherwiseA~(G)i,j={xi,j,i<j,(vi,vj)∈E−xi,j,i>j,(vi,vj)∈E0,otherwise
其中 𝑥𝑖,𝑗xi,j 是一个变量，因此 ˜𝐴(𝐺)A~(G) 中共有 |𝐸||E| 个变量．
在无歧义的情况下，以下将 ˜𝐴(𝐺)A~(G) 简写为 ˜𝐴A~．
定理 （Tutte 定理）：𝐺G 存在完美匹配当且仅当 det˜𝐴 ≠0detA~≠0．
证明
这里引入「偶环覆盖」的概念：一个无向图 𝐺G 的偶环覆盖指用若干偶环（包括二元环）不重不漏地覆盖所有的点．
易证 𝐺G 存在完美匹配当且仅当 𝐺G 存在偶环覆盖．
- 如果 𝐺G 存在偶环覆盖，我们只需要在每个环都隔一条取一条边，就可以得到一个完美匹配．
- 如果 𝐺G 存在完美匹配，我们只需要将匹配边对应的二元环取出，就可以得到一个偶环覆盖．
然后证明 𝐺G 存在偶环覆盖当且仅当 ˜𝐴 ≠0A~≠0．
考虑行列式的定义
det𝐴=∑𝜋(−1)𝜋∏𝑖𝐴𝑖,𝜋𝑖detA=∑π(−1)π∏iAi,πi
其中 𝜋π 是任意排列，( −1)𝜋(−1)π 表示若 𝜋π 中的逆序对数为奇数，则取 −1−1，否则取 11．
不难看出每个排列都可以被看作 𝐺G 的一个环覆盖．如果这个环覆盖中存在奇环，则将这个环翻转后的和一定为 00，因此只有偶环覆盖才能使行列式不为 00，证毕．
定理 ：rank˜𝐴rankA~ 一定为偶数，并且 𝐺G 的最大匹配的大小等于 rank˜𝐴rankA~ 的一半．
证明
反对称矩阵的秩只能是偶数；后者请读者自行思考．
实际应用中不可能带着 |𝐸||E| 个变量进行计算，不过可以取一个数域，例如取某个素数 𝑝p 的剩余系 Z𝑝Zp，将变量分别随机替换为 Z𝑝Zp 中的数，再进行计算．方便起见，在无歧义的情况下，以下用 ˜𝐴A~ 直接指代替换后的矩阵．
定理 ：rank˜𝐴rankA~ 至多为 𝐺G 的最大匹配大小的两倍，并且二者相等的概率至少为 1 −𝑛𝑝1−np．
考虑到一般图最大匹配中 𝑛n 基本不会超过 103103，实际中 𝑝p 取 109109 数量级的素数就足够了．
由定理可知，如果只需要求最大匹配数，而无需匹配方案，那么只需要用一次高斯消元求出 rank˜𝐴rankA~ 即可，远比带花树简洁．不过如果需要输出方案，会稍微复杂一些，需要用到下面介绍的算法．
构造完美匹配
由 Tutte 定理和上面的定理可知，如果 𝐺G 存在完美匹配，那么 ˜𝐴A~ 有很大概率满秩．方便起见，以下叙述中均省略「有很大概率」．
记 𝐺G 中标号为 𝑖i 的点为 𝑣𝑖vi，进一步地我们有如下定理：
定理 ：˜𝐴−1𝑗,𝑖 ≠0 ⟺ 𝐺 −{𝑣𝑖,𝑣𝑗}A~j,i−1≠0⟺G−{vi,vj} 有完美匹配．
逆矩阵与伴随矩阵
对任意 𝑛n 阶方阵 𝐴A，定义其伴随矩阵为 𝐴∗𝑖,𝑗 =( −1)𝑖+𝑗𝑀𝑗,𝑖Ai,j∗=(−1)i+jMj,i，其中 𝑀𝑗,𝑖Mj,i 为删去第 𝑗j 行第 𝑖i 列的余子式．换言之，设 𝐴A 的代数余子式矩阵为 𝑀M，则 𝐴∗ =𝑀𝑇A∗=MT．
定理 ：如果 𝐴A 可逆，那么 𝐴−1 =1det𝐴𝐴∗A−1=1detAA∗．
所以这里的 𝐴−1𝑗,𝑖 ≠0 ⟺ 𝑀𝑖,𝑗 ≠0Aj,i−1≠0⟺Mi,j≠0，也就是 𝐴A 删去第 𝑖i 行第 𝑗j 列后的部分满秩．
换言之，如果 (𝑣𝑖,𝑣𝑗) ∈𝐸(vi,vj)∈E，并且 ˜𝐴−1𝑗,𝑖 ≠0A~j,i−1≠0，就表明存在一个完美匹配方案包含 (𝑣𝑖,𝑣𝑗)(vi,vj) 这条边．以下将这种边称为 可行边 ．
由如上定理，对于一个有完美匹配的无向图 𝐺G，我们可以得到一个比较显然的暴力算法来寻找一组完美匹配：每次枚举 𝑖,𝑗i,j，如果 (𝑣𝑖,𝑣𝑗)(vi,vj) 是一条可行边（连边存在，并且 ˜𝐴−1𝑗,𝑖 ≠0A~j,i−1≠0），就将 (𝑣𝑖,𝑣𝑗)(vi,vj) 加入匹配方案，并在 𝐺G 中都删掉这两个点，再重新计算新的 ˜𝐴−1A~−1．
总共要做 𝑛2n2 轮，每轮都是 𝑂(𝑛3)O(n3) 的，总的复杂度是 𝑂(𝑛4)O(n4)，有点慢了．实际上我们在重新计算 ˜𝐴−1A~−1 时，不必每次都重新用高斯消元求逆矩阵，而是可以利用如下定理：
定理 （消去定理）：令
𝐴=[𝑎1,1𝑣𝑇𝑢𝐵]𝐴−1=[ˆ𝑎1,1ˆ𝑣𝑇ˆ𝑢ˆ𝐵]A=[a1,1vTuB]A−1=[a^1,1v^Tu^B^]
并且 ˆ𝑎1,1 ≠0a^1,1≠0, 那么就有
𝐵−1=ˆ𝐵−ˆ𝑢ˆ𝑣𝑇ˆ𝑎1,1B−1=B^−u^v^Ta^1,1
定理中描述的是消去第一行第一列的情况．实际上，它可以非常显然地推广到消去任意一行一列的情况，因此我们只需在算法最开始计算一次 ˜𝐴−1A~−1，后面每次删除两个点时，只需执行两次 𝑂(𝑛2)O(n2) 的消去过程即可．
描述有些抽象，可以参考 C++ 代码
---|---
总共要做 𝑛2n2 轮，每轮复杂度为 𝑂(𝑛2)O(n2)，因此上述算法可以在 𝑂(𝑛3)O(n3) 的时间内找到一组完美匹配．
### 构造最大匹配
我们刚刚已经解决了构造一组完美匹配的问题，但是求解问题时一般需要最大匹配．
前面已经提到，𝐺G 的最大匹配大小等于 rank˜𝐴rankA~ 的一半．如果我们能找到 ˜𝐴A~ 的一个最大满秩子方阵，那么对子方阵对应的导出子图求出一组完美匹配，即可找到 𝐺G 的一组最大匹配．
换一个角度考虑，如果 𝐺G 有完美匹配，那么 ˜𝐴A~ 满秩，换言之，˜𝐴A~ 是线性无关的．那么如果 ˜𝐴A~ 不是满秩的，我们可以求出 ˜𝐴A~ 的一组线性基，然后只保留线性基对应的行列，就可以得到 ˜𝐴A~ 的一个最大满秩子方阵．
求出最大满秩子方阵之后，再用上面的算法找出导出子图的一组完美匹配，即可得到原图的一组最大匹配．注意由于高斯消元中可能会有行的交换，因此实现时要注意维护好点的编号．
[UOJ #79. 一般图最大匹配](https://uoj.ac/problem/79)
---|---
习题
参考资料
- Mucha M, Sankowski P.Maximum matchings via Gaussian elimination
- 周子鑫，杨家齐《基于线性代数的一般图匹配》
- ZYQN 《基于线性代数的一般图匹配算法》
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：H-J-Granger, Tiphereth-A, Ir1d, StudyingFather, countercurrent-time, Early0v0, NachtgeistW, 310552025atNYCU, CCXXXI, Enter-tainer, AngelKitty, antileaf, cjsoft, diauweb, ezoixx130, GekkaSaori, HeliumOI, Henry-ZHR, Konano, LovelyBuggies, Makkiy, mgt, minghu6, P-Y-Y, PotassiumWings, pukui, SamZhangQingChuan, ShizuhaAki, sshwy, Suyun514, weiyong1024, Xeonacid, yusancky, accelsao, AntiLeaf, GavinZhengOI, Gesrua, ksyx, kxccc, lychees, Peanut-Tang, SukkaW 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用