Náhodný graf

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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í.