带花树算法

带花树？错了，是开花算法（$\text{Blossom Algorithm}$）。

在维基百科上有漂亮的图片。$\text{OI-wiki}$ 中也是使用的这些图片。

在 $\mathrm{CF}$ 的帖子里有很好的叙述，可供参考。

称邻边都未匹配的点为 $\mathrm{exposed}$，裸露的。首先，最大匹配等价于图中没有增广路，其中增广路是两个端点都 $\mathrm{exposed}$ 且路径上的边的匹配情况交错。并且增广不会让之前不能增广的裸露点变得可增广，否则两条增广路的对称差（的俩连通块之一）是原本就可行的增广路。

因此我们可以从每个裸露点开始，找增广路。走增广路过程中走出的奇环被称作花（$\text{blossom}$）。花上没有裸露点，且仅有一个点的两条环上邻边都未匹配，称为花心。那么所有经过花的增广路必然经过花心。而且，花心到花上点有两种走法，必有其中之一能使得路径交错。因此花可以被 $\mathrm{contract}$ 。

缩 $\mathrm{blossom}$ 会嵌套；没有花时，图是二部图，增广路可以求解。

难点大概在于，怎样得到原图上的增广路。精细实现的复杂度应该可以做到 $\mathcal{O}(n^3)$，但因为我没实现过，所以我也不清楚。

线性代数做法

可见 $\mathrm{CF}$ 帖子的评论区，和 $2017$ 年论文《基于线性代数的一般图匹配》。引入 $\text{Tutte}$ 矩阵 $\tilde{A}(G)$ 满足
$${\tilde{A}}_{i,j}=\{\begin{array}{ll}{x}_{i,j}{e}_{i,j}& (i<j)\\ 0& (i=j)\\ -x_{j,i}{e}_{j,i}& (j<i)\end{array}$$

其中 $e_{i,j}$ 表示 $i,j$ 之间是否有连边，而 $x_{i,j}$ 是形式变元。

动机是 $\det \tilde{A}\ne 0$ 足以说明图中有完美匹配。因为行列式的定义相当于作环覆盖，存在奇环时，将环反向可以使值抵消；不存在奇环时，可以构造出匹配。

判定 $\det \tilde{A}\ne 0$ 利用随机化赋值，根据 $\text{Schwartz–Zippel}$ 引理，错误的概率不超过 $\frac{\mathrm{deg}\det \tilde{A}}{p}=\mathcal{O}(\frac{n}{p})$ 可以接受，其中 ${\mathbb{F}}_p$ 为随机范围。

考虑最大匹配。只需找出列 $\mathrm{rank}$，因为这些位置构成的主子式非零（别忘了 $\tilde{A}$ 是 斜对称 的）。所以，求最大匹配的值，已经有了 $\mathcal{O}(n^{\omega })$ 的做法。

Comment. 其中 $\mathcal{O}(n^{\omega })$ 表示矩阵乘法 $/$ 消元的复杂度。

Remark. 消元可以和矩阵乘法做到相同复杂度，但不是高斯消元。而且具体实现我也不会，据称巨复杂。所以我们也可以不管它

同时我们证明了 $\det \tilde{A}\ne 0$ 必然有 $2\mid n$ 。因为必须避免奇环。

构造解，不妨假定 $\det \tilde{A}\ne 0$ 。有个神奇的性质是
$$\det A^{\{i\},\{j\}}\ne 0*\det A^{\{i,j\},\{i,j\}}\ne 0$$

Comment. 由于麻烦，下面的一小段中漏掉了波浪线符号。

其中 $\det A^{S,T}$ 表示 $A$ 去掉 $S$ 中的行、$T$ 中的列的余子式。

证明充分性：因为 $\mathrm{rank}{A}^{\{i\},\{j\}}=n-1$ 因此 $\mathrm{rank}{A}^{\{i,j\},\{i,j\}}⩾n-3$，而斜对称矩阵的秩必然是偶数。

证明必要性：则列 $\mathrm{rank}{A}^{\{i,j\},\{j\}}=n-2$，故行 $\mathrm{rank}{A}^{\{j\},\{j\}}=n-2$，即 $A^{\varnothing ,\{j\}}$ 中第 $i$ 行可被其他行线性表出，然后 $\mathrm{rank}{A}^{\{i\},\{j\}}=\mathrm{rank}{A}^{\varnothing ,\{j\}}=n-1$，即证。

然后，显然 $\det A^{\{i,j\},\{i,j\}}\ne 0$ 则存在包含 $*i,j*$ 的完美匹配，接下来把 $i,j$ 删除继续递归。这只需判断 $\det A^{\{i\},\{j\}}$，联想到伴随矩阵 $A^{\ast }$，由于斜对称性，不需额外转置。又联想到 $A^{-1}=\frac{A^{\ast }}{\det A}$，因此只需判断 $({\tilde{A}}^{-1}{)}_{i,j}$ 是否非零即可。

需要动态维护矩阵的逆。利用这样的定理：若
$$A=\left(\begin{array}{cc}\bar{a}& \bar{v}\\ \bar{u}& \bar{B}\end{array}\right),A^{-1}=\left(\begin{array}{cc}a& v\\ u& B\end{array}\right)$$

那么 $B^{-1}=\bar{B}-\frac{uv}{a}$ 。其中 $u$ 是 $n\times 1$ 矩阵，$v$ 是 $1\times n$ 矩阵，$a\ne 0$ 。

证明只需暴力展开，此处略。不难发现这就对应了删去（同标号）一行一列的维护。

而高斯消元的初等行变化可以很容易地同步作用到 $A^{-1}$ 上，是可维护的。

显然每次维护是 $\mathcal{O}(n^2)$ 的，共 $n$ 次维护，总复杂度 $\mathcal{O}(n^3)$ 无误。

如果带权呢？把 $e_{i,j}$ 设为 $y^{w_{i,j}}$，转化为求算 $\det \tilde{A}$ 中 $y$ 最高次数，用插值得到 关于 $y$ 的结果。只在 $\sum w$ 较小时可用。

线性规划做法

根据 $\text{Jack Edmonds}$ 的研究¹，最大匹配可以用如下线性规划得到：
$$\{\begin{array}{ll}{\sum }_j{x}_{i,j}⩽1& \text{for all }i\in V\\ {\sum }_{i,j\in S}{x}_{i,j}⩽r& \text{for all }r⩽|V|,|S|=2r+1\\ x_{i,j}⩾0& \text{for all }i,j\in V\end{array}$$

他证明了该 $\mathrm{LP}$ 的解空间（多胞体）的所有顶点恰为所有匹配。

NEED HELP. 他是怎样证明的？我现在还没看懂。