imported>Icy2008 am 20. April 2026 um 17:46 Uhr

2026-04-20T17:46:20Z

Neue Seite

__KEIN_INHALTSVERZEICHNIS__
[[Datei:Random20-0.1-instance1.png|mini|[[Stochastischer Prozess#Pfade|Realisierung]] des Gilbert-Graphen <math>G(20;\; 0{,}1)</math>]]
Ein '''Zufallsgraph''' bezeichnet einen [[Graph (Graphentheorie)|''Graphen'']], bei dem die Kanten zufällig erzeugt werden. Häufig eingesetzte Modelle zufälliger Graphen sind:

* Das ''Gilbert-Modell'' (benannt nach [[Edgar Gilbert]]):<ref>E. N. Gilbert: ''Random graphs'', Annals of Mathematical Statistics, Band 30, 1959, S. 1141–1144</ref> <math>G(n, p)</math> mit einer natürlichen Zahl <math>n \ge 1</math>, der Zahl der Knoten, und einer Wahrscheinlichkeit <math>0 \le p \le 1</math> bezeichnet die Menge aller Graphen, bei denen für jedes [[Geordnetes Paar|geordnete Paar]] <math>(v_1, v_2)</math> von Knoten, mit <math>v_i\le n</math>, mit der Wahrscheinlichkeit <math>p</math> 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, <math>p = p(n)</math> in Abhängigkeit von <math>n</math> vorzugeben und dann das Verhalten bei wachsendem <math>n</math> zu untersuchen.

* Das ''Erdős-Rényi-Modell'' (benannt nach [[Paul Erdős]] und [[Alfréd Rényi]]):<ref>P. Erdős, A. Rényi: ''On Random Graphs I'', Publ. Math. Debrecen 6, 1959, S. 290–297</ref> <math>G(n, m)</math> mit natürlichen Zahlen <math>n \ge 1</math> und <math>m \ge 0</math> bezeichnet die Menge aller Graphen mit exakt <math>n</math> Knoten und <math>m</math> Kanten.

* Die Knoten <math>V</math> des Graphen <math>G</math> werden in der Ebene gemäß einer vorgegebenen Wahrscheinlichkeitsverteilung <math>f</math> verteilt. Wenn zwei Knoten <math>v_1, v_2</math> einen Abstand kleiner als eine vorgegebene Grenze <math>d</math> haben, werden sie durch eine Kante verbunden.

* Auf einer abzählbaren Knotenmenge kann jede Kante unabhängig und mit Wahrscheinlichkeit <math>\tfrac{1}{2}</math> gewählt werden – durch diese Konstruktion entsteht fast sicher der [[Rado-Graph]].

== Fragestellungen ==
Wichtige Fragestellungen bei zufälligen Graphen sind:

* Gegeben eine Eigenschaft <math>Q</math>, für welche <math>p</math> bzw. <math>m</math> und ab welcher Graphengröße <math>n</math> besitzen alle Graphen die Eigenschaft <math>Q</math>?

* Gegeben eine Eigenschaft <math>Q</math>, geht die Wahrscheinlichkeit für <math>Q</math> gegen 1 oder 0 für <math>n \rightarrow \infty</math>? Man sagt dann auch, fast alle oder fast gar keine Graphen erfüllen die Eigenschaft <math>Q</math> (siehe auch [[Rado-Graph#Null-Eins-Gesetz der Prädikatenlogik erster Stufe|hier]]).

== Wichtige Ergebnisse ==
Durch Anwendung der [[Probabilistische Methode|probabilistischen Methode]] auf sein Zufallsgraphenmodell bewies [[Paul Erdős]] den Satz: Für jede natürliche Zahl <math>k</math> gibt es einen Graphen, bei dem sowohl [[Taillenweite (Graphentheorie)|Taillenweite]] (Länge des kürzesten Kreises) als auch [[Chromatische Zahl]] größer als k sind.<ref>Reinhard Diestel, Graphentheorie, Berlin, Heidelberg, New York: Springer, 3. Auflage 2006, S. 256ff.</ref>

Im selben Zufallsgraphenmodell konnte gezeigt werden, dass [[Graphenisomorphismus|Isomorphie]] zu einem beliebigen Graphen für [[fast alle]] Graphen in linearer Zeit entscheidbar ist.<ref>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. [http://vlsicad.eecs.umich.edu/BK/SAUCY/papers/1980-35.pdf online]</ref>

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

== Einzelnachweise ==
<references />

[[Kategorie:Graphenklasse]]
[[Kategorie:Grundbegriff (Graphentheorie)]]
[[Kategorie:Stochastik]]

[[nl:Complexe netwerken#Random netwerken]]

Zufallsgraph - Versionsgeschichte

imported>Icy2008 am 20. April 2026 um 17:46 Uhr