随机图中k-独立集的相变性质  

Phase Transition Properties of k-Independent Sets in Random Graphs

作　　者：卢友军 许道云[1] Lu Youjun;Xu Daoyun(College of Computer Science and Technology, Guizhou University, Guiyang 550025)

机构地区：[1]贵州大学计算机科学与技术学院,贵阳550025

出　　处：《计算机研究与发展》2017年第12期2841-2848,共8页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61262006;61462001;61540050;61762019);贵州省重大应用基础研究项目(JZ20142001);贵州大学研究生创新基金项目(2016047)~~

摘　　要：相变性质是ER(Erdos-Renyi)随机图理论具有的重要性质,一个简单无向图G=(V,E)中的k-独立集是一个具有k个顶点的独立集.为更好地理解ER随机图中是一独立集的结构特性,提出并利用一阶矩和二阶矩方法严格证明了当2≤k=o(n^(1/2))时随机图G(n,p)中k-独立集出现相变的临界概率p_c=1-n^(-2/(k-1)).利用m≈pC_n^2时随机图G(n,p)和G(n,m)等价的性质给出了随机图G(n,m)中k-独立集出现相变的临界边数m_c=[((n(n-1))/2)(1-n^(-2/(k-1)))].实验结果表明:当2≤k=o(n^(1/2))时,随机图G(n,p)和G(n,m)中存在k-独立集的理论临界值和仿真得到的临界值一致且临界值与图节点总数n和独立集节点数k有关,而当k=ω(n^(1/2))时,随机图G(n,p)和G(n,m)中存在k-独立集的理论临界值和仿真临界值不一致.Phase transition property is one of the most important properties of the theory of Erds Rényi random graphs.A subset of vertices is a k independent set in a simple undirected graph G=(V,E)if the subset is an independent set containing k vertex.In order to understand the structural property of k independent sets in Erds Rényi random graphs,the phase transition properties of k independent sets in Erds Rényi random graphs are investigated in this paper.It is shown that the threshold probability is pc=1-n-2k-1for the existence of k independent sets in random graph G(n,p)via the first moment method and the second moment method when2≤k=ο(n).According to this fact that random graph G(n,p)is equivalent to random graph G(n,m)when m is close to pC2n,the threshold edge number is given by mc=n(n-1)21-n-2k-1for the existence of k independent sets in random graph G(n,m).The simulation results show that the consistence between simulation and theoretical threshold value for the existence of k independent sets in random graph G(n,p)and G(n,m)when2≤k=ο(n),and the threshold value is related to the total number n of vertices and the number k of vertices of independent set.However,when k=ω(n),the theoretical threshold value is not consistent with the simulation threshold value for the existence of k independent sets in random graph G(n,p)and G(n,m).

关 键 词：相变性质 随机图 k-独立集 临界概率 临界边数 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]