Zufallsgraph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Realisierung des Gilbert-Graphen

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

  • Gilbert-Graph: mit einer natürlichen Zahl und einer Wahrscheinlichkeit bezeichnet die Menge aller Graphen, bei denen für jedes geordnete Paar von Knoten, mit , mit der Wahrscheinlichkeit 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, in Abhängigkeit von vorzugeben und dann das Verhalten bei wachsendem zu untersuchen.
  • Erdős-Rényi-Graph: mit natürlichen Zahlen und bezeichnet die Menge aller Graphen mit exakt Knoten und Kanten.
  • Die Knoten des Graphen werden in der Ebene gemäß einer vorgegebenen Wahrscheinlichkeitsverteilung verteilt. Wenn zwei Knoten einen Abstand kleiner als eine vorgegebene Grenze haben, werden sie durch eine Kante verbunden.

Fragestellungen[Bearbeiten | Quelltext bearbeiten]

Wichtige Fragestellungen bei zufälligen Graphen sind:

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

Wichtige Ergebnisse[Bearbeiten | Quelltext bearbeiten]

Durch Anwendung der probabilistischen Methode auf sein Zufallsgraphenmodell bewies Paul Erdős den Satz von Erdős. [1]

Im selben Zufallsgraphenmodell konnte gezeigt werden, dass Isomorphie zu einem beliebigen Graphen für fast alle Graphen in linearer Zeit entscheidbar ist. [2]

Literatur[Bearbeiten | Quelltext bearbeiten]

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

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Diestel, Reinhard. Graphentheorie. Vol. 2. Berlin, Heidelberg, New York: Springer, 1996. S. 229.
  2. Babai, László, Paul Erdös, und Stanley M. Selkow. "Random graph isomorphism." Society for Industrial and Applied Mathematics Journal on Computing 9.3 (1980): 628-635. online