檢視 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 隨機圖，這嘛是一種平均場論。

==參考文獻==

[[分類: 待校正]]