Zufallsgraph

Ein Zufallsgraph bezeichnet e​inen Graphen, b​ei dem d​ie Kanten zufällig erzeugt werden. Häufig eingesetzte Modelle zufälliger Graphen sind:

• Gilbert-Graph (benannt nach Edgar Gilbert):[1] ${\displaystyle G(n,p)}$ mit einer natürlichen Zahl ${\displaystyle n\geq 1}$, der Zahl der Knoten, und einer Wahrscheinlichkeit ${\displaystyle 0\leq p\leq 1}$ bezeichnet die Menge aller Graphen, bei denen für jedes geordnete Paar ${\displaystyle (v_{1},v_{2})}$ von Knoten, mit ${\displaystyle v_{i}\leq n}$, mit der Wahrscheinlichkeit ${\displaystyle 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, ${\displaystyle p=p(n)}$ in Abhängigkeit von ${\displaystyle n}$ vorzugeben und dann das Verhalten bei wachsendem ${\displaystyle n}$ zu untersuchen.

• Erdős-Rényi-Graph (benannt nach Paul Erdős und Alfréd Rényi):[2] ${\displaystyle G(n,m)}$ mit natürlichen Zahlen ${\displaystyle n\geq 1}$ und ${\displaystyle m\geq 0}$ bezeichnet die Menge aller Graphen mit exakt ${\displaystyle n}$ Knoten und ${\displaystyle m}$ Kanten.

• Die Knoten ${\displaystyle V}$ des Graphen ${\displaystyle G}$ werden in der Ebene gemäß einer vorgegebenen Wahrscheinlichkeitsverteilung ${\displaystyle f}$ verteilt. Wenn zwei Knoten ${\displaystyle v_{1},v_{2}}$ einen Abstand kleiner als eine vorgegebene Grenze ${\displaystyle d}$ haben, werden sie durch eine Kante verbunden.

Realisierung des Gilbert-Graphen ${\displaystyle G(20;\;0{,}1)}$