0%

边/点双连通图计数

有标号边/点双连通图计数。

下面只讨论有根情况,无根情况即乘以 $\dfrac 1 n$。

答案为 $g_n$。

有标号边双连通图计数

我们都知道有标号无向连通图的 EGF 怎么求。记为 $F(x)$。

对于一个无向连通图,枚举根节点所在边双连通分量的大小。剩下的部分是一个个无向连通图,挂在根边双联通分量的任意一个点上,于是有

这里出现了一个复合,难以处理,需要请出一个新的工具:

拉格朗日反演

回到边双连通图计数的问题上。

设 $H(x)=x\exp F(x)$,则

有标号点双连通图计数

根有可能存在于多个点双中,这些点双显然两两间只有根一个交点,如果把根去掉,那么原图会被分为数个连通块,一个点双对应一个。所以把连通块 exp 即可。下面分析单个连通块。

枚举点双大小 $i+1$,显然它的 EGF 是

这里 $G(x)$ 移了一位,是 $\sum_{i=1}^\infty g_{i+1}\dfrac{x^i}{i!}$。有

设 $H(x)=\dfrac{F(x)}x$,则有