Erdős, Pál; Rényi, Alfréd On random graphs. I. (English) Zbl 0092.15705 Publ. Math. Debr. 6, 290-297 (1959). Aus dem vollständigen Graph mit \(n\) Knotenpunkten und \({n \choose 2}\) Kanten werden durch ein symmetrisches Zufallsexperiment genau \([{1 \over 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 \to \infty\) bestimmt. Die Verff. erhalten in beiden Fällen den gleichen Grenzwert \((k!)^{-1} (e^{-2c})^k e^{-e^{-2c}}\). Reviewer: G.Ringel Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 11 ReviewsCited in 625 Documents MSC: 05C80 Random graphs (graph-theoretic aspects) Keywords:topology PDF BibTeX XML Cite \textit{P. Erdős} and \textit{A. Rényi}, Publ. Math. Debr. 6, 290--297 (1959; Zbl 0092.15705) OpenURL