763
个编辑
更改
跳到导航
跳到搜索
第35行：
第35行： − 故当n很大且np=常数时，服从[https://en.wikipedia.org/wiki/Poisson_distribution 泊松分布]。+ − + − + − +
→G(n,p)的性质
其中n为图中节点的总数。由于
其中n为图中节点的总数。由于
:<math>P(\deg(v) = k) \to \frac{(np)^k \mathrm{e}^{-np}}{k!} \quad \text{ as } n \to \infty \text{ and } np = \text{ constant },</math>
:<math>P(\deg(v) = k) \to \frac{(np)^k \mathrm{e}^{-np}}{k!} \quad \text{ as } n \to \infty \text{ and } np = \text{ constant },</math>
故当<math>n</math>很大且<math>np=</math>常数时，服从[https://en.wikipedia.org/wiki/Poisson_distribution 泊松分布]。
在1960年的一篇论文中，Erdős和Rényi<ref name="Erdos1960">{{cite journal |last=Erdős |first=P. |last2=Rényi |first2=A. |year=1960 |title=On the evolution of random graphs|journal=Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publications of the Mathematical Institute of the Hungarian Academy of Sciences] |volume=5 |issue=|pages=17–61|id= |url=http://www.renyi.hu/~p_erdos/1960-10.pdf |accessdate= |quote= |doi=}} 这里的概率p指的是<math>N(n) = \tbinom{n}{2} p</math></ref>非常精确地描述了p在不同取值下<math>G(n, p)</math>的表现。其结论有：
在1960年的一篇论文中，Erdős和Rényi<ref name="Erdos1960">{{cite journal |last=Erdős |first=P. |last2=Rényi |first2=A. |year=1960 |title=On the evolution of random graphs|journal=Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publications of the Mathematical Institute of the Hungarian Academy of Sciences] |volume=5 |issue=|pages=17–61|id= |url=http://www.renyi.hu/~p_erdos/1960-10.pdf |accessdate= |quote= |doi=}} 这里的概率p指的是<math>N(n) = \tbinom{n}{2} p</math></ref>非常精确地描述了p在不同取值下<math>G(n, p)</math>的表现。其结论有：
*若np<1，则<math>G(n,p)</math>中的一个图几乎一定没有连通分量的大小大于<math>O(log(n))</math>。
*若<math>np<1</math>，则<math>G(n,p)</math>中的一个图几乎一定没有连通分量的大小大于<math>O(log(n))</math>。
*若np=1，则<math>G(n,p)</math>中的一个图几乎必有最大的连通分量，其阶为n <sup>2/3</sup>。
*若<math>np=1</math>，则<math>G(n,p)</math>中的一个图几乎必有最大的连通分量，其阶为<math>n^{2/3}</math>。
*若np→c>1，其中c为常数，则<math>G(n,p)</math>中的一个图几乎必有唯一的包含节点有限部分的巨连通集团。没有连通分量会有超过<math>O(log(n))</math>个节点。
*若<math>np→c>1</math>，其中<math>c</math>为常数，则<math>G(n,p)</math>中的一个图几乎必有唯一的包含节点有限部分的巨连通集团。没有连通分量会有超过<math>O(log(n))</math>个节点。
*若<math>p<\tfrac{(1-\varepsilon)\ln n} n</math>，则<math>G(n,p)</math>中的一个图几乎必有孤立节点，因而它是不连通的。
*若<math>p<\tfrac{(1-\varepsilon)\ln n} n</math>，则<math>G(n,p)</math>中的一个图几乎必有孤立节点，因而它是不连通的。
*若 <math>p{>}\tfrac{(1+\varepsilon)\ln n} n</math>，则<math>G(n,p)</math>中的一个图几乎一定是连通的。
*若 <math>p{>}\tfrac{(1+\varepsilon)\ln n} n</math>，则<math>G(n,p)</math>中的一个图几乎一定是连通的。