更改

The theory of random graphs studies typical properties of random graphs, those that hold with high probability for graphs drawn from a particular distribution.  For example, we might ask for a given value of <math>n</math> and <math>p</math> what the probability is that <math>G(n,p)</math> is connected.  In studying such questions, researchers often concentrate on the asymptotic behavior of random graphs&mdash;the values that various probabilities converge to as <math>n</math> grows very large. Percolation theory characterizes the connectedness of random graphs, especially infinitely large ones.

The theory of random graphs studies typical properties of random graphs, those that hold with high probability for graphs drawn from a particular distribution.  For example, we might ask for a given value of <math>n</math> and <math>p</math> what the probability is that <math>G(n,p)</math> is connected.  In studying such questions, researchers often concentrate on the asymptotic behavior of random graphs&mdash;the values that various probabilities converge to as <math>n</math> grows very large. Percolation theory characterizes the connectedness of random graphs, especially infinitely large ones.

随机图理论研究随机图的典型性质，即从特定分布中抽取的图的高概率性质。例如，我们可以要求一个给定的值 <math>n</math> 和 <math>p</math> 什么是 <math>G(n，p)</math> 连接的概率。在研究这些问题时，研究人员往往集中在随机图的渐近行为上——各种概率收敛到的值变得非常大。'''<font color="#FF8000">渗流理论 Percolation Theory </font>'''刻画了随机图，特别是无穷大图的'''<font color="#FF8000">连通性 Connectedness </font>'''。

随机图理论研究随机图的典型性质，即从特定分布中抽取的图的高概率性质。例如，我们可以要求一个给定的值 <math>n</math> 和 <math>p</math> <math>G(n，p)</math> 连接的概率。在研究这些问题时，研究人员往往集中在随机图的趋近行为上——各种概率收敛到的值变得非常大。'''<font color="#FF8000">渗流理论 Percolation Theory </font>'''刻画了随机图，特别是无穷大图的'''<font color="#FF8000">连通性 Connectedness </font>'''。

Percolation is related to the robustness of the graph (called also network).  Given a random graph of <math>n</math> nodes and an average degree <math>\langle k\rangle</math>. Next we remove randomly a fraction <math>1-p</math> of nodes and leave only a fraction <math>p</math>. There exists a critical percolation threshold <math>p_c=\tfrac{1}{\langle k\rangle}</math> below which the network becomes fragmented while above <math>p_c</math> a giant connected component exists.

Percolation is related to the robustness of the graph (called also network).  Given a random graph of <math>n</math> nodes and an average degree <math>\langle k\rangle</math>. Next we remove randomly a fraction <math>1-p</math> of nodes and leave only a fraction <math>p</math>. There exists a critical percolation threshold <math>p_c=\tfrac{1}{\langle k\rangle}</math> below which the network becomes fragmented while above <math>p_c</math> a giant connected component exists.

'''<font color="#FF8000">渗流 Percolation </font>''' 与图形(也称为网络)的'''<font color="#FF8000">健壮性 Robustness </font>'''有关。给定一个随机图形，其中的节点是 <math>n</math> 和一个平均度 <math>\langle k\rangle</math> 。接下来我们随机移除一部分概率为 <math>1-p</math> 的节点，只留下一部分概率为 <math>p</math> 的节点。存在一个'''<font color="#FF8000">临界渗透阈值 Critical Percolation Threshold </font>'''<math>p_c=\tfrac{1}{\langle k\rangle}</math>，当低于这个临界渗透阈值，网络变得支离破碎，而高于临界渗透阈值 <math>p_c</math> 的网络则存在一个巨大的'''<font color="#FF800">连接元件 Connected Component </font>'''(图论)。

'''<font color="#FF8000">渗流 Percolation </font>''' 与图形(也称为网络)的'''<font color="#FF8000">紧密性 Robustness </font>'''有关。给定一个随机图形，其中的节点是 <math>n</math> 和一个平均度 <math>\langle k\rangle</math> 。接下来我们随机移除一部分概率为 <math>1-p</math> 的节点，只留下一部分概率为 <math>p</math> 的节点。存在一个'''<font color="#FF8000">临界渗透阈值 Critical Percolation Threshold </font>'''<math>p_c=\tfrac{1}{\langle k\rangle}</math>，当低于这个临界渗透阈值，网络变得支离破碎，而高于临界渗透阈值 <math>p_c</math> 的网络则存在一个巨大的'''<font color="#FF800">连接元件 Connected Component </font>'''(图论)。

<ref>{{cite book |title= Complex Networks: Structure, Robustness and Function |authors= Reuven Cohen and [[Shlomo Havlin]] |year= 2010 |url= http://havlin.biu.ac.il/Shlomo%20Havlin%20books_com_net.php |publisher= Cambridge University Press}}</ref><ref name ="On Random Graphs" />

<ref>{{cite book |title= Complex Networks: Structure, Robustness and Function |authors= Reuven Cohen and [[Shlomo Havlin]] |year= 2010 |url= http://havlin.biu.ac.il/Shlomo%20Havlin%20books_com_net.php |publisher= Cambridge University Press}}</ref><ref name ="On Random Graphs" />

If edges, <math>M</math> in a random graph, <math>G_M</math> is large enough to ensure that almost every <math>G_M</math> has minimum degree at least 1, then almost every <math>G_M</math> is connected and, if <math>n</math> is even, almost every <math>G_M</math> has a perfect matching. In particular, the moment the last isolated vertex vanishes in almost every random graph, the graph becomes connected.

If edges, <math>M</math> in a random graph, <math>G_M</math> is large enough to ensure that almost every <math>G_M</math> has minimum degree at least 1, then almost every <math>G_M</math> is connected and, if <math>n</math> is even, almost every <math>G_M</math> has a perfect matching. In particular, the moment the last isolated vertex vanishes in almost every random graph, the graph becomes connected.

如果随机图中的边 <math>M</math>，<math>G_M</math> 足够大以确保几乎每个 <math>G_M</math> 的最小阶数至少为1，那么几乎每个 <math>G</math> 是连通的，如果 <math>n</math> 是偶数，则几乎每个 <math>G_M</math> 都有一个'''<font color="#FF8000">完美匹配 Perfect Matching </font>'''。特别是，在几乎每个随机图中，最后一个孤立点消失的那一刻，图会变连通。

如果随机图中的边 <math>M</math>，<math>G_M</math> 大到足以确保几乎每个 <math>G_M</math> 的最小阶数至少为1，那么几乎每个 <math>G</math> 是连通的，如果 <math>n</math> 是偶数，则几乎每个 <math>G_M</math> 都有一个'''<font color="#FF8000">完美匹配 Perfect Matching </font>'''。特别是，在几乎每个随机图中，最后一个孤立点消失的那一刻，图会变连通。