笔记：割空间、环空间、切边等价

笔记：割空间、环空间、切边等价

分类：无向图、DFS 树、线性代数

来源：20230804 正睿 OI ix35 讲课

割和割空间

割：将点集划分为两部分 \(A, B\)，它们之间的边集称为一组割 \(C(A, B)\) 或 \(C(A)\)。

割空间：将割视为 \(\mathbb F_2\) 上的 \(m\) 维向量，所有割构成一个线性空间，称为割空间，其维数是 \(n − 1\)（连通），一组基是任意 DFS 树上所有子树 \(S(x)\) 对应的割集 \(C(S(x))\)。

偶子图和环空间

偶子图：包含所有点，且每个点的度数都是偶数的子图。

环空间：将偶子图视为 \(\mathbb F_2\) 上的 \(m\) 维向量，所有偶子图构成一个线性空间，称为环空间，其维数是 \(m − n + 1\)（连通），一组基是任意 DFS 树上仅包含每条非树边的偶子图（可以包含某些树边）。

割空间和环空间互为正交补。怎么使用正交补空间详见 CF1336E2 Chiori and Doll Picking (hard version) - 洛谷。

切边等价

定义两条边切边等价，当且仅当任意一个环要么同时包含它们，要么同时不包含它们。

你可以理解成，切边等价类就是所有简单环加加减减可以形成的那些不可划分的最小点集。

我们可以用随机 hash 法求切边等价类，任求一个生成树，对于非树边随机一个权值，树边的权值为所有跨过它的非树边权值的异或和，权值相等的边构成一个切边等价类。

复习一下 FWT

FWT 是线性变换，它满足：

\[\text{FWT}(A)_S=\sum_{T}(-1)^{|S\cap T|}A_T \]

\[FWT(AB)_S=FWT(A)_S\cdot FWT(B)_S \]

\[FWT(A+B)_S=FWT(A)_S+FWT(B)_S \]

由定义可以得到的一个常用的式子：

\[[x^\varnothing]IFWT(A)=\frac{1}{2^n}\sum_{S}A_S \]

用 FWT 解释环空间

有多少个 \(n\) 阶无向图是偶子图呢？这实际上就是要求它的环空间的元素个数（也就是 \(2^{\text{维度}}\)）。我们也可以用 FWT 解释。将每条边看成 \(\mathbb F_2\) 上的 \(n\) 维向量，只有两个位置为 \(1\)，那么我们要求的就是：

\[[x^\varnothing]\prod_{u\neq v}(1+x^{\{u, v\}}) \]

根据 \(IFWT(FWT(A))=A\) 并利用 FWT 的线性性可以将它化简为：

\[\frac{1}{2^n}\sum_{S}\prod_{u\neq v}FWT(1+x^{\{u, v\}})_S \]

\(FWT(1+x^{\{u, v\}})\) 就很有意思了，首先容易得到 \(FWT(1)_S=1\)。然后分析 \(FWT(x^{\{u,v\}})_S\)，它就是 \((-1)^{|S\cap\{u,v\}|}\)，\(u, v\) 一个在 \(S\) 中另一个不在时是 \(-1\)，其它情况是 \(+1\)。发现后者取到 \(-1\) 之后，\(FWT(1+x^{\{u, v\}})_S\) 这一项就会取到零，整个积式就是零。可以观察到只有 \(\varnothing\) 和全集是不存在 \(u, v\) 使其取到 \(-1\) 的，于是整个式子其实就是

\[\frac{1}{2^n}\times 2\times 2^{\binom{n-1}2}=2^{\binom {n-1}2-n+1} \]

实际上也就是环空间的维度 \(m-n+1\)。这种方法胜在无中生有，不需要想到上面说到的环空间的基的构造。但是你一旦记住了环空间的基怎么构造，这种方法就会因为太长被抛弃。