763
个编辑
更改
跳到导航
跳到搜索
第23行：
第23行： − + 第44行：
第44行： − + − + 第54行：
第54行： + +
→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)的性质==
==<math>G(n,p)</math>的性质==
沿用上述符号，<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
沿用上述符号，<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=
*若<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>中的一个图几乎一定是连通的。
因此<math> \tfrac{\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
当<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
| title = The employee party problem
| title = The employee party problem
| volume = 19}}</ref>
| volume = 19}}</ref>
因此，尽管确定图中最大团的大小是[https://en.wikipedia.org/wiki/NP-complete NP完全的]，但“典型”图中最大团的大小（根据此模型）是非常好理解的。
因此，尽管确定图中最大团的大小是[https://en.wikipedia.org/wiki/NP-complete NP完全的]，但“典型”图中最大团的大小（根据此模型）是非常好理解的。
ER图的连边对偶图是几乎有着相同度分布的图，但具有度相关性，且集聚系数更高。<ref>{{cite journal |last1=Ramezanpour |first1=A. |last2=Karimipour |first2=V. |last3=Mashaghi |first3=A. |date=April 2003 |title=Generating correlated networks from uncorrelated ones |journal=Physical Review E |volume=67 |issue=4 |pages=046107
ER图的连边对偶图是几乎有着相同度分布的图，但具有度相关性，且集聚系数更高。<ref>{{cite journal |last1=Ramezanpour |first1=A. |last2=Karimipour |first2=V. |last3=Mashaghi |first3=A. |date=April 2003 |title=Generating correlated networks from uncorrelated ones |journal=Physical Review E |volume=67 |issue=4 |pages=046107