763
个编辑
更改
→G(n, p)的性质
[[File:1280px-Erdos generated network-p0.01.jpg|200px|thumb|right|二项分布ER模型生成的一个图<math>（p=0.01）</math>]]
[[File:1280px-Erdos generated network-p0.01.jpg|200px|thumb|right|二项分布ER模型生成的一个图<math>（p=0.01）</math>]]
==G(n, p)的性质==
==G(n,p)的性质==
沿用上述符号，<math>G(n,p)</math>中的一个图平均有<math>\binom{n}{2}p</math>条连边。任意特定节点的度服从[https://en.wikipedia.org/wiki/Binomial_distribution 二项分布]：<ref>{{cite journal |last= Newman |first= Mark. E. J. |authorlink= |last2=Strogatz |first2=S. H. |last3=Watts |first3=D. J. |year= 2001 |title= Random graphs with arbitrary degree distributions and their applications|journal= Physical Review E|volume=64 |issue= |pages=026118
|id=
|id=
|url=
|url=
.[https://en.wikipedia.org/wiki/ArXiv arxiv]:[https://arxiv.org/abs/cond-mat/0007235 cond-mat/0007235]
.[https://en.wikipedia.org/wiki/ArXiv arxiv]:[https://arxiv.org/abs/cond-mat/0007235 cond-mat/0007235]
.[https://en.wikipedia.org/wiki/Bibcode bibcode]:[http://adsabs.harvard.edu/abs/2001PhRvE..64b6118N 2001PhRvE..64b6118N]}}, Eq. (1)</ref>
.[https://en.wikipedia.org/wiki/Bibcode bibcode]:[http://adsabs.harvard.edu/abs/2001PhRvE..64b6118N 2001PhRvE..64b6118N]}}, Eq. (1)</ref>
:<math>P(\deg(v) = k) = {n-1\choose k}p^k(1-p)^{n-1-k},</math>
其中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>
故当n很大且np=常数时，服从[https://en.wikipedia.org/wiki/Poisson_distribution 泊松分布]。
故当n很大且np=常数时，服从[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在不同取值下G(n, p)的表现。其结论有：
*若np<1，则G(n, p)中的一个图几乎一定没有连通分量的大小大于O(log(n))。
*若np=1，则G(n, p)中的一个图几乎必有最大的连通分量，其阶为n <sup>2/3</sup>。
在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→c>1，其中c为常数，则G(n, p)中的一个图几乎必有唯一的包含节点有限部分的[[巨连通集团]]。没有连通分量会有超过O(log(n))个节点。
*若np<1，则<math>G(n,p)</math>中的一个图几乎一定没有连通分量的大小大于<math>O(log(n))</math>。
*若<math>p<\tfrac{(1-\varepsilon)\ln n} n</math>，则G(n, p)中的一个图几乎必有孤立节点，因而它是不连通的。
*若np=1，则<math>G(n,p)</math>中的一个图几乎必有最大的连通分量，其阶为n <sup>2/3</sup>。
*若 <math>p{>}\tfrac{(1+\varepsilon)\ln n} n</math>，则G(n, p)中的一个图几乎一定是连通的。
*若np→c>1，其中c为常数，则<math>G(n,p)</math>中的一个图几乎必有唯一的包含节点有限部分的巨连通集团。没有连通分量会有超过<math>O(log(n))</math>个节点。
因此<math> \tfrac{\ln n} n</math>是G(n, p)连通性的重要临界值。
*若<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> \tfrac{\ln n} n</math>是<math>G(n,p)<\math>连通性的重要临界值。
当<math>n</math>趋于无穷大时，还有许多图的性质几乎处处成立。例如，存在<math>k(n)</math>（近似等于<math>2log^2(n)<\math>）使得<math>G(n,0.5)</math>中最大团的大小几乎必为<math>k(n)</math>或<math>k(n)+1</math>。<ref>{{cite journal
| last = Matula | first = David W.
| last = Matula | first = David W.
| date = February 1972
| date = February 1972