Zufallsgraph

Ein Zufallsgraph oder zufälliger Graph bezeichnet einen Graphen, bei dem die Kanten zufällig erzeugt werden. Zufallsgraphen sind die Grundlage der Perkolationstheorie und lassen sich zur Modellierung poröser Medien oder in der Netzwerktheorie einsetzen.

Definition

Sei <math>K</math> eine abzählbare Menge von Knoten. Dann heißt ein Wahrscheinlichkeitsmaß <math>\mathbb P</math> auf der Kantenmenge <math>\lbrace \lbrace k,l \rbrace \vert k,l \in K \rbrace</math> Zufallsgraphenmodell.<ref>Matthias Löwe: Zufällige Graphen. Vorlesungsskript SS. 2009, abgerufen am 14. Juni 2026. </ref>

Beispiele

Mögliche Methoden, Zufallsgraphen zu erzeugen, sind:

• 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.

Gilbert-Modell

Datei:Random20-0.1-instance1.png

Realisierung des Gilbert-Graphen <math>G(20;\; 0{,}1)</math>

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 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.

Erdős-Rényi-Modell

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.

Perkolationsmodelle sind ebenfalls zufällige Graphen.

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 hier).

Wichtige Ergebnisse

Durch Anwendung der 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 (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 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. online</ref>

Anwendungen

Mithilfe von Zufallsgraphen lassen sich untere Schranken für Ramsey-Zahlen bestimmen.

Satz (Erdős, 1947).<ref>P. Erdös "Some remarks on the theory of graphs", Bulletin of the American Mathematical Society, Bull. Amer. Math. Soc. 53(4), 292-294, (April 1947)</ref><ref>Noga Alon, Joel H. Spencer: The probabilistic method (= Wiley-Interscience series in discrete mathematics and optimization). 4. print Auflage. Wiley, New York, NY 1992, ISBN 978-0-471-53588-1, Proposition 1.1.1. </ref> Für <math>n \geq k \geq 2</math>, wenn <math display="inline">\binom{n}{k}2^{1-\binom{k}{2}} < 1</math> , dann gilt <math>R(k,k) > n</math>.

Mithilfe der Stirlingschen Formel folgt

Korollar <math display="inline">R(k,k) > \frac{1}{e \sqrt{2}} k 2^{\frac{k}{2}}</math>

Zufallsgraphen sind auch nützlich zur Behandlung des Problems des Handlungsreisenden.

Lemma (Few, 1955)<ref>L. Few: The shortest path and the shortest road through n points. In: Mathematika. Band 2, Nr. 2, Dezember 1955, ISSN 0025-5793, S. 141–144, doi:10.1112/S0025579300000784 (wiley.com [abgerufen am 14. Juni 2026]). </ref> Bestimme <math>N</math> Punkte im Einheitsquadrat. Dann gilt, dass die Länge <math>L_N</math> der kürzesten Rundreise durch alle dieser <math>N</math> Punkte von oben durch <math>2 \sqrt{N} + 2 + \sqrt{2}</math> beschränkt ist.

Satz (Beaudward, Helton, Hammersby, 1959)<ref>Jillian Beardwood, J. H. Halton, J. M. Hammersley: The shortest path through many points. In: Mathematical Proceedings of the Cambridge Philosophical Society. Band 55, Nr. 4, Oktober 1959, ISSN 0305-0041, S. 299–327, doi:10.1017/S0305004100034095 (cambridge.org [abgerufen am 14. Juni 2026]). </ref> Es existiert <math>c > 0</math>, sodass fast sicher <math display="inline">\frac{L_N}{\sqrt{N}} \xrightarrow[N \to \infty]{\textrm{f.s.}} c</math> gilt.

Mithilfe des Lemmas von Few lässt sich zeigen, dass <math display="inline">c \in [\frac12, 2]</math>, doch ansonsten ist <math>c</math> weitestgehend unbekannt.

Literatur

• Douglas B. West: Introduction to Graph Theory. Prentice Hall, Upper Saddle River, N.J. 1996, ISBN 0-13-227828-6.
• Béla Bollobás: Random Graphs. 2. Auflage. Cambridge University Press, 2001, ISBN 978-0-521-79722-1. 

Einzelnachweise

<references />