小粉兔 的博客

小粉兔 的博客

题解 SP4420 【KPGRAPHS - Counting Graphs】

posted on 2020-06-03 02:03:09 | under 题解 |

和 sys 聊天的时候他说审题解会审到很多有趣的题目,然后我让他推荐几题,他跟我说了这题。

然而目前好像没看到这题有题解,难道是他拒绝了?

我觉得这题也不会很有趣吧,就是中规中矩的图计数问题,纯理性愉悦内容,比赛基本不考的那种。

本着服务大众的理念,来普及一下这些简单的图计数。

进入正题,要计数三种图(简单有标号无向图):

  1. 连通图
  2. 欧拉图(即可以一笔画的图)
  3. 二分图

连通图

令 $n$ 个点的连通图数量为 $a_n$,特别地,规定 $a_0 = 0$,令 $\displaystyle \hat A = \mathbf{EGF}(a) = \sum_{i = 0}^{\infty} \frac{a_i}{i!} z^i$,即 $a$ 的指数型生成函数。

令 $n$ 个点的图数量为 $d_n$,显然有 $\displaystyle d_n = 2^{\binom{n}{2}}$。

根据图计数理论有 $\displaystyle \hat A = \ln \mathbf{EGF}(d)$。

如果 $\hat G = \ln \hat F$,两边求导移项得 $\hat F {\hat G}' = {\hat F}'$,比较系数后不难得到递推式。

欧拉图

令 $n$ 个点的欧拉图数量为 $b_n$,特别地,规定 $b_0 = 0$,令 $\displaystyle \hat B = \mathbf{EGF}(b) = \sum_{i = 0}^{\infty} \frac{b_i}{i!} z^i$,即 $b$ 的指数型生成函数。

令 $n$ 个点的,每个点的度数都是偶数的图数量为 $e_n$,有 $\displaystyle e_n = 2^{\binom{n - 1}{2}}$,特别地,规定 $e_0 = 1$。

这是因为考虑前 $(n - 1)$ 个点组成的任意图,加入第 $n$ 个点时仅和 $1 \sim (n - 1)$ 号点中度数为奇数的点连边,得到最终的图。据此 $n$ 个点的每个点的度数都是偶数的图,与 $(n - 1)$ 个点的任意图是一一对应的,于是前式得证。

一张图是欧拉图,当且仅当图中的每个点的度数都是偶数,且是图是连通图。

根据图计数理论有 $\displaystyle \hat B = \ln \mathbf{EGF}(e)$。

同上,求导比较系数后不难得到递推式。

二分图

EntropyIncreaser 已经在 UOJ Goodbye Jihai D. 新年的追逐战 中运用了类似方法求出此序列,可以查看他的 题解

令 $n$ 个点的二分图数量为 $c_n$,特别地,规定 $c_0 = 1$,令 $\displaystyle \hat C = \mathbf{EGF}(c) = \sum_{i = 0}^{\infty} \frac{c_i}{i!} z^i$,即 $c$ 的指数型生成函数。

考虑求出 $n$ 个点的点二染色(黑白染色)图数量 $f_n$,令 $\hat F = \mathbf{EGF}(f)$。

容易得到:$\displaystyle \hat F = \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} \binom{i + j}{i} 2^{i j} \frac{z^{i + j}}{(i + j)!}$。

即可以 $\mathcal O (m^2)$ 的时间复杂度求出 $f$ 的前 $m$ 项,若要追求更优的复杂度可以参考:

根据 Chirp Z-Transform,可以进行如下推导:

$$\begin{aligned} \hat F &= \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} \binom{i + j}{i} 2^{i j} \frac{z^{i + j}}{(i + j)!} \\ &= \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} \frac{2^{ij}}{i! j!} z^{i + j} \\ &= \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} \frac{2^{-\binom{i}{2}}}{i!} \frac{2^{-\binom{j}{2}}}{j!} 2^{\binom{i + j}{2}} z^{i + j} \\ &= \sum_{n = 0}^{\infty} 2^{\binom{n}{2}} z^n \left[ [y^n] {\left( \sum_{i = 0}^{\infty} 2^{-\binom{i}{2}} \frac{y^i}{i!} \right)}^2 \right]\end{aligned}$$

使用快速多项式乘法即可得到更优的复杂度,但在本题中这不是必要的。

考虑到每个连通二分图均有两种染色方案,令 $n$ 个点的连通二分图数量为 $g_n$,令 $\hat G = \mathbf{EGF}(g)$,特别地,规定 $g_0 = 0$。

则 $2 \hat G$ 即为点二染色连通二分图的指数型生成函数。

根据图计数理论有 $2 \hat G = \ln \hat F$。

同样地还有 $\hat C = \exp \hat G$。

即 $\displaystyle \hat C = \exp \frac{\ln \hat F}{2} = {\hat F}^{1 / 2}$。

两边求导移项得 $2 \hat C {\hat C}' = {\hat F}'$,比较系数后不难得到递推式。