在數學中，隨機圖是指由隨機過程產生的圖。隨機圖的理論處于圖論和概率論的交叉地帶，主要研究各種經典隨機圖的性質。第一批關于隨機圖的結果是保羅·埃爾德什和阿爾弗雷德·雷尼在1959年至1966年的一系列論文中提出的。
概念
隨機圖(random graph)是一類重要的圖。它是伴隨有不確定性的圖。按某種隨機方式刪去一個圖G的某些節點或邊而保留下來的圖稱為隨機子圖，又稱隨機圖。G稱為隨機圖的原始圖隨機圖的性質與原始圖及隨機刪除部分節點或邊的方式有關。隨機刪除方式包括只刪點、只刪邊和既刪點又刪邊三種。研究較多的原始圖有完全圖和晶形圖。若按某種刪除方式得到的一類隨機圖看成是概率空間，則有關的圖的不變量或參數就是該空間的隨機變量。從任一節點出發，按不過重復節點的原則，可隨機走遍所有節點的圖稱為隨機哈密頓圖。從任一節點出發，按不過重復邊的原則，可隨機走遍所有邊而回到出發點的圖稱為隨機可跡圖。若原始圖為完全圖，且按隨機刪邊方式得到的任一隨機圖邊數固定，則稱這樣的隨機圖為定邊數隨機圖。若原始圖為完全圖，每條邊刪除的概率相同且各邊的刪除相互獨立，則這種隨機圖稱為定邊密度隨機圖。
定義與模型
隨機圖的“隨機”二字體現在邊的分布上。一個隨機圖實際上是將給定的頂點之間隨機地連上邊。假設將一些紐扣散落在地上，并且不斷隨機地將兩個紐扣之間系上一條線，這樣就得到一個隨機圖的例子。邊的產生可以依賴于不同的隨機方式，這樣就產生了不同的隨機圖模型。一個典型的模型是保羅·埃爾德什和雷尼共同研究的ER模型。ER模型是指在給定n個頂點后，規定每兩個頂點之間都有p的概率連起來，而且這些判定之間兩兩無關。這樣得到的隨機圖一般記作Gnp或ERn(p)。
另一種隨機圖模型叫做內積模型。內積模型的機制是對每一個頂點指定一個實系數的向量，而兩個頂點之間是否連接的概率則是它們的向量的內積的函數。
一般來說，可以定義任意兩個頂點之間相連的概率，這個概率也被稱為邊概率。定義更廣泛的隨機圖模型的方法是定義所謂的網絡概率矩陣。這個矩陣的系數就是邊概率，因此詳細刻畫了隨機圖的模型。
隨機規則圖是隨機圖中特殊的一類，它的性質可能會與一般的隨機圖不同。
性質
隨著邊概率的不同，隨機圖可能會呈現不同的屬性。對于最典型的ER模型，保羅·埃爾德什與雷尼研究了當頂點數目 n 趨向于正無窮大時，ER隨機圖的性質與概率 p 之間的關系。他們發現，當 p 的值越過某些門檻時，ER隨機圖的性質會發生突然的改變。ER隨機圖的許多性質都是突然涌現的，比如說，當 p 的值小于某個特殊值之前，隨機圖具有某個性質的可能性等于0，但當 p 的值大于這個特殊值以后，隨機圖具有這個性質的可能性會突然變成1 ? 。
舉例來說，當概率 p 大于某個臨界值 p( n) 后，生成的隨機圖幾乎必然是連通的（概率等于1）。也就是說，對于散落在地上的 n 個紐扣，如果你以這樣的概率 p 將兩個紐扣之間系上線，那么你拿起一顆紐扣時就幾乎能帶起所有的紐扣了。
隨機樹
隨機樹是隨機圖的一類。如同隨機圖一樣，隨機樹是一個經由隨機過程建立的樹。隨機樹的一種生成方法是利用隨機置換。首先生成一個階隨機置換函數，將 個可能連起來的邊標上 1 至 的序號。然后按照從小到大的序號排列為原本沒有邊的圖一一添加邊。添加第 k條邊時，如果發現添加后會導致圖中出現一個圈，那么就放棄添加這條邊，而開始添加第條邊。最后得到的就是一個隨機樹。
參考資料 >