Zufallsgraph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Realisierung des Gilbert-Graphen G(20;\; 0{,}1)

Ein Zufallsgraph bezeichnet einen Graphen, bei dem die Kanten zufällig erzeugt werden. Häufig eingesetzte Modelle zufälliger Graphen sind:

  • Gilbert-Graph: G(n, p) mit einer natürlichen Zahl n \ge 1 und einer Wahrscheinlichkeit 0 \le p \le 1 bezeichnet die Menge aller Graphen, bei denen für jedes geordnete Paar (v_1, v_2) von Knoten, mit v_i\le n, 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.
  • Erdős-Rényi-Graph: G(n, m) mit natürlichen Zahlen n \ge 1 und m \ge 0 bezeichnet die Menge aller Graphen mit exakt n Knoten und m Kanten.
  • Die Knoten V des Graphen G werden in der Ebene gemäß einer vorgegebenen Wahrscheinlichkeitsverteilung f verteilt. Wenn zwei Knoten v_1, v_2 einen Abstand kleiner als eine vorgegebene Grenze d haben, werden sie durch eine Kante verbunden.

Fragestellungen[Bearbeiten]

Wichtige Fragestellungen bei zufälligen Graphen sind:

  • Gegeben eine Eigenschaft Q und teste, für welche p bzw. m und ab welcher Graphengröße n besitzen alle Graphen die Eigenschaft Q?
  • Gegeben eine Eigenschaft Q, geht die Wahrscheinlichkeit für Q gegen 1 oder 0 für n \rightarrow \infty? Man sagt dann auch, fast alle oder fast gar keine Graphen erfüllen die Eigenschaft Q.

Wichtige Ergebnisse[Bearbeiten]

Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Näheres ist eventuell auf der Diskussionsseite oder in der Versionsgeschichte angegeben. Bitte entferne zuletzt diese Warnmarkierung.

Einige NP-schwere Probleme lassen sich mit Hilfe zufälliger Graphen effizient beantworten. Beispielsweise kann Graph-Isomorphie für G(n,1/2) in O(n^2) getestet werden.

Literatur[Bearbeiten]

  • Douglas B. West: Introduction to Graph Theory. Prentice Hall, Upper Saddle River, N.J. 1996, ISBN 0-13-227828-6.