Náhodný graf

Náhodný graf je graf, který vznikl náhodným procesem. Náhodný může být jak počet uzlů nebo hran, tak rozmístění hran mezi uzly. Poprvé jej definovali Paul Erdős a Alfréd Rényi ve společné práci „On Random Graphs“ v roce 1959. V jejich modelu $G(n,p)$ s $n$ uzly, který je nejstudovanější, se hrany vyskytují nezávisle s pravděpodobností $p$. V příbuzném modelu $G(n,M)$ existuje přesně M hran, přičemž každý z možných grafů se vyskytuje se stejnou pravděpodobností.