隨機圖
在數學中，隨機圖是指圖形上概率分佈的一般術語。隨機圖可以僅通過概率分佈或生成它們的隨機過程來描述。隨機圖的理論在於圖理論與概率理論之間的相交。從數學角度來看，隨機圖用於回答有關典型圖的屬性的問題。它的實際應用都可以在需要對複雜網絡進行建模的所有領域中找到 - 因此，許多隨機圖模型都是已知的，反映了不同領域遇到的各種複雜網絡的類型。在數學上下文中，隨機圖幾乎完全指ERDőS -Rényi隨機圖模型。在其他情況下，任何圖形模型都可以稱為隨機圖。
楷模
通過從一組n個孤立的頂點開始，並隨機添加它們之間的連續邊緣，從而獲得隨機圖。該研究在該領域的目的是確定圖表的特定特性可能出現在哪個階段。不同的隨機圖模型在圖上產生不同的概率分佈。最常見的研究是埃德加·吉爾伯特（ Edgar Gilbert 
密切相關的模型， ERDőS -Rényi模型表示G （ n ， m ），將同等的概率分配給所有具有M邊的圖形。在0≤m≤n的情況下， g （ n ， m ）具有
相反，如果我們從無限的頂點開始，然後再次讓每個可能的邊緣以0 < p <1的概率獨立發生，那麼我們得到一個稱為無限隨機圖的對象G。除了p是0或1的微不足道的情況外，此類g幾乎肯定具有以下屬性：
給定任何n + m元素
， V中有一個頂點C ，該頂點與每個頂點
並且不毗鄰任何
。
事實證明，如果頂點集是可計數的，則具有同構，只有單個圖形，即rado圖。因此，任何無數的無限隨機圖幾乎都是Rado圖，因此，該圖有時被稱為隨機圖。但是，對於不可數的圖，類似結果並非如此，其中有許多（非同形）圖滿足上述屬性。
另一個概括吉爾伯特（Gilbert）隨機圖模型的模型是隨機點產品模型。隨機點產物圖與每個頂點一個真實向量相關聯。任何頂點u和v之間的邊緣紫外線的概率是其各自向量的點產物u • v的一定函數。
網絡概率矩陣通過邊緣概率隨機圖模型，該圖表示概率
對於M pn ，其中n是可能的最大邊數，兩個最廣泛的模型G （ N ， M ）和G （ N ， P ）幾乎可以互換。
隨機常規圖構成一種特殊情況，其屬性通常與隨機圖不同。
一旦我們擁有一個隨機圖的模型，圖形上的每個函數都將成為一個隨機變量。該模型的研究是確定是否可能發生財產的可能性，或者至少估計可能發生的概率。
術語
隨機圖上下文中“幾乎每個”一詞是指空間和概率的序列，因此誤差概率往往為零。
特性
隨機圖的理論研究隨機圖的典型特性，該圖具有從特定分佈中繪製的圖形概率高的典型特性。例如，我們可能會要求給定的值
滲透與圖形的魯棒性有關（也稱為網絡）。給定一個隨機圖
局部滲透是指刪除鄰居的節點，下一個最近的鄰居等，直到一小部分
隨機圖被廣泛用於概率方法中，其中人們試圖證明具有某些屬性的圖。隨機圖上的屬性的存在通常可以通過szemerédi規律性引理表示該屬性幾乎在所有圖上的存在。
在隨機的常規圖中， 
圖的度序列
如果邊緣， 
均勻數量的頂點上的幾乎每個圖形過程都將最低度提高到1或隨機圖，略高於
對於一些常數
隨機圖的屬性可能會在圖形轉換下改變或保持不變。例如， Mashaghi A.等。係數。
染色
給定一個隨機圖N ，帶有頂點v （ g ）= {1，...， n }，通過顏色數的貪婪算法，可以用顏色1，2，... （頂點1彩色1，頂點2是彩色1，如果它不與頂點1相鄰，否則顏色為2等）。到目前為止，給出許多Q顏色的隨機圖的正確色素的數量仍然未知。具有參數n的隨機圖的色度多項式的零和邊緣M或連接概率P的縮放比例已使用基於符號模式匹配的算法進行了經驗研究。
隨機樹
隨機樹是由隨機過程形成的樹或樹木。在大量的n和大小m （ n ）的隨機圖中， k級的樹成分數的分佈是漸近的泊松。隨機樹的類型包括統一的樹木，隨機最小的跨越樹，隨機二進制樹， Treap ，快速探索隨機樹，布朗樹和隨機森林。
條件隨機圖
考慮在概率空間上定義的給定隨機圖模型
特殊情況是條件均勻的隨機圖，其中
歷史
最早使用隨機圖模型是Helen Hall Jennings和Jacob Moreno於1938年在研究中考慮了“機會社會圖”（有指導性的ERDőS-Rényi模型），以比較比較其網絡數據中回報鏈接的分數與隨機模型的分數。另一種用途，名稱為“隨機淨”，是Ray Solomonoff和Anatol Rapoport在1951年使用的，使用了有向圖的模型，該圖形具有固定的外觀和隨機選擇的附件。
PaulErdős和AlfrédRényi在其1959年的“隨機圖上”的“隨機圖”中首次定義了隨機圖的Erdős–Rényi模型，並由Gilbert獨立於他的論文“隨機圖”。