背景:
图:图是一些顶点以及连接顶点的边的集合。相关概念可以参考这里。
随机图:一个包含 n 个顶点的简单图,其中每两个顶点间存在边的可能性为 p。这样的图记为 G(n, p)。
连通图:在无向图 G 中,两个顶点 u 和 v 被称为是连通的,如果 G 中存在一条从 u 到 v 的路径。否则,它们就被称为是不连通的。如果图中的每对不同的顶点间都是连通的,那么这个图也就被称为是连通的。否则,它被称为是不连通的。
路径:图论中,一条路径就是连接着一系列有序顶点的一系列的有序边。一条路径可以是无限的,但是一条有限路径总是有第一个顶点,称为起始点,并且有最后一个顶点。它们都称作是终端顶点。其他的顶点是内部顶点。
环:一个环就是起始顶点与结束顶点相同的一条路径。在环中,起始顶点的挑选是任意的。
树:树是不含有环的连通图。
问题:
对于一个随机图 G(n, p),它是连通的概率是多少?
解:
用 P(n) 表示 G(n, p) 的连通概率,那么有这样的递推公式:
证明:
首先,我们规定一个顶点是一个连通图,而且因为它不含有环,所以它也是一棵树。即 P(1) = 1,因为由于这个规定,那么由一个顶点构成的图一定是连通的。
然后,我们再引入一个孤立子树的概念。一个孤立子树,是图的一部分,它本身是连通的(树的概念保证连通),然而它内部的每一个顶点,和图中该子树外面的任意顶点都不连通(即不存边)。
其次有一个很浅显的命题:对于 G(n, p),如果它不连通,则其一定含有两个或者以上的孤立子树。反之也成立。
下面,我们试图先求出 G(n, p) 不连通的概率 Q(n),然后它连通的概率可以很简单地由 P(n) = 1 - Q(n) 得出。
现在我们从 G(n, p) 中任意选出 k 个顶点组成的区域 A(k),它是孤立子树的概率是
其中 q = 1 - p,即任意两个顶点不连通的概率。
1. 因为要 A(k) 是孤立子树,那么首先它是连通的,这个概率是 P(k);
2. 其次对于A(k)外的某一个顶点,它与A(k)内的k个顶点都不连通的概率是
。然后,这样的点共有 n-k 个,所以A(k)外的每个顶点与 A(k) 内部所有k个顶点都不连通的概率即为 。两个条件同时满足,使用乘法即得到
。现在,我们来对 G(n, p) 不连通这个事件空间进行分割,分割时要注意不重复,不遗漏。为了方便地做到这一点,我们将焦点放在G(n, p)中的一个特定顶点 v 上。那么 G(n, p) 不连通等价于:
v 是一棵孤立子树IsolatedTree(1) (注意这个概率是 P{A(k=1) 是孤立子树} =
);或者
v 与另外一点构成一棵孤立子树 IsolatedTree(2) (注意这个概率是 P{A(k=2) 是孤立子树} =
)。
而这另外一点的选取方式共有 种;或者
...
v 与另外k-1个点构成一棵孤立子树 IsolatedTree(k) (注意这个概率是 P{A(k) 是孤立子树} =
。
而这另外的k-1个点的选取方式共有 种;或者
...
v 与另外(n-2)个点构成一棵孤立子树 IsolatedTree(n-1) (注意这个概率是 P{A(k=(n-1)) 是孤立子树} =
。
而这另外的(n-2)个点的选取方式共有 种。
再没有其他情况,而且也没有重复的情况。
这些情况是或者的关系,将它们的概率加起来,即得到 G(n, p) 不连通的概率
最后,得到随机图 G(n, p) 连通的概率是P(n) = 1 - Q(n),即
【证毕】
特别说明:
对于 G(1, p),其连通的概率是 P(1) = 1;
对于 G(2, p),其连通的概率是
对于 G(3, p),其连通的概率是
直观的在线实验:
请点击 http://zizhujy.com/GraphWorld 进行在线实验: