Zufallsgraph

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:
- Das Gilbert-Modell (benannt nach Edgar Gilbert):[1]
mit einer natürlichen Zahl
, der Zahl der Knoten, 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.
- Das Erdős-Rényi-Modell (benannt nach Paul Erdős und
Alfréd Rényi):[2]
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.
- Auf einer abzählbaren Knotenmenge kann jede Kante unabhängig und mit Wahrscheinlichkeit
gewählt werden – durch diese Konstruktion entsteht fast sicher der Rado-Graph.
Fragestellungen
Wichtige Fragestellungen bei zufälligen Graphen sind:
- Gegeben eine Eigenschaft
, 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
Durch Anwendung der probabilistischen Methode auf sein Zufallsgraphenmodell
bewies Paul Erdős den Satz: Für jede natürliche Zahl
gibt es einen Graphen, bei dem sowohl Taillenweite
(Länge des kürzesten Kreises) als auch Chromatische Zahl größer
Im selben Zufallsgraphenmodell konnte gezeigt werden, dass Isomorphie zu einem beliebigen Graphen für fast alle Graphen in linearer Zeit entscheidbar ist.[4]
Literatur
- Douglas B. West: Introduction to Graph Theory. Prentice Hall, Upper Saddle River, N.J. 1996, ISBN 0-13-227828-6.
Einzelnachweise
- ↑ E. N. Gilbert: Random graphs, Annals of Mathematical Statistics, Band 30, 1959, S. 1141–1144
- ↑ P. Erdős, A. Rényi: On Random Graphs I, Publ. Math. Debrecen 6, 1959, S. 290–297
- ↑ Reinhard Diestel, Graphentheorie, Berlin, Heidelberg, New York: Springer, 3. Auflage 2006, S. 256ff.
- ↑ 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



© biancahoegel.de
Datum der letzten Änderung: Jena, den: 23.03. 2024