ER隨機圖

  提示：此條目頁的主題不是ER模型。

在圖論中，ER隨機圖（Erdős–Rényi random graph）是一種網絡，以概率p連接N個節點中的每一對節點。ER隨機圖以埃爾德什·帕爾和阿爾弗雷德·雷尼（Alfréd Rényi）的名字命名。他們在1959年發明了這種模型。同年，Edward Gilbert獨立提出了另外一個模型。

p = 0.01

在Erdős-Rényi模型中，在頂點集數目相同時，具有固定邊數的所有圖均具有同等的概率出現。在吉爾伯特（Gilbert）引入的模型中，每個邊都有固定的出現概率，並且獨立於其他邊的概率。這些模型可用於概率方法中，以證明滿足各種屬性的圖的存在，或者對幾乎所有圖具有屬性的含義提供嚴格的定義。

定義

ER隨機圖主要有兩種高度相關的模型。

• 在G(n, M)模型中，確定的圖從具有n個頂點和M條邊的所有圖集合中等概率隨機選擇。例如，在G(3, 2)模型中，具有三個頂點和兩條邊的圖總共有3種，它們每一個都以1/3的概率出現在G(3, 2)中。當0 ≤ M ≤ N, G(n,M) 總共有${\tbinom {N}{M}}$種可能的確定圖，每種圖出現的概率是$1/{\tbinom {N}{M}}$。
• 在G(n, p)模型中，通過隨機連接n個獨立節點構造一個圖，每條邊出現的概率是p，且不同邊存在與否互相獨立。對於具有n個頂點和M條邊的圖，其出現的概率是$p^{M}(1-p)^{{n \choose 2}-M}$。由此，p越大，G中出現邊較多的圖的概率會上升。

通常在頂點數n趨向於無窮大時研究隨機圖的性質和變化行為。儘管p或M可以為固定值，但它們也可以依賴n的取值。例如，G(n, 2ln(n)/n)中的每個圖幾乎都是連通圖；隨着n趨於無窮大，G(n, 2ln(n)/n)中幾乎每個圖都被連接。

兩種模型的比較

G(n, p)的邊數期望值為${\tbinom {n}{2}}p$，因此根據大數定理，幾乎所有G(n, p)模型中的圖的邊數都會有${\tbinom {n}{2}}p$個。因此，一個粗略的想法是，如果pn² → ∞，並且$M={\tbinom {n}{2}}p$，那麼隨着n的增大，G(n,p)的變化行為應該與G(n, M)類似。

在pn² → ∞假設的基礎上，我們考慮一個圖的單調性質P（這意味着，若A是B的子圖，並且A擁有性質P,那麼B也將擁有性質P）；那麼「P對於幾乎所有G(n, p)成立」等價於「P對於幾乎所有G(n, M)成立」。但對於非單調的性質P，表述的等價性不一定成立。

事實上，G(n, p)模型是當今最常用的模型，部分原因是邊存在的獨立性簡化了許多分析。

G(n,p)的性質

使用上面的符號，G(n, p)中的圖邊數的平均值是${\tbinom {n}{2}}p$。任何特定頂點的度服從於二項分布：

$P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},$

其中n是圖中頂點的數目。因為

$P(\deg(v)=k)\to {\frac {(np)^{k}\mathrm {e} ^{-np}}{k!}}\quad {\text{ as }}n\to \infty {\text{ and }}np={\text{constant}},$

此分布為泊松分布對於較大的n和常數np。

在1960年的論文中，Erdős和Rényi對於不同的p精準地描述了G(n, p)變化行為。這些結果包括：

• 若np < 1，那麼G(n, p)中的圖幾乎一定沒有大小大於O(log(n))的連通分支。
• 若np = 1，那麼G(n, p)中的圖幾乎一定存在一個最大的連通分支，其大小約為n^2/3。
• 若np → c > 1，c為常數，那麼G(n, p)中的一個圖幾乎必有唯一的包含結點有限部分的巨型連通分支，其他連通分支不會包含超過O(log(n))個頂點。
• 若$p<{\tfrac {(1-\varepsilon )\ln n}{n}}$，那麼G(n, p)中的一個圖幾乎必有孤立點，因此這個圖是不連通的。
• 若$p>{\tfrac {(1+\varepsilon )\ln n}{n}}$，那麼G(n, p)幾乎一定連通。

因此${\tfrac {\ln n}{n}}$是一個鋒利閾值。

隨着n趨於無窮大，G(n,p)可以幾乎精確地描述圖的其他屬性。

滲流理論

完全圖上的滲流理論是ER隨機圖，這也是一種平均場論。