浅谈带边数限制的有标号图计数问题

参考自 @tiger0133 提供的资料，十分感谢。 注意部分结论还没有得到代码的验证。若有误麻烦指出，谢谢。 本文中，所有的图都是指点有标号、边没有标号的简单图。 ## 前置知识 - 一些简单的只限制点数的图计数问题 - [二元多项式基本运算](https://www.luogu.com.cn/blog/Hakurei-Reimu/poly2d) 下面将这些问题分为无向图和有向图两类来分别讨论。 ## 无向图计数 定义级数序列 $(a_n(w))_{k=0}^{\infty}$ 的*指数生成函数（EGF）*为 $$ \mathrm{A}(z,w)=\sum_{n\geq 0}a_n(w)\frac{z^n}{n!} $$ 这是一个每一项均为关于 $w$ 的级数的多项式，或者是一个关于 $z,w$ 的二元多项式。 我们知道，在生成函数中，一个变量的幂次标记了某个特定项目的出现次数。在接下来的问题中，我们默认 $z$ 标记点数，$w$ 标记边数，即 $z^nw^m$ 项系数表示 $n$ 个点、$m$ 条边的某种图的个数。将 $w=1$ 代入可以得到只有点数限制的情况。 回顾一下之前学习的知识，容易得出无向图的 EGF 为 $$ \mathrm{G}(z,w)=\sum_{n\geq 0}(1+w)^{\binom{n}{2}}\frac{z^n}{n!} $$ 这是因为一张无向图中，一对无序点对间要么有边，要么没有边。 然后，无向连通图的 EGF 为 $$ \mathrm{C}(z,w)=\ln \mathrm{G}(z,w) $$ 因为一张无向图是由若干连通分量组合而成，反过来就对应了 $\ln$ 运算。 上面只是热身，那么接下来的几个问题就稍有难度了。 ### 仙人掌计数 如果一张无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。 设有根仙人掌的 EGF 为 $\mathrm{Cactus}(z,w)$。讨论与根相邻的连通子图的两种情况： - 通过一条边与根相邻。那么这个子图仍是一棵仙人掌，算上这条边后 EGF 为 $w\mathrm{Cactus}(z,w)$。 - 通过环与根相邻。一个环上的所有子图都是一棵仙人掌，并且这个环可以翻转。因为除了根以外有 $n$ 个点的环包含 $n+1$ 条边，所以这个环的 EGF 为 $\frac{1}{2}\sum\limits_{n\geq 2}w^{n+1}\mathrm{Cactus}(z,w)^n$。 边和环都可以任意排列，因此可以列出方程 $$ \begin{aligned}{} \mathrm{Cactus}(z,w)&=\exp\left(w\mathrm{Cactus}(z,w)+\frac{1}{2}\sum_{n\geq 2}w^{n+1}\mathrm{Cactus}(z,w)^n\right)\\ &=\exp\left(w\mathrm{Cactus}(z,w)+\frac{w^3\mathrm{Cactus}(z,w)^2}{2-2w\mathrm{Cactus}(z,w)}\right) \end{aligned} $$ 至此，已经可以牛顿迭代求解。也可以对等式两边同时取 $\ln$，以免去大常数的 $\exp$ 运算。 因为考虑的是有根的情况，所以为了得到无根的答案还要除以点数。 ### 点双连通图计数 如果一张无向连通图删去任何一个点后仍然连通，我们就称之为点双连通图。 首先设有根连通图的 EGF 为 $\mathrm{R}(z,w)$。容易发现，$n$ 个点的有根连通图个数是无根连通图个数的 $n$ 倍，因此 $\mathrm{R}(z,w)$ 可以直接由 $\mathrm{C}(z,w)$ 得出。 然后设有根点双连通图的 EGF 为 $$ \mathrm{pBCC}(z,w)=\sum_{n\geq 0}pb_n(w)\frac{z^n}{n!} $$ 这里为了计算方便，我们规定 $0$ 个节点的连通图和双连通图的个数都是 $0$。另外，我们令 $pb_1(w)=0$。虽然只有一个点的图也应该是点双连通图，但在计算中保留这个特性是十分不优美的。 对于一张有根连通图，考虑一个包含根的点双连通分量。在这个点双连通分量中，除了根以外的所有节点都可以挂上一个连通子图。如果它包含 $n+1$ 个节点，则其 EGF 为 $\dfrac{pb_{n+1}(w)\mathrm{R}(z,w)^n}{n!}$。这些点双连通分量可以自由排列，再计入根的贡献，得 $$ \begin{aligned}{} \mathrm{R}(z,w)&=z\exp\sum_{n\geq 1}\frac{pb_{n+1}(w)\mathrm{R}(z,w)^n}{n!}\\ &=z\exp\frac{\partial\mathrm{pBCC}}{\partial\mathrm{R}(z,w)}(\mathrm{R}(z,w),w) \end{aligned} $$ 设 $\mathrm{R}^{-1}$ 为 $\mathrm{R}$ 关于 $z$ 的复合逆，那么 $\mathrm{R}(\mathrm{R}^{-1}(z,w),w)=z$。代入得 $$ \begin{gathered}{} z=\mathrm{R}^{-1}(z,w)\exp\frac{\partial\mathrm{pBCC}}{\partial z}(z,w)\\ \frac{\partial\mathrm{pBCC}}{\partial z}(z,w)=\ln\frac{z}{\mathrm{R}^{-1}(z,w)} \end{gathered} $$ 设 $\mathrm{H}(z,w)=\ln\dfrac{\mathrm{R}(z,w)}{z}$，可以使用扩展形式的拉格朗日反演公式来解决点数固定时的问题 $$ \begin{aligned}{} [z^n]\frac{\partial\mathrm{pBCC}}{\partial z}(z,w)&=\frac{1}{n}[z^{-1}]\frac{\partial\mathrm{H}}{\partial z}(z,w)\frac{1}{\mathrm{R}(z,w)^n}\\ &=\frac{1}{n}[z^{n-1}]\frac{\partial\mathrm{H}}{\partial z}(z,w)\exp(-n\mathrm{H}(z,w)) \end{aligned} $$ 注意这里的 $[z^n]\mathrm{A}(z,w)$ 表示提取 $\dfrac{a_n(w)}{n!}$ 这个级数，而不是 $z^ny^0$ 项系数，下同。 ### 边双连通图计数 如果一张无向连通图删去任何一条边后仍然连通，我们就称之为边双连通图。 设有根边双连通图的 EGF 为 $$ \mathrm{eBCC}(z,w)=\sum_{n\geq 0}eb_n(w)\frac{z^n}{n!} $$ 对于根节点所在的边双连通分量，枚举它的大小为 $n$，则其 EGF 为 $\dfrac{eb_n(w)z^n}{n!}$。考虑一个与这个边双连通分量相邻的连通子图，它的内部方案数为 $\mathrm{R}(z,w)$，且有一条边从根连向 $n$ 个点中的一个，所以这部分的 EGF 为 $nw\mathrm{R}(z,w)$。将这些子图任意排列，得 $$ \begin{aligned}{} \mathrm{R}(z,w)&=\sum_{n\geq 1}\frac{eb_n(w)z^n\exp(nw\mathrm{R}(z,w))}{n!}\\ &=\mathrm{eBCC}(z\exp w\mathrm{R}(z,w),w) \end{aligned} $$ 设 $\mathrm{H}(z,w)=z\exp w\mathrm{R}(z,w)$，$\mathrm{H}^{-1}$ 为其关于 $z$ 的复合逆，代入得 $$ \mathrm{eBCC}(z,w)=\mathrm{R}(\mathrm{H}^{-1}(z,w),w) $$ 仍可以使用扩展形式的拉格朗日反演公式来解决点数固定时的问题 $$ \begin{aligned}{} [z^n]\mathrm{eBCC}(z,w)&=\frac{1}{n}[z^{-1}]\frac{\partial\mathrm{R}}{\partial z}(z,w)\frac{1}{\mathrm H(x)^n}\\ &=\frac{1}{n}[z^{n-1}]\frac{\partial\mathrm{R}}{\partial z}(z,w)\exp(-nw\mathrm{R}(z,w)) \end{aligned} $$ ## 有向图计数 为了处理带边数限制的有向图计数问题，我们引入新的数学工具。 定义级数序列 $(a_n(w))_{k=0}^{\infty}$ 的*图论生成函数（GGF）*为 $$ \mathbf{A}(z,w)=\sum_{n\geq 0}\frac{a_n(w)}{(1+w)^{\binom{n}{2}}}\frac{z^n}{n!} $$ 这里以粗体来区分 GGF 与 EGF。容易得出有向图的 GGF 为 $$ \mathbf{D}(z,w)=\sum_{n\geq 0}(1+w)^{\binom{n}{2}}\frac{z^n}{n!} $$ 这是因为所有有序点间要么有边，要么没有，所以 $d_n(w)=(1+w)^{n(n-1)}$。另外，点集（即没有边的有标号图）的 GGF 为 $$ \mathbf{Set}(z,w)=\sum_{n\geq 0}\frac{1}{(1+w)^{\binom{n}{2}}}\frac{z^n}{n!} $$ 因为无论如何都只有一种不连边方案。 定义两个多项式 $A(z)=\sum_{n\geq 0}a_n\frac{z^{n}}{n!}$ 和 $B(z)=\sum_{n\geq 0}b_n\frac{z^{n}}{n!}$ 的*指数型 Hadamard 积*为 $$ A(z)\odot B(z)=\left(\sum_{n\geq 0}a_n\frac{z^n}{n!}\right)\odot\left(\sum_{n\geq 0}b_n\frac{z^n}{n!}\right)=\sum_{n\geq 0}a_nb_n\frac{z^n}{n!} $$ 这里需要注意一下与点乘的区别。这种运算可以用来转化 EGF 和 GGF：对于一个族 $\mathcal{A}$，它的 EGF 与 GGF 存在以下关系 $$ \mathrm{A}(z,w)=\mathrm{G}(z,w)\odot \mathbf{A}(z,w)\quad \mathrm{and}\quad \mathbf{A}(z,w)=\mathbf{Set}(z,w)\odot \mathrm{A}(z,w) $$ 直接展开即可得证。 下面我们来讨论 GGF 的组合意义。考虑两个族 $\mathcal{A}$ 和 $\mathcal{B}$，它们对应的级数序列分别为 $(a_n(w))$ 和 $(b_n(w))$。那么 $\mathbf{A}(z,w)\mathbf{B}(z,w)$ 的级数序列为 $$ \begin{aligned} c_n(w)&=(1+w)^{\binom{n}{2}}n![z^n]\left(\sum_k\frac{a_k(w)}{(1+w)^{\binom{k}{2}}}\frac{z^k}{k!}\right)\left(\sum_l\frac{a_l(w)}{(1+w)^{\binom{l}{2}}}\frac{z^l}{l!}\right)\\ &=\sum_{k+l=n}\binom{n}{k}(1+w)^{kl}a_k(w)b_l(w) \end{aligned} $$ 这表示什么呢？考虑从 $\mathcal{A}$ 中选出一个大小为 $k$ 的图 $a$，从 $\mathcal{B}$ 中选出一个大小为 $l$ 的图 $b$，使得 $k+l=n$。然后给这 $n$ 个点重新标号，从 $\{1,\dots,n\}$ 中选出一个大小为 $k$ 的子集给 $a$ 标号，再用其补集给 $b$ 标号，共有 $\binom{n}{k}$ 种方案。然后，$a$ 中的任意一点都可以向 $b$ 中的任意一点连一条有向边，这里的贡献为 $(1+w)^{kl}$。我们把这样得到的所有有向图构成的族称作 $\mathcal{A}$ 与 $\mathcal{B}$ 的 *arrow product*，对比上式可以发现 $\mathbf{A}(z,w)\mathbf{B}(z,w)$ 就是族 $\mathcal{A}$ 与族 $\mathcal{B}$ 的 arrow product 的 GGF。 有了这个性质，我们来看接下来的几个问题。 ### 有向无环图计数 如果一张有向图从任意顶点出发无法经过若干条边回到该点，我们就称之为有向无环图（DAG）。 设包含一个用来标记源点（零入度点）个数的额外变量 $u$ 的 DAG 的 GGF 为 $\mathbf{DAG}(z,w,u)$。由二项式定理可知，标记了部分源点的 DAG 的 GGF 为 $\mathbf{DAG}(z,w,u+1)$。我们选出一些源点向其他点任意连边，发现得到的是点集与 DAG 的 arrow product，即 $$ \mathbf{DAG}(z,w,u+1)=\mathbf{Set}(zu,w)\mathbf{DAG}(z,w) $$ $zu$ 表示这个点占用了一个源点的位置。因为没有源点的 DAG 只有空 DAG，所以 $\mathbf{DAG}(z,w,0)=1$，那么代入 $u=-1$ 得 $1=\mathbf{Set}(-z,w)\mathbf{DAG}(z,w)$，即 $\mathbf{DAG}(z,w)=\dfrac{1}{\mathbf{Set}(-z,w)}$。然后把 $u$ 替换成 $u-1$ 还可以得到标记了源点个数的 DAG 的 GGF $$ \mathbf{DAG}(z,w,u)=\frac{\mathbf{Set}((u-1)z,w)}{\mathbf{Set}(-z,w)} $$ ### 强连通图计数 如果一张有向图从任意顶点除法都可以经过若干条边回到该点，我们就称之为强连通图。 设强连通图的 EGF 为 $\mathrm{SCC}(z,w)$。将一张有向图的强连通分量缩成点，可以得到一张 DAG。类似地，我们把没有前驱的强连通分量称为类源 SCC，使用一个额外变量 $u$ 来标记有向图中的类源 SCC，记作 $\mathbf{D}(z,w,u)$。那么有 $$ \mathbf{D}(z,w,u+1)=(\mathbf{Set}(z,w)\odot\exp u\mathrm{SCC}(z,w))\mathbf{D}(z,w,u) $$ 这里的 $\exp$ 是将标号重新分配到各个类源 SCC 中，与 $\mathbf{Set}(z,w)$ 取 Hadamard 积是为了将 EGF 转化为 GGF。代入 $u=-1$，得 $$ \begin{gathered} 1=(\mathbf{Set}(z,w)\odot\exp(-\mathrm{SCC}(z,w)))\mathbf{D}(z,w)\\ \exp(-\mathrm{SCC}(z,w))=\mathrm{G}(z,w)\odot\frac{1}{\mathbf{D}(z,w)}\\ \mathrm{SCC}(z,w)=-\ln\left(\mathrm{G}(z,w)\odot\frac{1}{\mathrm{G}(z,w)}\right) \end{gathered} $$ ### 初始连通图计数 $$ \mathbf{IC}(z,w)=\mathrm{C}(z,w)=\ln\mathrm{G}(z,w) $$ 待续。