On random graphs. I. (English) Zbl 0092.15705

Erdős, Pál; Rényi, Alfréd

Publ. Math., Debrecen 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

MSC:

05C80

Random graphs (graph-theoretic aspects)

Keywords:

topology