论文部分内容阅读
相变性质是ER(Erdos-Rényi)随机图理论具有的重要性质,一个简单无向图G=(V,E)中的k独立集是一个具有k个顶点的独立集.为更好地理解ER随机图中k独立集的结构特性,提出并利用一阶矩和二阶矩方法严格证明了当2≤k=ο(n)时随机图G(n,p)中k独立集出现相变的临界概率pc=1-n-2k-1.利用m≈pC2n时随机图G(n,p)和G(n,m)等价的性质给出了随机图G(n,m)中k独立集出现相变的临界边数mc=n(n-1)21-n-2k-1.实验结果表明:当2≤k=ο(n)时,随机图G