【摘要】：相變性質(zhì)是ER(Erdos-Renyi)隨機(jī)圖理論具有的重要性質(zhì),一個(gè)簡單無向圖G=(V,E)中的k-獨(dú)立集是一個(gè)具有k個(gè)頂點(diǎn)的獨(dú)立集.為更好地理解ER隨機(jī)圖中是一獨(dú)立集的結(jié)構(gòu)特性,提出并利用一階矩和二階矩方法嚴(yán)格證明了當(dāng)2≤k=o(n~(1/2))時(shí)隨機(jī)圖G(n,p)中k-獨(dú)立集出現(xiàn)相變的臨界概率p_c=1-n~(-2/(k-1)).利用m≈pC_n~2時(shí)隨機(jī)圖G(n,p)和G(n,m)等價(jià)的性質(zhì)給出了隨機(jī)圖G(n,m)中k-獨(dú)立集出現(xiàn)相變的臨界邊數(shù)m_c=[((n(n-1))/2)(1-n~(-2/(k-1)))].實(shí)驗(yàn)結(jié)果表明:當(dāng)2≤k=o(n~(1/2))時(shí),隨機(jī)圖G(n,p)和G(n,m)中存在k-獨(dú)立集的理論臨界值和仿真得到的臨界值一致且臨界值與圖節(jié)點(diǎn)總數(shù)n和獨(dú)立集節(jié)點(diǎn)數(shù)k有關(guān),而當(dāng)k=ω(n~(1/2))時(shí),隨機(jī)圖G(n,p)和G(n,m)中存在k-獨(dú)立集的理論臨界值和仿真臨界值不一致.
[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 鈮，

本文編號(hào)：2208925