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 s uzly, který je nejstudovanější, se hrany vyskytují nezávisle s pravděpodobností . V příbuzném modelu existuje přesně M hran, přičemž každý z možných grafů se vyskytuje se stejnou pravděpodobností.