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

Phase Transitions Properties of k-Clique in Random Graph G( n,p)

作　　者：卢友军 许道云[2] 

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

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

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

摘　　要：随机图G(n,p)模型是随机图理论中最重要的模型之一。该模型中有两个参数n和p,n表示图中的顶点数,p表示图中的任意两个不同顶点之间独立生成边的概率。证明了随机图G(n,p)中存在k-团的临界值为p=n-2k-1;同时证明了随机图G(n,p)中具有k≥3顶点孤立团的连通分量数服从均值λ=e-x-k3/k!的泊松分布;最后,数值实验分析随机图G(n,p)实例中3-团和10-团的相变。数值实验结果表明,实验与理论结果相符。One of the most important models in random G（n,p） graph theory is the random graph models, where n is the number of vertices of the graph and p is the probability generating independently edge between arbitrary 2 two different vertices in the model. It is shown that the threshold p = n-2/k-1 is for the existence of k -clique in random graph G（ n ,p）, and the distribution of the number of connected components of isolated clique with order k ≥ 3 is asymptotically Poisson with mean λ=e^-x-k3/k! The numerical experiment shows that the phase transition for the existence of 3-clique and 10-clique in random graph G（ n ,p） instances, the results of numerical testing shows the consistence between experimental and theoretical resuhs.

关 键 词：随机图 k-团 相变 

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