在圖論 中，ER隨機圖 （Erdős–Rényi random graph） 是一種網絡，以概率p連接N個節點中的每一對節點。ER隨機圖以埃爾德什·帕爾 和阿爾弗雷德·雷尼 [ 1] [ 2] [ 3]
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 ) 總共有
(
N
M
)
{\displaystyle {\tbinom {N}{M}}}
1
/
(
N
M
)
{\displaystyle 1/{\tbinom {N}{M}}}
[ 4]
在G (n , p )模型中，通過隨機連接n 個獨立節點構造一個圖，每條邊出現的概率是p ，且不同邊存在與否互相獨立。對於具有n 個頂點和M 條邊的圖，其出現的概率是
p
M
(
1
−
p
)
(
n
2
)
−
M
{\displaystyle 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 )的邊數期望 值為
(
n
2
)
p
{\displaystyle {\tbinom {n}{2}}p}
大數定理 ，幾乎所有G (n , p )模型中的圖的邊數都會有
(
n
2
)
p
{\displaystyle {\tbinom {n}{2}}p}
pn 2 → ∞，並且
M
=
(
n
2
)
p
{\displaystyle M={\tbinom {n}{2}}p}
n 的增大，G (n ,p )的變化行為應該與G (n , M )類似。
在pn 2 → ∞假設的基礎上，我們考慮一個圖的單調性質P （這意味着，若A 是B 的子圖，並且A 擁有性質P ,那麼B 也將擁有性質P ）；那麼「P 對於幾乎所有G (n , p )成立」等價於「P 對於幾乎所有G (n , M )成立」。但對於非單調的性質P ，表述的等價性不一定成立。
事實上，G (n , p )模型是當今最常用的模型，部分原因是邊存在的獨立性簡化了許多分析。
使用上面的符號，G (n , p )中的圖邊數的平均值是
(
n
2
)
p
{\displaystyle {\tbinom {n}{2}}p}
度 服從於二項分佈 ：[ 5]
P
(
deg
(
v
)
=
k
)
=
(
n
−
1
k
)
p
k
(
1
−
p
)
n
−
1
−
k
,
{\displaystyle P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},}
其中n 是圖中頂點的數目。因為
P
(
deg
(
v
)
=
k
)
→
(
n
p
)
k
e
−
n
p
k
!
as
n
→
∞
and
n
p
=
constant
,
{\displaystyle 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[ 6] 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
<
(
1
−
ε
)
ln
n
n
{\displaystyle p<{\tfrac {(1-\varepsilon )\ln n}{n}}}
G (n , p )中的一個圖幾乎必有孤立點，因此這個圖是不連通的。
若
p
>
(
1
+
ε
)
ln
n
n
{\displaystyle p>{\tfrac {(1+\varepsilon )\ln n}{n}}}
G (n , p )幾乎一定連通。 因此
ln
n
n
{\displaystyle {\tfrac {\ln n}{n}}}
隨着n 趨於無窮大，G (n ,p )可以幾乎精確地描述圖的其他屬性。
Erdős, P.; Rényi, A. On Random Graphs. I (PDF) . Publicationes Mathematicae. 1959, 6 : 290–297. （原始內容存檔 (PDF) 於2020-08-07）. Béla Bollobás , Random Graphs , 1985, Academic Press Inc., London Ltd.
Erdős, P.; Rényi, A. On the evolution of random graphs [論隨機圖的演化] (PDF) . Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publications of the Mathematical Institute of the Hungarian Academy of Sciences]. 1960, 5 : 17–61 [2020-12-19 ] . （原始內容存檔 (PDF) 於2021-02-01） （英語） . The probability p used here refers there to
N
(
n
)
=
(
n
2
)
p
{\displaystyle N(n)={\tbinom {n}{2}}p}
