随机图中k-独立集的相变性质
卢友军,许道云
2017, 54(12):
2843-2850.
doi:10.7544/issn1000-1239.2017.20160694
摘要
(
1115 )
HTML
(
2)
PDF (1700KB)
(
457
)
相关文章 |
计量指标
相变性质是ER(Erds-Rényi)随机图理论具有的重要性质,一个简单无向图G=(V,E)中的k-独立集是一个具有k个顶点的独立集.为更好地理解ER随机图中k-独立集的结构特性,提出并利用一阶矩和二阶矩方法严格证明了当2≤k=ο(n)时随机图G(n,p)中k-独立集出现相变的临界概率p\-c=1-n\+-2/k-1.利用m≈pC\+2\-n时随机图G(n,p)和G(n,m)等价的性质给出了随机图G(n,m)中k-独立集出现相变的临界边数m\-c=[n(n-1)/2(1-n\+-2/k-1)].实验结果表明:当2≤k=ο(n)时,随机图G(n,p)和G(n,m)中存在k-独立集的理论临界值和仿真得到的临界值一致且临界值与图节点总数n和独立集节点数k有关,而当k=ω(n)时,随机图G(n,p)和G(n,m)中存在k-独立集的理论临界值和仿真临界值不一致.