随机图G(2n,p)中k-匹配的相变性质  

Phase Transitions Properties of k-Matchings In Random Graph G(2n,p)

作　　者：林妤[1] 许道云[2] 

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

出　　处：《贵州大学学报（自然科学版）》2014年第1期69-74,共6页Journal of Guizhou University:Natural Sciences

基　　金：国家自然科学基金项目资助(61262006)

摘　　要：随机图G(n,p)模型中有两个参数n和p,n表示图中的结点数,p表示图中任意两个不同结点之间独立生成边的概率。证明了随机图G(2n,p)中存在k-匹配的临界值为p=kn-2。实验分析了随机图G(2n,p)实例中10-匹配和25-匹配以及k=n-1匹配的相变。最后总结出临界函数与匹配的边数和结点数有关系。实验表明,理论与实验一致。There are two parameters n and p in random graphs model G（n,p）. Here n is the number of vertices of the graph and p is the edge probability. For each pair of vertices, u and v , the edge （u,v） is present with probability p. The property that G（2n,p） has k matching has phase transition at p = kn-2 . Experimental verifi- cation the phase transition of 10-matching and 25-matching and k = （n - 1 ）-matching in random graphs G（2n, p）. Finally, it is concluded that the threshold function is related with the vertuces and the number of edges of the matching. Validation showed that the theoretical results are in conformity with the experimental results.

关 键 词：随机图 k-匹配 相变 

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