[Study Notes] Maximum matching of general graphs

带花树算法

带花树？错了,is the flowering algorithm（$\text{Blossom Algorithm}$）.

在维基百科There are beautiful pictures on it.$\text{OI-wiki}$ These images are also used in .

在 $\mathrm{CF}$ 的帖子There is a good narrative in it,可供参考.

A point whose adjacent edges are not matched is called $\mathrm{exposed}$,裸露的.首先,Maximum matching is equivalent to no augmenting path in the graph,where the augmentation path is both endpoints $\mathrm{exposed}$ And the matching cases of the edges on the path are staggered.And augmentation does not make nudity points that were previously not augmentable become augmentable,Otherwise, the symmetry of the two augmenting paths is poor（one of the two connected blocks）It is an augmentation path that is already feasible.

So we can start with each bare spot,找增广路.The odd rings that emerge during the augmentation path are called flowers（$\text{blossom}$）.There are no bare spots on the flowers,And the adjacent edges on the two rings with only one point are not matched,called the flower heart.Then all augmentation paths that pass through the flower must pass through the heart of the flower.而且,There are two ways to go from the center of the flower to the point of the flower,One of them must be able to make the paths interleaved.So flowers can be covered $\mathrm{contract}$ .

缩 $\mathrm{blossom}$ 会嵌套;No time spent,图是二部图,Augmenting paths can be solved.

The difficulty is probably that,How to get the augmented path on the original image.The complexity of the fine-grained implementation should do it $\mathcal{O}(n^3)$,But because I didn't realize it,So I don't know either.

Linear algebra practice

可见 $\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}$ is a formal variable.

动机是 $\det \tilde{A}\ne 0$ Suffice it to say that there is a perfect match in the graph.Because the definition of determinant is equivalent to making a ring cover,When there are odd rings,Reversing the ring makes the values ​​cancel out;When there is no odd ring,Matches can be constructed.

判定 $\det \tilde{A}\ne 0$ Use random assignment,根据 $\text{Schwartz–Zippel}$ 引理,The probability of error does not exceed $\frac{\mathrm{deg}\det \tilde{A}}{p}=\mathcal{O}(\frac{n}{p})$ 可以接受,其中 ${\mathbb{F}}_p$ is a random range.

Consider maximum matching.Just find out the column $\mathrm{rank}$,Because the main subform formed by these positions is non-zero（别忘了 $\tilde{A}$ 是 斜对称 的）.所以,Find the largest matching value,已经有了 $\mathcal{O}(n^{\omega })$ 的做法.

Comment. 其中 $\mathcal{O}(n^{\omega })$ 表示矩阵乘法 $/$ Elimination complexity.

Remark. Elimination can be done with the same complexity as matrix multiplication,But not Gaussian elimination.And I don't know how to implement it,It is said to be very complicated.So we can leave it alone

同时我们证明了 $\det \tilde{A}\ne 0$ 必然有 $2\mid n$ .Because odd rings must be avoided.

构造解,不妨假定 $\det \tilde{A}\ne 0$ .It has a magical property
$$\det A^{\{i\},\{j\}}\ne 0*\det A^{\{i,j\},\{i,j\}}\ne 0$$

Comment. 由于麻烦,The tilde symbol is missing from the snippet below.

其中 $\det A^{S,T}$ 表示 $A$ 去掉 $S$ 中的行、$T$ The cofactors of the columns in .

证明充分性：因为 $\mathrm{rank}{A}^{\{i\},\{j\}}=n-1$ 因此 $\mathrm{rank}{A}^{\{i,j\},\{i,j\}}⩾n-3$,The rank of an obliquely symmetric matrix must be even.

证明必要性：则列 $\mathrm{rank}{A}^{\{i,j\},\{j\}}=n-2$,the old way $\mathrm{rank}{A}^{\{j\},\{j\}}=n-2$,即 $A^{\varnothing ,\{j\}}$ 中第 $i$ Rows can be represented linearly by other rows,然后 $\mathrm{rank}{A}^{\{i\},\{j\}}=\mathrm{rank}{A}^{\varnothing ,\{j\}}=n-1$,即证.

然后,显然 $\det A^{\{i,j\},\{i,j\}}\ne 0$ contains $*i,j*$ 的完美匹配,接下来把 $i,j$ Delete continues recursion.It's just judgment $\det A^{\{i\},\{j\}}$,Think of the adjoint matrix $A^{\ast }$,due to oblique symmetry,No additional transposition is required.又联想到 $A^{-1}=\frac{A^{\ast }}{\det A}$,因此只需判断 $({\tilde{A}}^{-1}{)}_{i,j}$ Whether it is non-zero or not.

The inverse of the matrix needs to be maintained dynamically.Use this theorem：若
$$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$ .

The proof just needs to be violently unfolded,此处略.It is not difficult to find that this corresponds to deletion（Same label）Row-by-column maintenance.

And the elementary row changes of Gaussian elimination can be easily synchronized $A^{-1}$ 上,是可维护的.

Apparently every maintenance is $\mathcal{O}(n^2)$ 的,共 $n$ maintenance,总复杂度 $\mathcal{O}(n^3)$ 无误.

If you have the right？把 $e_{i,j}$ 设为 $y^{w_{i,j}}$,Convert to calculation $\det \tilde{A}$ 中 $y$ 最高次数,obtained by interpolation 关于 $y$ 的结果.只在 $\sum w$ Available when smaller.

Linear programming practice

根据 $\text{Jack Edmonds}$ 的研究¹,The maximum matching can be obtained using the following linear programming：
$$\{\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}$$

He proved that $\mathrm{LP}$ 的解空间（multicellular body）All vertices of are exactly all matches.

NEED HELP. How did he prove it？I don't understand it yet.

---

1. Maximum Matching and a Polyhedron With 0,1-Vertices. doi: 10.6028/jres.069.（Scientific Internet access is faster） ︎