Zufallsgraph
aus Wikipedia, der freien Enzyklopädie
Ein Zufallsgraph bezeichnet einen Graphen, bei dem die Kanten zufällig erzeugt werden. Zwei häufig eingesetzte Modelle zufälliger Graphen sind:
- G(n,p) mit einer natürlichen Zahl
und einer Wahrscheinlichkeit 
bezeichnet die Klasse aller Graphen, bei denen für jedes Tupel (v1,v2) von Knoten mit der Wahrscheinlichkeit p bestimmt wird, ob sie durch eine Kante verbunden werden, und das unabhängig von den anderen Kanten. Man untersucht dann häufig, mit welcher Wahrscheinlichkeit die erzeugten Graphen eine bestimmte Eigenschaft haben, z. B. ob sie zusammenhängend sind. Eine weitere Möglichkeit ist es, p = p(n) in Abhängigkeit von n vorzugeben und dann das Verhalten bei wachsendem n zu untersuchen.
- Die Knoten V des Graphen G werden in der Ebene gemäß einer vorgegebenen Wahrscheinlichkeitsverteilung f verteilt. Wenn zwei Knoten v1,v2 einen Abstand kleiner als eine vorgegebene Grenze d haben, werden sie durch eine Kante verbunden.
