背景：

图：图是一些顶点以及连接顶点的边的集合。相关概念可以参考这里。

随机图：一个包含 n 个顶点的简单图，其中每两个顶点间存在边的可能性为 p。这样的图记为 G(n, p)。

连通图：在无向图 G 中，两个顶点 u 和 v 被称为是连通的，如果 G 中存在一条从 u 到 v 的路径。否则，它们就被称为是不连通的。如果图中的每对不同的顶点间都是连通的，那么这个图也就被称为是连通的。否则，它被称为是不连通的。

路径：图论中，一条路径就是连接着一系列有序顶点的一系列的有序边。一条路径可以是无限的，但是一条有限路径总是有第一个顶点，称为起始点，并且有最后一个顶点。它们都称作是终端顶点。其他的顶点是内部顶点。

环：一个环就是起始顶点与结束顶点相同的一条路径。在环中，起始顶点的挑选是任意的。

树：树是不含有环的连通图。

问题：

对于一个随机图 G(n, p)，它是连通的概率是多少？

解：

用 P(n) 表示 G(n, p) 的连通概率，那么有这样的递推公式：

P\left(n\right)=1-\sum _{k=1}^{n-1}C_{n-1}^{k-1}P\left(k\right)\left(1-p\right)^{k\left(n-k\right)}

证明：

首先，我们规定一个顶点是一个连通图，而且因为它不含有环，所以它也是一棵树。即 P(1) = 1，因为由于这个规定，那么由一个顶点构成的图一定是连通的。

然后，我们再引入一个孤立子树的概念。一个孤立子树，是图的一部分，它本身是连通的（树的概念保证连通），然而它内部的每一个顶点，和图中该子树外面的任意顶点都不连通（即不存边）。

其次有一个很浅显的命题：对于 G(n, p)，如果它不连通，则其一定含有两个或者以上的孤立子树。反之也成立。

下面，我们试图先求出 G(n, p) 不连通的概率 Q(n)，然后它连通的概率可以很简单地由 P(n) = 1 - Q(n) 得出。

现在我们从 G(n, p) 中任意选出 k 个顶点组成的区域 A(k)，它是孤立子树的概率是P\left(k\right)\cdot q^{k\left(n-k\right)}。

其中 q = 1 - p，即任意两个顶点不连通的概率。

1. 因为要 A(k) 是孤立子树，那么首先它是连通的，这个概率是 P(k)；

2. 其次对于A(k)外的某一个顶点，它与A(k)内���k个顶点都不连通的概率是q^k。然后，这样的点共有 n-k 个，所以A(k)外的每个顶点与 A(k) 内部所有k个顶点都不连通的概率即为q^{k\cdot \left(n-k\right)}。

两个条件同时满足，使用乘法即得到 P\left(k\right)\cdot q^{k\left(n-k\right)}。

现在，我们来对 G(n, p) 不连通这个事件空间进行分割，分割时要注意不重复，不遗漏。为了方便地做到这一点，我们将焦点放在G(n, p)中的一个特定顶点 v 上。那么 G(n, p) 不连通等价于：

v 是一棵孤立子树IsolatedTree(1) (注意这个概率是 P{A(k=1) 是孤立子树} =
P\left(k\right)\cdot q^{k\left(n-k\right)}=P(1) \cdot q^{1 \cdot (n-1)}=P(1)q^{n-1})；或者

v 与另外一点构成一棵孤立子树 IsolatedTree(2) (注意这个概率是 P{A(k=2) 是孤立子树} =
P\left(k\right)\cdot q^{k\left(n-k\right)}=P(2) \cdot q^{2 \cdot (n-2)}=P(2)q^{2(n-2)})。
而这另外一点的选取方式共有 C_{n-1}^1 种；或者

...

v 与另外k-1个点构成一棵孤立子树 IsolatedTree(k) (注意这个概率是 P{A(k) 是孤立子树} =
P\left(k\right)\cdot q^{k\left(n-k\right)}。
而这另外的k-1个点的选取方式共有C_{n-1}^{k-1}种；或者

...

v 与另外(n-2)个点构成一棵孤立子树 IsolatedTree(n-1) (注意这个概率是 P{A(k=(n-1)) 是孤立子树} =
P\left(k\right)\cdot q^{k\left(n-k\right)}=P(n-1) \cdot q^{(n-1) \cdot (n-(n-1))}=P(n-1)q^{n-1}。
而这另外的(n-2)个点的选取方式共有C_{n-1}^{n-2}种。

再没有其他情况，而且也没有重复的情况。

这些情况是或者的关系，将它们的概率加起来，即得到 G(n, p) 不连通的概率 Q(n)=\sum _{k=1}^{n-1}C_{n-1}^{k-1}P\left(k\right)\left(1-p\right)^{k\left(n-k\right)}

最后，得到随机图 G(n, p) 连通的概率是P(n) = 1 - Q(n)，即

P\left(n\right)=1-\sum _{k=1}^{n-1}C_{n-1}^{k-1}P\left(k\right)\left(1-p\right)^{k\left(n-k\right)}

【证毕】

特别说明：

对于 G(1, p)，其连通的概率是 P(1) = 1；

对于 G(2, p)，其连通的概率是 P\left(2\right)=C_1^0P\left(1\right)q^1=q

对于 G(3, p)，其连通的概率是 P\left(3\right)=C_2^0P\left(1\right)q^2+C_2^1P\left(2\right)q^2=q^2+2q^3

直观的在线实验：

请点击 http://zizhujy.com/GraphWorld 进行在线实验：