作者：卢友军; 许道云相变性质随机图临界概率临界边数
摘要：相变性质是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(n,p)和G(n,m)中存在k独立集的理论临界值和仿真得到的临界值一致且临界值与图节点总数n和独立集节点数k有关,而当k=ω(n)时,随机图G(n,p)和G(n,m)中存在k独立集的理论临界值和仿真临界值不一致.
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
