本文中，所有的图都是指有标号图。
前置知识
下面将这些问题分为无向图和有向图两类来分别讨论。
无向图计数
定义级数序列 (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)
冷滟泽的个人博客