更改

跳到导航 跳到搜索
添加155字节 、 2020年9月6日 (日) 18:32
第35行: 第35行:  
A closely related model, the Erdős–Rényi model denoted G(n,M), assigns equal probability to all graphs with exactly M edges. With 0 ≤ M ≤ N, G(n,M) has <math>\tbinom{N}{M}</math> elements and every element occurs with probability <math>1/\tbinom{N}{M}</math>.  The latter model can be viewed as a snapshot at a particular time (M) of the random graph process <math>\tilde{G}_n</math>, which is a stochastic process that starts with n vertices and no edges, and at each step adds one new edge chosen uniformly from the set of missing edges.
 
A closely related model, the Erdős–Rényi model denoted G(n,M), assigns equal probability to all graphs with exactly M edges. With 0 ≤ M ≤ N, G(n,M) has <math>\tbinom{N}{M}</math> elements and every element occurs with probability <math>1/\tbinom{N}{M}</math>.  The latter model can be viewed as a snapshot at a particular time (M) of the random graph process <math>\tilde{G}_n</math>, which is a stochastic process that starts with n vertices and no edges, and at each step adds one new edge chosen uniformly from the set of missing edges.
   −
一个密切相关的模型,Erdős-Rényi 模型表示''G'' (''n'',''M''),给每一个正好有''M''条边的图赋予等概率。当0≤ ''M'' ≤ ''N'' 时,''G'' (''n'',''M'')具有 <math>\tbinom{N}{M}</math> 元素,且每个元素都以概率<math>1/\tbinom{N}{M}</math> 出现。后一个模型可以看作是随机图过程<math>\tilde{G}_n</math>某个特定时间(''M'')的一个快照,这个时间(''M'')是从 n 个顶点开始没有边的一个随机过程,每个步骤均匀地从缺失的边集中选择一个新的边。
+
一个密切相关的模型,'''<font color="#FF8000">Erdős-Rényi 模型 Erdős–Rényi Model </font>'''表示''G'' (''n'',''M''),给每一个正好有''M''条边的图赋予等概率。当0≤ ''M'' ≤ ''N'' 时,''G'' (''n'',''M'')具有 <math>\tbinom{N}{M}</math> 元素,且每个元素都以概率<math>1/\tbinom{N}{M}</math> 出现。后一个模型可以看作是随机图过程<math>\tilde{G}_n</math>某个特定时间(''M'')的一个快照,这个时间(''M'')是从 n 个顶点开始没有边的一个随机过程,每个步骤均匀地从缺失的边集中选择一个新的边。
      第43行: 第43行:  
If instead we start with an infinite set of vertices, and again let every possible edge occur independently with probability 0 < p < 1, then we get an object G called an infinite random graph. Except in the trivial cases when p is 0 or 1, such a G almost surely has the following property:
 
If instead we start with an infinite set of vertices, and again let every possible edge occur independently with probability 0 < p < 1, then we get an object G called an infinite random graph. Except in the trivial cases when p is 0 or 1, such a G almost surely has the following property:
   −
如果我们从一个无限的顶点集合开始,然后再次让每个可能的边以概率0 < ''p'' < 1独立出现,那么我们得到一个对象 ''G'' 称为无限随机图。除了在 ''p'' = 0或1的平凡情况下,这样的 ''G'' 几乎肯定具有以下性质:
+
如果我们从一个无限的顶点集合开始,然后再次让每个可能的边以概率0 < ''p'' < 1独立出现,那么我们得到一个对象 ''G'' 称为'''<font color="#FF8000">无限随机图 Infinite Graph </font>'''。除了在 ''p'' = 0或1的平凡情况下,这样的 ''G'' 几乎肯定具有以下性质:
      第59行: 第59行:  
It turns out that if the vertex set is countable then there is, up to isomorphism, only a single graph with this property, namely the Rado graph. Thus any countably infinite random graph is almost surely the Rado graph, which for this reason is sometimes called simply the random graph. However, the analogous result is not true for uncountable graphs, of which there are many (nonisomorphic) graphs satisfying the above property.
 
It turns out that if the vertex set is countable then there is, up to isomorphism, only a single graph with this property, namely the Rado graph. Thus any countably infinite random graph is almost surely the Rado graph, which for this reason is sometimes called simply the random graph. However, the analogous result is not true for uncountable graphs, of which there are many (nonisomorphic) graphs satisfying the above property.
   −
结果表明,如果顶点集是可数的,那么在同构意义下,只有一个图具有这个性质,即 Rado 图。因此,任何可数无限随机图几乎可以肯定是 Rado 图,由于这个原因,有时被简称为随机图。然而,对于'''<font color="#FF8000">不可数图 Uncountable Graph </font>'''类似的结果是不正确的,不可数图中有许多'''<font color="#F8000">(不同构)图 Nonisomorphic Graph </font>'''满足上述性质。
+
结果表明,如果顶点集是可数的,那么在'''<font color="#FF8000">同构 Isomorphism </font>'''意义下,只有一个图具有这个性质,即 Rado 图。因此,任何可数无限随机图几乎可以肯定是 Rado 图,由于这个原因,有时被简称为随机图。然而,对于'''<font color="#FF8000">不可数图 Uncountable Graph </font>'''类似的结果是不正确的,不可数图中有许多'''<font color="#FF8000">(不同构)图 Nonisomorphic Graph </font>'''满足上述性质。
      第99行: 第99行:  
Once we have a model of random graphs, every function on graphs, becomes a random variable. The study of this model is to determine if, or at least estimate the probability that, a property may occur.
 
Once we have a model of random graphs, every function on graphs, becomes a random variable. The study of this model is to determine if, or at least estimate the probability that, a property may occur.
   −
一旦我们有了一个随机图的模型,图上的每个函数都变成了一个随机变量。对这个模型的研究是为了确定,或者至少是估计一个特性可能发生的概率。
+
一旦我们有了一个随机图的模型,图上的每个函数都变成了一个随机变量。对这个模型的研究是为了确定,或者至少估计一个属性可能发生的概率。
    
<br>
 
<br>
274

个编辑

导航菜单