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

发布时间：2018-08-28 09:01

【摘要】：相变性质是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-独立集的理论临界值和仿真临界值不一致.
[Abstract]:The property of phase transition is an important property of ER (Erdos-Renyi) random graph theory. A k-independent set in a simple undirected graph G = (vwe E) is an independent set with k vertices. In order to better understand the structural properties of an independent set in a ER random graph, the critical probability of phase transition in a random graph G (n ~ (1 / 2) is strictly proved by the first-order and second-order moment methods. The critical probability of the phase transition of the kindependent set in G (n ~ (1 / 2) is proved strictly by using the first-order moment and second-order moment method, and the critical probability of the phase transition of the k-independent set in G (n ~ (1 / 2) is proved by the method of first-order moment and second-order moment. By using the equivalent properties of m 鈮，

本文编号：2208925