Náhodný graf
Z Wikipedie, otevřené encyklopedie
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 nejstudověnější, se hrany vyskytují s pravděpodobností p. Podobný model G(n,M) existuje přesně M hran.