当前位置:网站首页>[Study Notes] Maximum matching of general graphs
[Study Notes] Maximum matching of general graphs
2022-08-11 10:54:00 【OneInDark】
带花树算法
带花树?错了,is the flowering algorithm( Blossom Algorithm \text{Blossom Algorithm} Blossom Algorithm).
在维基百科There are beautiful pictures on it. OI-wiki \text{OI-wiki} OI-wiki These images are also used in .
在 C F \rm CF CF 的帖子There is a good narrative in it,可供参考.
A point whose adjacent edges are not matched is called e x p o s e d \rm exposed exposed,裸露的.首先,Maximum matching is equivalent to no augmenting path in the graph,where the augmentation path is both endpoints e x p o s e d \rm exposed 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( blossom \text{blossom} 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 c o n t r a c t \rm contract contract .
缩 b l o s s o m \rm blossom 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 O ( n 3 ) \mathcal O(n^3) O(n3),But because I didn't realize it,So I don't know either.
Linear algebra practice
可见 C F \rm CF CF 帖子的评论区,和 2017 2017 2017 年论文《基于线性代数的一般图匹配》.引入 Tutte \text{Tutte} Tutte 矩阵 A ~ ( G ) \tilde A(G) A~(G) 满足
A ~ i , j = { x i , j e i , j ( i < j ) 0 ( i = j ) − x j , i e j , i ( j < i ) \tilde A_{i,j}=\begin{cases} x_{i,j}e_{i,j} &(i<j)\\ 0 &(i=j)\\ -x_{j,i}e_{j,i} &(j<i) \end{cases} A~i,j=⎩⎨⎧xi,jei,j0−xj,iej,i(i<j)(i=j)(j<i)
其中 e i , j e_{i,j} ei,j 表示 i , j i,j i,j 之间是否有连边,而 x i , j x_{i,j} xi,j is a formal variable.
动机是 det A ~ ≠ 0 \det\tilde A\ne 0 detA~=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 A ~ ≠ 0 \det\tilde A\ne 0 detA~=0 Use random assignment,根据 Schwartz–Zippel \text{Schwartz–Zippel} Schwartz–Zippel 引理,The probability of error does not exceed deg det A ~ p = O ( n p ) {\deg\det\tilde A\over p}=\mathcal O({n\over p}) pdegdetA~=O(pn) 可以接受,其中 F p \mathbb{F}_p Fp is a random range.
Consider maximum matching.Just find out the column r a n k \rm rank rank,Because the main subform formed by these positions is non-zero(别忘了 A ~ \tilde A A~ 是 斜对称 的).所以,Find the largest matching value,已经有了 O ( n ω ) \mathcal O(n^\omega) O(nω) 的做法.
Comment. 其中 O ( n ω ) \mathcal O(n^\omega) O(nω) 表示矩阵乘法 / / / 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 A ~ ≠ 0 \det\tilde A\ne 0 detA~=0 必然有 2 ∣ n 2\mid n 2∣n .Because odd rings must be avoided.
构造解,不妨假定 det A ~ ≠ 0 \det\tilde A\ne 0 detA~=0 .It has a magical property
det A { i } , { j } ≠ 0 * det A { i , j } , { i , j } ≠ 0 \det A^{\{i\},\{j\}}\ne 0\iff\det A^{\{i,j\},\{i,j\}}\ne 0 detA{ i},{ j}=0*detA{ i,j},{ i,j}=0
Comment. 由于麻烦,The tilde symbol is missing from the snippet below.
其中 det A S , T \det A^{S,T} detAS,T 表示 A A A 去掉 S S S 中的行、 T T T The cofactors of the columns in .
证明充分性:因为 rank A { i } , { j } = n − 1 \operatorname{rank}A^{\{i\},\{j\}}=n-1 rankA{ i},{ j}=n−1 因此 rank A { i , j } , { i , j } ⩾ n − 3 \operatorname{rank}A^{\{i,j\},\{i,j\}}\geqslant n-3 rankA{ i,j},{ i,j}⩾n−3,The rank of an obliquely symmetric matrix must be even.
证明必要性:则列 rank A { i , j } , { j } = n − 2 \operatorname{rank}A^{\{i,j\},\{j\}}=n-2 rankA{ i,j},{ j}=n−2,the old way rank A { j } , { j } = n − 2 \operatorname{rank}A^{\{j\},\{j\}}=n-2 rankA{ j},{ j}=n−2,即 A ∅ , { j } A^{\varnothing,\{j\}} A∅,{ j} 中第 i i i Rows can be represented linearly by other rows,然后 rank A { i } , { j } = rank A ∅ , { j } = n − 1 \operatorname{rank}A^{\{i\},\{j\}}=\operatorname{rank}A^{\varnothing,\{j\}}=n-1 rankA{ i},{ j}=rankA∅,{ j}=n−1,即证.
然后,显然 det A { i , j } , { i , j } ≠ 0 \det A^{\{i,j\},\{i,j\}}\ne 0 detA{ i,j},{ i,j}=0 contains * i , j * \langle i,j\rangle *i,j* 的完美匹配,接下来把 i , j i,j i,j Delete continues recursion.It's just judgment det A { i } , { j } \det A^{\{i\},\{j\}} detA{ i},{ j},Think of the adjoint matrix A ∗ A^\ast A∗,due to oblique symmetry,No additional transposition is required.又联想到 A − 1 = A ∗ det A A^{-1}={A^\ast\over\det A} A−1=detAA∗,因此只需判断 ( A ~ − 1 ) i , j (\tilde A^{-1})_{i,j} (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 = ( a ˉ v ˉ u ˉ B ˉ ) , A − 1 = ( a v u B ) A=\begin{pmatrix} \bar a & \bar v\\ \bar u & \bar B \end{pmatrix}, \quad A^{-1}=\begin{pmatrix} a & v\\ u & B \end{pmatrix} A=(aˉuˉvˉBˉ),A−1=(auvB)
那么 B − 1 = B ˉ − u v a B^{-1}=\bar B-{uv\over a} B−1=Bˉ−auv .其中 u u u 是 n × 1 n\times 1 n×1 矩阵, v v v 是 1 × n 1\times n 1×n 矩阵, a ≠ 0 a\ne 0 a=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 A^{-1} A−1 上,是可维护的.
Apparently every maintenance is O ( n 2 ) \mathcal O(n^2) O(n2) 的,共 n n n maintenance,总复杂度 O ( n 3 ) \mathcal O(n^3) O(n3) 无误.
If you have the right?把 e i , j e_{i,j} ei,j 设为 y w i , j y^{w_{i,j}} ywi,j,Convert to calculation det A ~ \det\tilde A detA~ 中 y y y 最高次数,obtained by interpolation 关于 y y y 的结果.只在 ∑ w \sum w ∑w Available when smaller.
Linear programming practice
根据 Jack Edmonds \text{Jack Edmonds} Jack Edmonds 的研究1,The maximum matching can be obtained using the following linear programming:
{ ∑ j x i , j ⩽ 1 for all i ∈ V ∑ i , j ∈ S x i , j ⩽ r for all r ⩽ ∣ V ∣ , ∣ S ∣ = 2 r + 1 x i , j ⩾ 0 for all i , j ∈ V \begin{cases} \sum_{j}x_{i,j}\leqslant 1 &\text{for all }i\in V\\ \sum_{i,j\in S}x_{i,j}\leqslant r &\text{for all }r\leqslant|V|,\;|S|=2r+1\\ x_{i,j}\geqslant 0 &\text{for all }i,j\in V \end{cases} ⎩⎨⎧∑jxi,j⩽1∑i,j∈Sxi,j⩽rxi,j⩾0for all i∈Vfor all r⩽∣V∣,∣S∣=2r+1for all i,j∈V
He proved that L P \rm LP LP 的解空间(multicellular body)All vertices of are exactly all matches.
NEED HELP. How did he prove it?I don't understand it yet.
Maximum Matching and a Polyhedron With 0,1-Vertices. doi: 10.6028/jres.069.(Scientific Internet access is faster) ︎
边栏推荐
猜你喜欢
Neuropathic pain classification picture Daquan, neuropathic pain classification
Use Function Compute to package and download OSS files [Encounter Pit Collection]
漫画手绘之临摹篇
Database indexes and their underlying data structures
chrome is set to dark mode (including the entire webpage)
本地开发好的 SAP UI5 应用部署到 ABAP 服务器时,中文字符变成乱码的原因分析和解决方案
MongoDB 非关系型数据库
LeetCode 剑指 Offer 35. 复杂链表的复制
『独家』互联网 BAT 大厂 Android高级工程师面试题:174道题目让你做到面试无忧
虚拟机使用 WinSCP & Putty
随机推荐
VMWare中安装的win10,新增其他盘符,如:E盘,F盘等
How to build programming ideas and improve programming ideas
Open Office XML 格式中的 Style 设计原理
MySQL数据库基础_常用数据类型_表设计
MySQL表sql语句增删查改_查询
【Mask2Former】 解决代码中一些问题
Incredible, thanks to this Android interview question, I have won offers from many Internet companies
假设检验:正态性检验的那些bug——为什么对同一数据,normaltest和ktest会得到完全相反的结果?
如何解决 “主节点故障恢复的自动化” 问题?
chrome is set to dark mode (including the entire webpage)
使用.NET简单实现一个Redis的高性能克隆版(七-完结)
10Super详解
如何建立编程思想和提高编程思想
【UOJ 454】打雪仗(通信题)(分块)
安装nodejs
Ali Ermian: Do you know how to tune the JVM?
【luogu CF1286E】Fedya the Potter Strikes Back(字符串)(KMP)(势能分析)(线段树)
LeetCode·每日一题·1417.重新格式化字符串·模拟
虚拟机使用 WinSCP & Putty
MySQL约束