基本介紹
- 中文名：隨機圖
- 外文名：Random graphs
- 學科：數學、統計學
- 提出者：保羅·埃爾德什和阿爾弗雷德·雷尼
概念,定義與模型,性質,隨機樹,
概念
隨機圖(random graph)是一類重要的圖。它是伴隨有不確定性的圖.按某種隨機方式刪去一個圖G的某些節點或邊而保留下來的圖稱為隨機子圖，又稱隨機圖。G稱為隨機圖的原始圖隨機圖的性質與原始圖及隨機刪除部分節點或邊的方式有關。隨機刪除方式包括只刪點、只刪邊和既刪點又刪邊三種。研究較多的原始圖有完全圖和晶形圖。若按某種刪除方式得到的一類隨機圖看成是機率空間，則有關的圖的不變數或參數就是該空間的隨機變數。從任一節點出發，按不過重複節點的原則，可隨機走遍所有節點的圖稱為隨機哈密頓圖。從任一節點出發，按不過重複邊的原則，可隨機走遍所有邊而回到出發點的圖稱為隨機可跡圖。若原始圖為完全圖，且按隨機刪邊方式得到的任一隨機圖邊數固定，則稱這樣的隨機圖為定邊數隨機圖。若原始圖為完全圖，每條邊刪除的機率相同且各邊的刪除相互獨立，則這種隨機圖稱為定邊密度隨機圖。
定義與模型
隨機圖的“隨機”二字型現在邊的分布上。一個隨機圖實際上是將給定的頂點之間隨機地連上邊。假設將一些紐扣散落在地上，並且不斷隨機地將兩個紐扣之間繫上一條線，這樣就得到一個隨機圖的例子。邊的產生可以依賴於不同的隨機方式，這樣就產生了不同的隨機圖模型。一個典型的模型是埃爾德什和雷尼共同研究的ER模型。ER模型是指在給定n個頂點後，規定每兩個頂點之間都有p的機率連起來（0⩽p⩽1），而且這些判定之間兩兩無關。這樣得到的隨機圖一般記作Gnp或ERn(p)。
另一種隨機圖模型叫做內積模型。內積模型的機制是對每一個頂點指定一個實係數的向量，而兩個頂點之間是否連線的機率則是它們的向量的內積的函式。
一般來說，可以定義任意兩個頂點之間相連的機率，這個機率也被稱為邊機率。定義更廣泛的隨機圖模型的方法是定義所謂的網路機率矩陣。這個矩陣的係數就是邊機率，因此詳細刻畫了隨機圖的模型。
隨機規則圖是隨機圖中特殊的一類，它的性質可能會與一般的隨機圖不同。
性質
隨著邊機率的不同，隨機圖可能會呈現不同的屬性。對於最典型的ER模型，埃爾德什與雷尼研究了當頂點數目 n 趨向於正無窮大時，ER隨機圖的性質與機率p 之間的關係。他們發現，當 p 的值越過某些門檻時，ER隨機圖的性質會發生突然的改變。ER隨機圖的許多性質都是突然湧現的，比如說，當 p 的值小於某個特殊值之前，隨機圖具有某個性質的可能性等於0，但當 p 的值大於這個特殊值以後，隨機圖具有這個性質的可能性會突然變成1。
舉例來說，當機率 p 大於某個臨界值 pc(n) 後，生成的隨機圖幾乎必然是連通的（機率等於1）。也就是說，對於散落在地上的 n 個紐扣，如果你以這樣的機率 p 將兩個紐扣之間繫上線，那么你拿起一顆紐扣時就幾乎能帶起所有的紐扣了。
