×

zbMATH — the first resource for mathematics

On random graphs. I. (English) Zbl 0092.15705
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
PDF BibTeX XML Cite