黄 斌，吴春旺，郑丰华,蔺 冰

(1.成都信息工程学院数学学院， 四川 成都 610225;2.成都信息工程学院网络工程学院，四川 成都 610225;3.成都信息工程学院计算中心和网络舆情研究所，四川 成都 610225)

1 引言

近十多年来，随着对复杂网络研究热潮的兴起，随机图成为一种重要的复杂网络模型，常常称作随机网络或随机图[1，2]。人们对复杂网络的鲁棒性、传播动力学等的研究，常常会用到随机图，即需要生成随机图模型。Erdös P和Rényi A最早研究随机图时，他们对随机图的本质做了大量的研究[3]。 随机图包含两个最基本的随机图模型[4～6]：第一种随机图模型是对给定的n个顶点的空图，任选两个顶点，两个顶点连边的概率为p所得到的一个图；而第二种随机图模型是随机选择具有M条边和n个顶点的一个图。第一种随机图模型是由Gilbert E N首先提出的[7]，而第二种随机图模型是由Erdös P和 Rényi A 提出的[4]，人们在不至于混淆的前提下，提及随机图是这两种模型中的一种。时至今日，随机图又被称为ER(Erdös-Rényi)图。自从随机图建立以来, 对随机图的研究就从未停止过，随着对随机图研究的深入，随机图的理论和应用得到极大的发展，如随机图的连通性[3]、随机图的着色[8]及色数[9，10]等等。

在复杂网络研究中，生成随机图的加边的概率小于其阈值时生成图是不连通的[3]，这对进一步研究产生了一定的困难，也不便于用随机图模仿现实中的网络，而现实世界的绝大多数网络都是连通的，如互联网、电力网、交通网等。另外，随机图模型……