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

灵梦

2020-07-18 16:52:11

Personal

参考自 @tiger0133 提供的资料,十分感谢。

注意部分结论还没有得到代码的验证。若有误麻烦指出,谢谢。

本文中,所有的图都是指点有标号、边没有标号的简单图。

前置知识

下面将这些问题分为无向图和有向图两类来分别讨论。

无向图计数

定义级数序列 (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)。讨论与根相邻的连通子图的两种情况:

边和环都可以任意排列,因此可以列出方程

\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) $$ \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) $$ 待续。