随机图

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

概念

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

定义与模型

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