763
个编辑
更改
跳到导航
跳到搜索
第14行：
第14行： − + − + − +
→两种模型的比较
==两种模型的比较==
==两种模型的比较==
<math>G(n,p)</math>中可能的连边数为<math>\binom{n}{2}p</math>，由[https://en.wikipedia.org/wiki/Law_of_large_numbers 大数定律]，<math>G(n,p)</math>中的每个图几乎必有大概这么多连边（假设可能的连边数趋于无穷）。因此，粗略的结果是如果pn<sup>2</sup> → ∞，那么当<math>M=\tbinom{n}{2} p</math>随着n的增加而增加时，<math>G(n,p)</math>将与<math>G(n,M)</math>有相似的表现。许多图的性质都是这样。如果P是满足对子图序[https://en.wikipedia.org/wiki/Monotonic_function 单调]的任意一种图的性质（即若A是B的子图且A满足P，则B也满足P），那么命题“<math>G(n,p)</math>中几乎所有图满足P”等价于“<math> G(n, \tbinom{n}{2} p) </math>中几乎所有图满足<math>P</math>”（其中pn<sup>2</sup> → ∞）。
<math>G(n,p)</math>中可能的连边数为<math>\binom{n}{2}p</math>，由[https://en.wikipedia.org/wiki/Law_of_large_numbers 大数定律]，<math>G(n,p)</math>中的每个图几乎必有大概这么多连边（假设可能的连边数趋于无穷）。因此，粗略的结果是如果<math>p^2 →∞</math>，那么当<math>M=\tbinom{n}{2} p</math>随着<math>n</math>的增加而增加时，<math>G(n,p)</math>将与<math>G(n,M)</math>有相似的表现。许多图的性质都是这样。如果P是满足对子图序[https://en.wikipedia.org/wiki/Monotonic_function 单调]的任意一种图的性质（即若<math>A</math>是<math>B</math>的子图且<math>A</math>满足<math>P</math>，则<math>B</math>也满足<math>P</math>），那么命题“<math>G(n,p)</math>中几乎所有图满足<math>P</math>”等价于“<math> G(n, \tbinom{n}{2} p) </math>中几乎所有图满足<math>P</math>”（其中pn<sup>2</sup> → ∞）。
例如，当<math>P</math>是[https://en.wikipedia.org/wiki/Connectedness 连通性]时，或P是包含[https://en.wikipedia.org/wiki/Hamiltonian_path 哈密顿圈]的性质时，上述关系就成立。然而，它对非单调性质（如具有偶数连边的性质）未必成立。
例如，当<math>P</math>是[https://en.wikipedia.org/wiki/Connectedness 连通性]时，或<math>P</math>是包含[https://en.wikipedia.org/wiki/Hamiltonian_path 哈密顿圈]的性质时，上述关系就成立。然而，它对非单调性质（如具有偶数连边的性质）未必成立。
如今在实际应用中，<math>G(n,p)</math>模型更加常用，部分原因是通过连边的独立性进行分析较为容易。
如今在实际应用中，<math>G(n,p)</math>模型更加常用，部分原因是通过连边的独立性进行分析较为容易。
[[File:1280px-Erdos generated network-p0.01.jpg|200px|thumb|right|二项分布ER模型生成的一个图（p=0.01）]]
[[File:1280px-Erdos generated network-p0.01.jpg|200px|thumb|right|二项分布ER模型生成的一个图<math>（p=0.01）</math>]]
==G(n, p)的性质==
==G(n, p)的性质==