Tutte 矩阵学习笔记

前言

这个玩意能解决一般图上的完美匹配存在性问题

为啥要学呢，因为有道模拟赛题的正解是这玩意，然而那题被我随机化 + 匈牙利艹过去了，跑的比正解快 100 倍（，但是听了正解，感觉正解非常牛逼

正片

对于一个 \(n\) 个点，\(m\) 条边的无向图 \(G = (V,E)\)

构造一个 \(Tutte\) 矩阵 \(T\)，其中

\[T_{i,j} = \begin{cases} w_{i,j} & (i,j) \in E \& i < j \\ -w_{i,j} & (i,j) \in E \& i > j \\ 0 & (i,j) \notin E \end{cases} \]

那么这个图存在最大匹配的充要条件是 \(det(T) \neq 0\)

证明

回顾行列式的定义

\[det(T) = \sum_{p} (-1)^{cyc(p)} \prod T_{i,p_i} \]

那么 \(det(T)\) 的本质就是枚举若干个环来分割这个图

如果这些环中存在奇环，那你考虑把环上的边全部反向，这样权值会乘 \((-1)^{odd}\)，和前面的贡献抵消

所以一个分割对 \(det(T)\) 有贡献当且仅当它分割出来全是偶环

那么全是偶环，在偶环上隔一条边取一条边，就能构成原图的最大匹配