ER隨機圖

佇圖論內底，ER 隨機圖（Erdős–Rényi random graph）伊是一个網路，以概率 p 連接 N 一个節點內底每一對點。ER 隨機圖以埃爾德啥・帕爾佮阿爾鴻雷德・雷尼啊（Alfréd Rényi）的名號名。𪜶佇一九五九年發明了這種模型。仝年，Edward Gilbert 獨立提出另外一个模型。

佇咧 Erdős-Rényi 模型中，佇咧頂點集數目相仝的時陣，有固定的邊數的所有的圖樣有仝款等的概率出現。佇吉爾伯特（Gilbert）引入來的模型內底，遐攏有固定的出現概率，而且獨立於其他邊仔的概率。這寡模型會當用於概率方法內底，以證明滿足各種屬性的圖存在，抑是講對差不多所有圖有屬性的含義提供嚴格的定義。

定義

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

佇咧 _ G _ ( _ n _ , _ M _ ) 模型中，確定的圖對有來 _ n _ 阮這个頂點佮 _ M _ 條邊的所有圖集合中等概率隨機選擇。比如講，佇咧 _ G _ ( 三 , 二 ) 模型中，具有三个頂點佮兩條邊的彼个圖攏總就有三種，𪜶每一个攏以三分之一的概率出現佇 _ G _ ( 三 , 二 ) 中。做零 ≤ _ M _ ≤ _ N _ , _ G _ ( _ n _ , _ M _ ) 攏總有 $ { \ tbinom { N } { M } } $ 種可能的確定圖，逐種圖出來的概率是 $ 一 / { \ tbinom { N } { M } } $。
佇咧 _ G _ ( _ n _ , _ p _ ) 模型中，通過隨機接 _ n _ 個獨立節點構造一個圖，逐條邊出現的概率是 _ p _，閣無仝邊存在佮無互相獨立。對於具有 _ n _ 阮這个頂點佮 _ M _ 條邊的圖，其實出現的概率是 $ p ^ { M } ( 一-p ) ^ { { n \ choose 二 }-M } $。由此，_ p _ 愈大，_ G _ 中出現較濟的圖的概率會夯懸。

通常佇頂點數 _ n _ 因為無窮大時研究隨機圖的性質佮變化行為。就算講 _ p _ 抑是 _ M _ 會當做固定值，但是𪜶嘛是會當依賴 _ n _ 的取值。比如講，_ G _ ( _ n _ , 二 ln ( _ n _ ) / _ n _ ) 咱中的每一个圖差不多攏是連通圖；隨著 _ n _ 因為無窮大，_ G _ ( _ n _ , 二 ln ( _ n _ ) / _ n _ ) 差不多每一圖攏予人連接。

兩種模型的較

_ G _ ( _ n _ , _ p _ ) 的邊數向望價值為 $ { \ tbinom { n } { 二 } } p $，就按呢根據大數定理，差不多所有 _ G _ ( _ n _ , _ p _ ) 模型中的圖樣攏會有 $ { \ tbinom { n } { 二 } } p $ 個。所以，一个粗略的想法是講，若是 _ pn _ 二 → ∞，並且 $ M={ \ tbinom { n } { 二 } } 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 } { 二 } } p $。任何特定頂點的度服裝二項分布：

$ P ( \ deg ( v )=k )={ n 影一 \ choose k } p ^ { k } ( 一-p ) ^ { n 影一-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 _。

佇一九六Ｏ年的論文中，Erdős 和 Rényi 對無仝款的 _ p _ 精準的所在是咧講 _ G _ ( _ n _ , _ p _ ) 變化行為。遮的結果包括：

若是 _ np _ < 一，遐爾 _ G _ ( _ n _ , _ p _ ) 中的圖差不多一定無大細大於 O ( log ( _ n _ ) ) 的連通分支。
若是 _ np _=一，遐爾 _ G _ ( _ n _ , _ p _ ) 中的圖差不多一定存在一个上大的連通分支，其大細約仔為 _ n _ 三分之二。
若是 _ np _ → _ c _ > 一，_ c _ 為常數，遐爾 _ G _ ( _ n _ , _ p _ ) 中的一个圖強欲是必有唯一的包含結點有限部份的巨型連通分支，其他連通分支袂包括超過 O ( log ( _ n _ ) ) 頂點。
若是 $ p < { \ tfrac { ( 一-\ varepsilon ) \ ln n } { n } } $，遐爾 _ G _ ( _ n _ , _ p _ ) 中的一个圖強欲著孤立點，所以這圖是無連通的。
若是 $ p > { \ tfrac { ( 一 + \ varepsilon ) \ ln n } { n } } $，遐爾 _ G _ ( _ n _ , _ p _ ) 差不多一定連通。

所以 $ { \ tfrac { \ ln n } { n } } $ 是一个鋒利允准。

隨著 _ n _ 因為無窮大，_ G _ ( _ n _ , _ p _ ) 會當強欲精確來講圖的其他的屬性。

滲流理論

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

參考文獻