小记 - 关于 qoj1351 的一些思考

· · 算法·理论

昨天看见有人在 u 群里问，于是就想了想，感觉挺有意思的，便记录下来。笔者不会数学，写得可能会很民科。

qoj 1351

给定一个无向连通图 G=(V,E)。把原图中割掉一些边，使其变为二分图，对割边数量最小的方案记数，保证割不超过 2 条边。

sjy 讲课的做法：先建 dfs 树。不妨设 |V|=n,|E|=n-1+m，其中前 m 条边为非树边，后 n-1 条边为树边。使用 xor hash，对每条非树边 (u_i,v_i) 赋随机权值 w_i，并将 dfs 树上 u_i 到 v_i 路径上所有边的权值 xor 上 w_i。只需满足割完边后原图中所有边（树边与非树边都算）xor 值为 0 均可。

约定：下文中对 0/1 向量的加法均为模 2 意义下的加法，乘法 \times 均为逐位相乘（结果还是 0/1 向量）。对于 0/1 向量 \vec{v}，定义 \operatorname{popc}(\vec{v}) 为其所有位的数相加模 2 意义下的值。定义 \vec{u}\subset\vec{v} 当且仅当 \vec{u}\times\vec{v}=\vec{u}。

我们使用 |E| 维的 0/1 向量 \vec{v} 表示图上一条链/一个环/一个边集，其中 v_i=1 当且仅当图中第 i 条边出现在其中。

对于 1\leq i\leq m，第 i 条边（非树边）与 dfs 树上若干条边组成一个环，称其为 \vec{R_i}。

将原问题进行拓展：去掉割边树不超过 2 的限制。

定理

对于图 G=(V,E)，设割边集为 \vec{cut}\subset\vec{E}，则：

G'=(V,\vec{E}+\vec{cut})$ 为二分图 $\iff\exist\vec{cut'}\subset\vec{cut},\ \forall1\leq i\leq m,\ \operatorname{popc}(\vec{R_i}\times\vec{cut'})=\operatorname{popc}(\vec{R_i})

证明如下：（注：下文中所有加法运算均为模 2 意义下的加法运算）

右推左

只需证若 \forall1\leq i\leq m,\ \operatorname{popc}(\vec{R_i}\times\vec{cut})=\operatorname{popc}(\vec{R_i})，则 G'=(V,\vec{E}+\vec{cut}) 为二分图。

使用反证法，若 G' 存在奇环，不妨设其为 \vec{T}=\sum_{i=1}^d \vec{R_{v_i}}。考虑 \sum_{i=1}^d\operatorname{popc}(\vec{R_{v_i}}\times\vec{cut})，一方面：

\sum_{i=1}^d\operatorname{popc}(\vec{R_{v_i}}\times\vec{cut})=\sum_{i=1}^d\operatorname{popc}(\vec{R_{v_i}})=\operatorname{popc}(\sum_{i=1}^d\vec{R_i})=\operatorname{popc}(\vec{T})=1

另一方面：

\sum_{i=1}^d\operatorname{popc}(\vec{R_{v_i}}\times\vec{cut})=\sum_{j=1}^d\sum_{i=1}^{n-1+m}cut_i\times R_{v_j,i}=\sum_{i=1}^{n-1+m}cut_i\times(\sum_{j=1}^dR_{v_j,i})=\sum_{i=1}^{n-1+m}cut_i\times T_i=\operatorname{popc}(\vec{cut}\times\vec{T})=0

推出矛盾。

左推右

只需证对于任意极小的 cut 满足 G'=(V,\vec{E}+\vec{cut}) 为二分图，均有 \forall1\leq i\leq m,\ \operatorname{popc}(\vec{R_i}\times\vec{cut})=\operatorname{popc}(\vec{R_i})。

对于任意 1\leq i\leq m，令 \vec{c_i}=\vec{cut}\times\vec{R_i}。对于任意 1\leq j\leq n-1+m，若 c_{i,j}=1，则由条件 cut 为极小的，可得 \vec{cut}+\vec{e_j}（即在割 cut 中去掉 j 这条边）不为能使原图 G 变为二分图的割，故不妨设有奇环 T_j 满足 \vec{T_j}\times\vec{cut}=\vec{e_j}。

使用反证法，若 \operatorname{popc}(\vec{c_i})+\operatorname{popc}(\vec{R_i})=1，则有：

\vec{cut}\times(\vec{R_i}+\sum_{j=1}^{n-1+m,\ c_{i,j}=1}\vec{T_j})=\vec{cut}\times\vec{R_i}+\sum_{j=1}^{n-1+m,\ c_{i,j}=1}\vec{cut}\times\vec{T_j}=\vec{c_i}+\sum_{j=1}^{n-1+m,\ c_{i,j}=1}\vec{e_j}=\vec{c_i}+\vec{c_i}=\vec{0}

又：

\operatorname{popc}(\vec{R_i}+\sum_{j=1}^{n-1+m,\ c_{i,j}=1}\vec{T_j})=\operatorname{popc}(\vec{R_i})+\sum_{i=1}^{n-1+m,c_{i,j}=1}\operatorname{popc}(\vec{T_j})=\operatorname{popc}(\vec{R_i})+\operatorname{popc}(\vec{c_i})=1

故我们找到了 G' 上的一个奇环，矛盾。