Erdos-Reni Modell

Beschreibung

Das Erdos-Reni-Modell beschreibt eines von zwei ähnlichen Methoden, um zufällige Graphen zu generieren. Die meisten Definitionen geben einen Graph mit $n$ Knoten an, studiert wird aber üblicherweise der Grenzwert.

Definition $G(n,M)$-Modell

Ein zufälliger Graph wird uniform aus der Menge aller Graphen mit $n$ Knoten und $M$ Kanten ausgesucht. Die Kanten sind markiert, d.h. die Permutation von Knoten resultiert in einen anderen Graph. Es lässt sich leicht zeigen, dass der Raum der Graphen die Größe $2^{n(n-1)}$ besitzt.

$G(n,p)$-Modell

Ein Graph mit $n$ Knoten wird erzeugt, indem jeder Kante eine Erscheinungswahrscheinlichkeit $p$ gegeben wird.

Eigenschaften

Eigenschaft