Seventh Mist

连通图计数

下面所说的图, 连通图, 都是指有标号, 没有自环或重边的无向图.

nn 个点的连通图数量

这个还是比较容易DP的.

f[n]f[n]表示nn个点的连通图数量, g[n]g[n]表示nn个点的图的数量, 那么我们有

g[n]=2(n2)\displaystyle g[n] = 2^{\binom{n}{2}} f[n]=g[n]i=1n1(n1i1)f[i]g[ni]\displaystyle f[n] = g[n] - \sum_{i = 1}^{n - 1} \binom{n - 1}{i - 1} \cdot f[i] \cdot g[n - i]

直接做是O(n2)O(n^2)的(貌似可以用生成函数搞搞?).

nn个点, mm条边的连通图的数量

f[n][m]f[n][m]表示nn个点, mm条边的连通图数量.

下面记v(G)v(G)GG的点数, e(G)e(G)GG的边数.

CGS(n,m)CGS(n, m)表示nn个点, mm条边的连通图的集合, GS(n,m)GS(n, m)表示nn个点, mm条边的图的集合, c(G)c(G)表示GG的连通块个数. [[布尔表达式]]表示对布尔表达式求值.

那么

f[n][m]=GCGS(n,m)1=GGS(n,m)[c(G)=1]\displaystyle f[n][m] = \sum_{G \in CGS(n, m)} 1 = \sum_{G \in GS(n, m)} [c(G) = 1]

留意到

m=1n(1)m1(m1)!S(n,m)=[n=1]\displaystyle \sum_{m=1}^n (-1)^{m - 1} (m-1)! S(n,m) = [n = 1]

其中S(n,m)S(n, m)表示第二类Stirling数.

f[n][m]=GGS(n,m)(i=1c(G)(1)c(G)1(c(G)1)!S(c(G),i))\displaystyle f[n][m] = \sum_{G \in GS(n, m)} \left( \sum_{i = 1}^{c(G)} (-1)^{c(G) - 1} (c(G) - 1)! S(c(G), i) \right)

接下来, 对于每个GGS(n,m)G \in GS(n, m), 我们考虑所有的图GG^\prime, 它保留了GG中所有边, 并且每个连通块都是完全图(注意, c(G)c(G^\prime)可以不等于c(G)c(G)!).

那么我们可以发现, 满足c(G)=ic(G^\prime) = iGG^\prime有恰好S(c(G),i)S(c(G), i)个.

因此对于每一个GG^\prime, 我们只需要统计有多少个GG(不妨设有cntcnt个), 之后再用(1)c(G)1(c(G)1)!cnt(-1)^{c(G) - 1} (c(G) - 1)! \cdot cnt更新答案.

那么对于每一个GG^\prime, 有多少个满足条件的GGS(n,m)G \in GS(n, m)呢? 答案是(e(G)m)\binom{e(G^\prime)}{m}.

于是现在我们要求的就是

g[n][m]=e(G)=m(1)c(G)1(c(G)1)!\displaystyle g[n][m] = \sum_{e(G^\prime) = m} (-1)^{c(G^\prime) - 1} (c(G^\prime) - 1)!

这可以用一个简单的DP求得. 为了让一个GG^\prime贡献恰好(c(G)1)!(c(G^\prime) - 1)!次, 我们可以乱序枚举除11所在连通块以外的连通块的出现顺序.

然后

f[n][m]=im(im)g[n][i]\displaystyle f[n][m] = \sum_{i \ge m} \binom{i}{m} \cdot g[n][i]

下面给出关键部分的代码.

[lang: cpp]
1
2
3
4
5
6
7
8
9
10
11
12
13
h[0][0] = 1;
int m = binom(n, 2);
for (int i = 0; i < n; ++i)
for (int j = 0; j <= calc(i); ++j)
if (h[i][j])
for (int k = 1; i + k <= n; ++k)
add(h[i + k][j + calc(k)], (i64)-h[i][j] * binom(i + k, k));
for (int i = 0; i <= m; ++i)
for (int j = 1; j <= n && calc(j) <= i; ++j)
add(g[i], (i64)h[n - j][i - calc(j)] * binom(n - 1, j - 1));
for (int i = 0; i <= m; ++i)
for (int j = 0; j <= i; ++j)
add(f[j], (i64)g[i] * binom(i, j));

复杂度是O(n4)O(n^4)的.

例题

对于一个nn个点的图(允许有自环, 重边), 我们每次随机两个[1,n][1, n]中的整数(u,v)(u, v), 并将边(u,v)(u, v)加入到图中. 问期望多少次之后图连通?

这个题有一个暴力做法, 那就是枚举连通块划分P={p1,p2,,pk}P = \{p_1, p_2, \ldots, p_k\}, 然后转移搞搞.

沿着这个思路下去, 我们考虑对于每一个状态PP, 它对答案的贡献是多少?

不妨设tot=i=1k(pi2)tot = \sum_{i = 1}^k \binom{p_i}{2}, 那么, 对于状态PP来说, 我们走到新的状态PP^\prime, 需要的期望步数为n2n2ntot\frac{n^2}{n^2 - n - tot}. 这是因为我们每一次随机到一条无用边(不能改变连通块划分的边)的概率为n2nin2\frac{n^2 - n - i}{n^2}, 取个倒数就可以啦.

这里插一句话, 为什么期望是概率的倒数呢? 这是随机过程理论中的一个经典结论:

一个有限不可约的状态空间中,任一状态的平均返回时间等于稳态分布中该状态概率的倒数;

这个平均返回时间指的就是第一次随机出来某个东西的时间的期望.

如果要不严谨地证明的话可以尝试用等比数列求和, 严谨的证明可以参考这篇讲稿.

那么我们考虑如何计算走到一个有ii条(算上重边和自环就是n+2in + 2i条)无用边的概率. 实际上这个概率就等于1P(1 - P(图连通)), 也就等于1f[i]((n2)i)1 - \frac{f[i]}{\binom{\binom{n}{2}}{i}}, 其中f[i]f[i]表示nn个点ii条边的连通图个数. (如果觉得无法接受, 可以考虑下这个问题本身的高度的对称性: 有ii条无用边的方案, 他们彼此间实际上是等概率的).

那么就这么愉快地做完啦! 时间复杂度O(n4)O(n^4).