广义串并联图学习笔记

Part 1 介绍

广义串并联图，就是不存在同胚于 $K4$ 的子图的无向图。

翻译一下就是不存在这样的结构：

$n$ 点 $m$ 边的广义串并联图有如下性质：

是平面图；
删掉重边后 $m\le 2n$ ；
可以通过不断重复以下操作缩成一个点：
- 删一度点（ $a- b$ 变为 $a$ ）；
- 缩二度点（ $a-b-c$ 变为 $a-c$ ）；
- 叠合重边；
去掉重边后可以从一个点不断重复以下操作构造：
- 加入一个新点，并和原图中的点连一条边；
- 选择原图中原有的一条边 $a-b$ ，加入一个点 $c$ ，连边 $c-a$ 和 $c-b$ ，原来的边 $a-b$ 可以任意删或不删；
分别对应性质 3 中的删一度点和缩二度点。

通过这条性质不难证明性质 2；

广义串并联图的性质和结构并不是很重要，重要的是性质 3 中的三个操作，不妨称其为“广义串并联操作”。

对于任意一个 $n$ 点 $m$ 边的无向图，设 $k=m-n$ ，不断在该图上重复广义串并联操作，则容易发现 $m-n$ 一定不会变大（删一度点和缩二度点不变，叠合重边减一），并且最后得到的图每个点度数 $\ge 3$ ，所以有 $2m'\ge 3n',m'\le n'+k$ ，解得 $n'\le 2k,m'\le 3k$ 。

也就是说，广义串并联操作可以将任意无向图变成 $O(m-n)$ 的图，并且原图的信息在新图上比较好维护。

Part 2 例题

2.1 典题

给定一个 $n$ 点 $m$ 边的无向图，求给每条边定向的方案数，满足定向后的图是 DAG。

$1\le n,m\le 10^5$ ， $m\le n+10$ 。

$n\le 20$ 是简单的，枚举入度为 $0$ 的那一层转移即可。但是要容斥一下还有别的点入度为 $0$ 的情况，所以有：

f_{s}=\sum\limits_{t\subseteq s,t\not=\varnothing} (-1)^{|t|+1}\times f_{s-t}\times h_t

其中若集合 $t$ 中点之间没有边则 $h_t=1$ ，否则其为 $0$ 。

那么对于本题，考虑使用广义串并联操作将原图缩小。对于每条边（注意进行过广义串并联操作后该边可能对应原图中的若干点和边），设两个值 $(f,g)$ 分别表示两端连通但未确定具体方向（存在 $u\to v$ 的路径或 $v\to u$ 的路径）和两端不连通的方案数，初始每条边都是 $(1,0)$ 。

考虑三种操作的影响：

删一度点：它连出去的唯一边随便定向，直接将 $2f+g$ 乘入答案，并把这个点删掉；
缩二度点：

设二度点 $u$ 的两个邻居是 $x$ 和 $y$ ，两条边分别是 $(f_1,g_1)$ 和 $(f_2,g_2)$ ，新的边是 $(f',g')$ 。
- 只有当 $x,u$ 和 $u,y$ 都连通且方向一致时 $x,y$ 才连通，故 $f'=f_1f_2$ ；
- $x,u$ 或 $u,y$ 至少一个不连通，或者 $x\to u,u\leftarrow y$ 或 $x\leftarrow u,u\to y$ 时 $x,y$ 不连通，故 $g'=2f_1g_2+2g_1f_2+g_1g_2+2f_1f_2$ ；
然后把 $u$ 删掉；
叠合重边：
- 两条重边至少一条连通 $x,y$ 就连通，并且这些重边必定同向（否则有环），故 $f'=f_1f_2+f_1g_2+g_1f_2$ ；
- 两条重边都不连通 $x,y$ 才不连通，故 $g'=g_1\times g_2$ ；

最后统计答案的时候先将 $\prod (f+g)$ 乘进答案里，对于转移时钦定的没有入度的点集，系数 $h_t$ 即为集合 $t$ 内点之间边 $(f,g)$ 的 $\frac{g}{f+g}$ 之积。

因为没有二度点，所以这样做一定是对的。

很多广义串并联图的题目都可以用类似设 $(f,g)$ 的方法解决。

广义串并联图学习笔记

Part 1 介绍

Part 2 例题

2.1 典题

Part 3 更多题目

感谢您的支持，我会继续努力的!