随机图

在数学中，随机图是指由随机过程产生的图。随机图的理论处于图论和概率论的交叉地带，主要研究各种经典随机图的性质。第一批关于随机图的结果是保罗·埃尔德什和阿尔弗雷德·雷尼在1959年至1966年的一系列论文中提出的。

概念随机图(random graph)是一类重要的图。它是伴随有不确定性的图.按某种随机方式删去一个图G的某些节点或边而保留下来的图称为随机子图，又称随机图。G称为随机图的原始图随机图的性质与原始图及随机删除部分节点或边的方式有关。随机删除方式包括只删点、只删边和既删点又删边三种。研究较多的原始图有完全图和晶形图。若按某种删除方式得到的一类随机图看成是概率空间，则有关的图的不变量或参数就是该空间的随机变量。从任一节点出发，按不过重复节点的原则，可随机走遍所有节点的图称为随机哈密顿图。从任一节点出发，按不过重复边的原则，可随机走遍所有边而回到出发点的图称为随机可迹图。若原始图为完全图，且按随机删边方式得到的任一随机图边数固定，则称这样的随机图为定边数随机图。若原始图为完全图，每条边删除的概率相同且各边的删除相互独立，则这种随机图称为定边密度随机图1。

定义与模型随机图的“随机”二字体现在边的分布上。一个随机图实际上是将给定的顶点之间随机地连上边。假设将一些纽扣散落在地上，并且不断随机地将两个纽扣之间系上一条线，这样就得到一个随机图的例子。边的产生可以依赖于不同的随机方式，这样就产生了不同的随机图模型。一个典型的模型是埃尔德什和雷尼共同研究的ER模型。ER模型是指在给定n个顶点后，规定每两个顶点之间都有p的概率连起来（0⩽p⩽1），而且这些判定之间两两无关。这样得到的随机图一般记作Gnp或ERn(p)。

另一种随机图模型叫做内积模型。内积模型的机制是对每一个顶点指定一个实系数的向量，而两个顶点之间是否连接的概率则是它们的向量的内积的函数2。

一般来说，可以定义任意两个顶点之间相连的概率，这个概率也被称为边概率。定义更广泛的随机图模型的方法是定义所谓的网络概率矩阵。这个矩阵的系数就是边概率，因此详细刻画了随机图的模型。

随机规则图是随机图中特殊的一类，它的性质可能会与一般的随机图不同。

性质随着边概率的不同，随机图可能会呈现不同的属性。对于最典型的ER模型，埃尔德什与雷尼研究了当顶点数目 n 趋向于正无穷大时，ER随机图的性质与概率p 之间的关系。他们发现，当 p 的值越过某些门槛时，ER随机图的性质会发生突然的改变。ER随机图的许多性质都是突然涌现的，比如说，当 p 的值小于某个特殊值之前，随机图具有某个性质的可能性等于0，但当 p 的值大于这个特殊值以后，随机图具有这个性质的可能性会突然变成12。

举例来说，当概率 p 大于某个临界值 pc(n) 后，生成的随机图几乎必然是连通的（概率等于1）。也就是说，对于散落在地上的 n 个纽扣，如果你以这样的概率 p 将两个纽扣之间系上线，那么你拿起一颗纽扣时就几乎能带起所有的纽扣了。

随机树随机树是随机图的一类。如同随机图一样，随机树是一个经由随机过程建立的树。随机树的一种生成方法是利用随机置换。首先生成一个 n(n−1)/2 阶随机置换函数，将 n(n−1)/2个可能连起来的边标上 1 至 n(n−1)/2的序号。然后按照从小到大的序号排列为原本没有边的图一一添加边。添加第 k条边时，如果发现添加后会导致图中出现一个圈，那么就放弃添加这条边，而开始添加第 k+1条边。最后得到的就是一个随机树。

本词条内容贡献者为:

孙和军 - 副教授 - 南京理工大学