Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 092.15705
Autor: Erdös, Pál; Rényi, Alfréd
Title: On random graphs. I. (In English)
Source: Publ. Math., Debrecen 6, 290-297 (1959).
Review: Aus dem vollständigen Graph mit n Knotenpunkten und {n \choose 2} Kanten werden durch ein symmetrisches Zufallsexperiment genau [ 1/2 n log n+cn] Kanten ausgewählt (c ist eine beliebige reelle Zahl). Der so ausgewählte Graph \Gamma hat möglicherweise isolierte Punkte, die hier auch als Zusammenhangskomponenten von \Gamma zu betrachten sind. Es wird die Wahrscheinlichkeit, daß die größte Zusammenhangskomponente von \Gamma genau n-k Knotenpunkte hat (k = 0,1,...) bzw. daß \Gamma aus genau k+1 Zusammenhangskomponenten besteht, bzw. eine weitere derartige Wahrscheinlichkeit asymptotisch für n ––> oo bestimmt. Die Verff. erhalten in beiden Fällen den gleichen Grenzwert (k!)-1 (e-2c)k e-e^{-2c}.
Reviewer: G.Ringel
Classif.: * 05C80 Random graphs
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag