c语言 判断一个图是否全连通_随机图模型

随机图模型

数学家是一种把咖啡变成定理的机器。--- Alfred Renyi A mathematician is a machine for turning coffee into theorems. --- Alfred Renyi

随机图的历史

在 1959 和 1968 年期间，数学家 Paul Erdos 和 Alfred Renyi 发表了关于随机图（Random Graph）的一系列论文，在图论的研究中融入了组合数学和概率论，建立了一个全新的数学领域分支---随机图论。

随机图的定义

本文只关注无向图的场景。顾名思义，随机图（Random Graph）就是将一堆顶点随机的连接上边。好比在地上撒了一堆豆子，而豆子之间是否用线来相连是根据某个概率值来确定的。通常来说，对于随机图而言有两种定义方式

1. 【定义一】给定
   和
   的定义是随机从
   个顶点和
   条边所生成的所有图集合中选择一个。其中，这样的图集合的势是
   因此获得其中某一个图的概率是
2. 【定义二】给定
   和
   ，
   的定义是有
   个顶点，并且两个顶点之间以概率
   来决定是否连边。

事实上，这两个定义是等价的，

另一方面，对于

进一步地，通过以上两个公式可以得到：

在定义一中，可以直接算出所有顶点的平均度是

随机图的度

图的度（degree）指的是对于某个顶点而言，与它相关联的边的条数。对于随机图

对于随机图

特别地，当

因此，在

随机图的连通分支

对于随机图

对于随机图

1. 当
   那么
2. 当
   那么
3. 当
   那么巨连通分支（Giant Component）存在，同时存在很多小的连通分支，在临界点
   的附近时，
   这里
4. 当
   那么图
   是全连通图，i.e.

在这个定理中，对于顶点的平均度

整个定理的证明有点复杂，但本文将会介绍两个临界点的计算。先来考虑第一个临界点

用

对于不在最大连通分支的顶点

根据

令

近似方程：

令

1. 当
   时，
   在
   上成立，i.e.
   在
   上的唯一解是
   换言之，
2. 当
   时，
   在
   成立，
   在
   成立。换言之，
   在
   上除了零之外还有解
   此时会存在巨连通分支，
   是解。

因此，最大连通分支的顶点数在这个点会出现突变，

再来考虑第二个临界点

两边求对数可以得到

随机图的六度分离

六度分离又称为小世界现象，它的含义是在地球上任意选择两个人，他们之间最多相隔

图中两个顶点的距离定义为两个顶点之间的最短路径长度，图的直径就是图中任意两点的距离的最大值。对于随机图

1. 个距离为
   的顶点；
2. 个距离为
   的顶点；
3. 个距离为
   的顶点；
4. 个距离为
   的顶点；

同时，

而随机图的直径的量级是与

参考文献

1. Erdos Renyi Model：https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model
2. Giant Component：https://en.wikipedia.org/wiki/Giant_component
3. Erdős P, Rényi A. On the evolution of random graphs[J]. Publ. Math. Inst. Hung. Acad. Sci, 1960, 5(1): 17-60.
4. Albert R, Barabási A L. Statistical mechanics of complex networks[J]. Reviews of modern physics, 2002, 74(1): 47.
5. 《巴拉巴西网络科学》，艾伯特-拉斯洛·巴拉巴西（Albert-LászlóBarabási），2020.