Lexikon der Mathematik: Zufällige Graphen
H.-J. Prömel und A. Taraz
Einordnung
Die Theorie zufälliger Graphen hat sich in jüngerer Zeit als ein äußerst lebendiges Teilgebiet der Graphentheorie herauskristallisiert. Sie verbindet Methoden der Kombinatorik mit denen der Wahrscheinlichkeitstheorie und schlägt mit ihren Resultaten Brücken von der Diskreten Mathematik bis hin zu Teilgebieten der Theoretischen Informatik.
Modell
Um das zugrundeliegende Zufallsexperiment zu beschreiben, sind zunächst einige einfache Definitionen notwendig. Ein Graph G besteht aus einer Knotenmenge V = V(G) und einer Kantenmenge E = E(G), wobei E ⊆ [V]2 ist. Graphen werden häufig wie folgt visualisiert. Die Knoten sind durch Punkte in der Ebene repräsentiert, und je zwei Knoten, die eine Kante bilden, sind durch eine Linie verbunden (Abbildung 1). Ein Subgraph H von G ist durch eine Knotenmenge E(H) ⊆ [V(G) und eine Kantenmenge E(H) ⊆ [V(H)]2 ∩ E(G) gegeben.
Abbildung 1: Beispiel für die Visualisierung eines Graphen
Sei n eine natürliche Zahl, und p = p(n) eine Funktion mit Werten zwischen 0 und 1. Ein zufälliger Graph, mit Gn,p bezeichnet, wird dadurch generiert, daß in einem Zufallsexperiment jede auf der Knotenmenge {1, …, n} mögliche Kante unabhängig mit Wahrscheinlichkeit p existiert. Wählt man p = 1/2, so sind alle Graphen als Ausgang des Experiments gleichwahrscheinlich, d. h. man erhält die Gleichverteilung auf der Klasse aller Graphen.
Probabilistische Methode
Lange bevor zufällige Graphen als eigenständiger Forschungsgegenstand auftraten, wurden sie als Hilfsmittel für Existenzbeweise benutzt. Die Grundidee ist hierbei die folgende: Um die Existenz eines Objekts mit einer gewünschten Struktur nachzuweisen, generiert man durch ein (geeignet abgestimmtes) Zufallsexperiment ein zufälliges Objekt und zeigt, daß die Wahrscheinlichkeit, daß das Objekt die gewünschte Struktur hat, positiv ist. Dieser Ansatz, oft als die Probabilistische Methode bezeichnet, wurde maßgeblich von Paul Erdős geprägt. Die beiden folgenden Beispiele gehen auf Erdős zurück.
Das erste prominente Beispiel der Probabilistischen Methode stammt aus dem Jahre 1947 und befaßt sich mit Cliquen, stabilen Mengen und der Ramseyfunktion. Eine Clique (bzw. eine stabile Menge) in einem Graph ist ein Subgraph, der dadurch definiert ist, daß jedes (bzw. keines) seiner Knotenpaare eine Kante bildet. Frank P. Ramsey hatte bereits 1930 bewiesen, daß zu je zwei natürlichen Zahlen s und t eine kleinste natürliche Zahl R(s, t) existiert, so daß jeder Graph auf n Knoten eine Clique der Größe s oder eine stabile Menge der Größe t enthalten muß. Auf der Suche nach unteren Schranken für R(s, t) betrachtete Erdős den zufälligen Graphen Gn,1/2. Die Wahrscheinlichkeit dafür, daß eine festgewählte Menge von s Knoten in Gn,1/2 eine Clique bildet, beträgt offensichtlich genau \({2}^{-\left(\begin{array}{c}s\\2\end{array}\right)}\). Somit ist die Wahrscheinlichkeit, daß Gn,1/2 eine Clique oder eine stabile Menge der Größe s besitzt, höchstens
Das zweite Beispiel beschäftigt sich mit Kreisen und der chromatischen Zahl eines Graphen G. Ein Kreis ist ein Subgraph, dessen Knoten zyklisch durch Kanten verbunden sind. Die chromatische Zahl χ(G) ist definiert als die kleinste Zahl von Farben, die benötigt werden, um die Knoten von G so zu färben, daß je zwei, die eine Kante bilden, verschieden gefärbt sind. Intuitiv scheint es einzuleuchten, daß die chromatische Zahl umso höher liegt, je „komplizierter“ der Graph aussieht. Insofern mag es andererseits überraschen, daß es zu je zwei natürlichen Zahlen k und ℓ einen kleinsten Graphen G(k, ℓ) gibt, dessen chromatische Zahl mindestens k beträgt, der aber keinen Kreis mit weniger als ℓ Knoten enthält. G(k, ℓ) ist also ein Graph, der einerseits eine hohe globale Komplexität besitzt, andererseits lokal sehr einfach aussieht. Die Existenz eines solchen Graphen läßt sich ebenfalls mit Hilfe der Probabilistischen Methode zeigen. Dabei startet man mit Gn,p und einem bestimmten p = p(n). Gn,p hat die erforderlichen Eigenschaften noch nicht, aber es läßt sich zeigen, daß man mit positiver Wahrscheinlichkeit einen Graphen mit den gewünschten Eigenschaften erhält, wenn man in Gn,p alle kurzen Kreise löscht.
Erstaunlich an diesen beiden Beispielen ist, daß es trotz energischer Versuche noch keine konstruktiven Beweise gibt, die auch nur annähernd an die Schranken für R(s, s) und G(k, ℓ) von Erdős heranreichen. Dies zeigt, daß zufällige Strukturen genau die Art von Regelmäßigkeit aufweisen, die man zur Lösung dieser und ähnlicher Probleme braucht, und das, obwohl Zufall ja häufig mit Chaos gleichgesetzt und als Gegenteil von Ordnung angesehen wird.
0-1-Gesetze, Phasenübergänge, Evolution
Zufällige Graphen traten erstmals um 1960 in einer Serie von wegweisenden Arbeiten von Paul Erdős und Alfred Rényi als eigenständiger Forschungsgegenstand auf. Die zentrale Frage – Gegeben eine bestimmte Grapheneigenschaft \({\mathcal{A}}\), wie groß ist die Wahrscheinlichkeit \(\Pr ({G}_{n,p}\in \mathcal{A})\), daß sie von einem zufälligen Graphen Gn,p erfüllt wird? – wird nun nicht mehr nur als Ansatz für Existenzbeweise gesehen, sondern als Selbstzweck untersucht.
Unabhängig von den betrachteten Eigenschaften zeigen sich hier zwei fundamentale Erkenntnisse.
0-1-Gesetze: Für die meisten festgelegten Kantenwahrscheinlichkeiten p = p(n) konvergiert \(\Pr ({G}_{n,p}\in \mathcal{A})\) mit wachsendem n gegen 0 oder 1.
Phasenübergänge: Die meisten Grapheneigenschaften besitzen eine Schwellenwertfunktion t(n), so daß für wachsendes n
Betrachtet man p als eine Art Zeitparameter, der von 0 bis 1 „läuft“, dann wird die Eigenschaft \({\mathcal{A}}\) also zunächst fast sicher nicht und nach Überschreiten des Schwellenwerts fast sicher angenommen. In diesem Zusammenhang spricht man von der Evolution: Gn,p entwickelt sich von einer stabilen Menge zu einer Clique auf n Knoten.
Für konstante Kantenwahrscheinlichkeiten p läßt sich beispielsweise zeigen, daß jede Eigenschaft, die sich in der Logik erster Stufe über Graphen ausdrücken läßt, ein 0-1-Gesetz besitzt. Ferner besagt ein Satz von Béla Bollobás und Andrew Thomason, daß jede Grapheneigenschaft, die abgeschlossen bezüglich der Addition von Kanten ist, eine Schwellenwertfunktion besitzt.
Erdős und Rényi gaben für viele interessante Eigenschaften Schwellenwertfunktionen an. Für die Eigenschaft, ein Dreieck (d. h. eine Clique der Länge 3) zu enthalten, liegt diese bei t(n) = 1/n. Dies läßt sich anschaulich dadurch begründen, daß die durchschnittliche Anzahl von Dreiecken in Gn,p durch \(({}_{3}^{n}){p}^{3}\) gegeben ist und daher mit wachsendem n gegen 0 oder ∞ strebt, je nach dem, ob p/t = p · n gegen 0 oder ∞ strebt. Wenn man mit der Dichte eines (Sub-)Graphen H das Verhältnis |E(H)|/|V(H)| bezeichnet, dann ist der Schwellenwert für das Auftreten spezieller Subgraphen offensichtlich um so höher, je dichter der Subgraph ist. Beispielsweise liegt der Schwellenwert für die Eigenschaft, einen Kreis zu besitzen, auch bei 1/n, und der Schwellenwert für das erste Auftreten einer Clique der Größe 4 bei n−2/3. Allgemein bestimmt sich der Schwellenwert für die Eigenschaft, eine Kopie eines festgewählten Graphen H als Subgraph zu enthalten, durch die Dichte des dichtesten Subgraphen von H, nämlich als
Zwei weitere grundlegende Grapheneigenschaften und ihre Schwellenwerte beschreiben, wie Gn,p im Laufe seiner Evolutionsgeschichte immer mehr zusammenwächst. Ein Graph heißt zusammenhängend, wenn man von jedem Knoten aus jeden Knoten über einen Weg – also eine Folge von sich berührenden Kanten – erreichen kann. Der Schwellenwert für diese Eigenschaft liegt bei t(n) = ln (n)/n und fällt interessanterweise mit dem Schwellenwert für die (offensichtlich notwendige) Eigenschaft, daß jeder Knoten in mindestens einer Kante liegt, zusammen. Nur wenig später wächst Gn,p noch mehr zusammen: t(n) = (ln n+ln ln n)/n markiert das erste Auftreten eines Hamiltonkreises, also eines Kreises, der jeden Knoten des Graphen genau einmal enthält. Auch dies koinzidiert mit dem Schwellenwert eines anderen Ereignisses, nämlich dem, daß jeder Knoten in mindestens zwei Kanten liegt.
Im „Inneren“ der Phasenübergänge
Was weiß man über das Verhalten der Wahrscheinlichkeit \(\Pr ({G}_{n,p}\in \mathcal{A)\), wenn p(n) von der gleichen Größenordnung ist wie t(n), also die Definition des Schwellenwerts nicht greift? Hier sind zwei unterschiedliche Phänomene zu beobachten: unscharfe und scharfe Phasenübergänge. Einige Eigenschaften kommen (relativ) langsam zur Geltung, so wie beispielsweise für p(n) = c/n gilt:
Andere Eigenschaften treten schlagartig ein: Für jedes beliebige ε > 0 gilt, daß für
Abbildung 2: Phasenübergänge für die Eigenschaften “hat Dreieck” (links) und “ist zusammenhängend” (rechts)
Doch auch innerhalb scharfer Phasenübergänge läßt sich der Weg von der 0 zur 1 nachverfolgen – häufig besteht hier die Kunst in der Wahl der richtigen Parametrisierung, also eines passenden Vergrößerungsglases oder einer adäquaten Zeitlupe. Wählt man beispielsweise p(n) = ln(n)/n+c/n, dann läßt sich zeigen, daß
Das Paradebeispiel für die richtige Wahl der Zeitlupe ist der Phasenübergang, den Gn,p am Schwellenwert t(n) = 1/n durchläuft. Bereits Erdős und Rényi konnten zeigen, daß Gn,p für p(n) = (1 − ε)/n fast sicher aus Zusammenhangskomponenten der Größenordnung höchstens log n besteht, daß für p(n) = 1/n bereits mehrere Komponenten der Größe n2/3 existieren, und bei p = (1 + ε)/n der Graph von einer einzigen großen Komponente beherrscht wird, die einen konstanten Anteil aller Knoten enthält. Mehr als 20 Jahre lang war jedoch die Frage offen, welche Kräfte und Mechanismen hier zu dem rasanten Zusammenwachsen während dieses sogenannten double jump beitragen, bevor sie in drei Arbeiten von Béla Bollobás, Tomasz Luczak und Svante Janson et al. auf der Basis der Parametrisierung p(n) = 1/n + λ/n4/3 beantwortet wurde.
Es werde angenommen, daß für ein gegebenes λ zwei Komponenten der Größe c1n2/3 und c2n2/3 existieren. Wenn man jetzt von λ zu λ + dλ übergeht, beträgt die Wahrscheinlichkeit, daß die Komponenten verschmelzen, c1c2dλ. Sie besitzen insofern eine Art Anziehungskraft, als daß die Wahrscheinlichkeit zuverschmelzen proportional zu ihrer Größe ist. Gleichzeitig erhalten größere Komponenten mehr und mehr Kreise und „schlucken“ einzelne Knoten. Eine sehr anschauliche Skizze findet sich in [1]: With λ = −106, say, we have feudalism. Many small components (castles) are each vying to be the largest. As λ increases, the components (nations) emerge. An already large France has much better chances of becoming larger than a smaller Andorra. The largest components tend strongly to merge and by λ = +106, it is very likely that a giant component, Roman Empire, has emerged. With high probability, this component is nevermore challenged for supremacy but continues absorbing smaller components until full connectivity – One World – is achieved.
Konzentration
Graphenparameter wie beispielsweise die chromatische Zahl χ(G) oder die Cliquenzahl ω(G) (d. h. die Kardinalität einer größten Clique) werden, wenn angewendet auf Gn,p, zu Zufallsvariablen. Ein wichtiges Ziel der Theorie zufälliger Graphen ist es, nicht nur das durchschnittliche Verhalten dieser Zufallsvariablen zu bestimmen, sondern auch zu zeigen, daß sie mit hoher Wahrscheinlichkeit um ihren Erwartungswert scharf konzentriert sind.
In der eingangs erwähnten Arbeit zeigte Erdős nicht nur, daß die Wahrscheinlichkeit Pr(ω(Gn,1/2) < 2 log n) positiv ist, sondern auch, daß sie für wachsendes n sogar gegen 1 konvergiert. David Matula gelang es 1976 darüber hinaus, eine weitaus stärkere Konzentrationsaussage zu beweisen. Die Cliquenzahl ist fast immer auf zwei Werte konzentriert: Es gibt eine Funktion l(n), die bis auf additive Konstanten die Größe 2 log n − 2 log log n hat und
Dieses Ergebnis mußte lange Zeit auf ein Analogon für die chromatische Zahl und damit auf die Beantwortung einer Frage von Erdős und Rényi aus dem Jahre 1960 warten. Da offensichtlich auch die Kardinalität einer größten stabilen Menge (und damit jede Farbklasse in einer Färbung) fast sicher kleiner als 2 log n sein muß, ist es offensichtlich, daß fast sicher χ(Gn,1/2) ≥ n/(2 log n) ist. Geoffrey Grimmett und Colin McDiarmid zeigten 1975 mit Hilfe eines einfachen Färbungsalgorithmus, daß fast sicher χ(Gn,1/2) ≤ (1 + ε)n/log n gilt. Eli Shamir und Joel Spencer konnten 1987 beweisen, daß χ(Gn,1/2) in einem Intervall der Größenordnung \(\sqrt{n}\) konzentriert ist, ohne jedoch eine Aussage darüber machen zu können, wo dieses Intervall genau liegt. Den Schlußpunkt setzte Bollobás mit dem Beweis, daß die untere Schranke von n/(2 log n) tatsächlich asymptotisch erreicht wird.
Die beiden zuletzt genannten Arbeiten beruhen darauf, daß man die Generierung eines zufälligen Graphen als Martingalprozeß auffaßt und in geschickter Weise Konzentrationsergebnisse für Martingale anwendet. Dieser Ansatz ist seitdem kontinuierlich weiterentwickelt worden und erfreut sich insbesondere auf dem Gebiet der Analyse randomisierter Algorithmen großer Erfolge.
Zufällige dreiecksfreie Graphen
Die Erforschung des Gn,p-Modells verdankt ihren Erfolg in erster Linie der Tatsache, daß sich der Wahrscheinlichkeitsraum durch unabhängige lokale Einzelexperimente modellieren läßt. Will man dagegen die Gleichverteilung auf einer Teilklasse aller Graphen untersuchen, die durch eine strukturelle Nebenbedingung charakterisiert sind, geht diese Unabhängigkeit verloren, und die Situation wird ungleich schwieriger. Als ein Beispiel betrachte man die Gleichverteilung auf der Klasse aller dreiecksfreier Graphen.
Wie sieht ein typischer dreiecksfreier Graph aus, welche chromatische Zahl hat er beispielsweise? Paul Erdős, Daniel Kleitman und Bruce Rothschild gaben auf diese Frage 1976 eine überraschende Antwort: Zwei! Sie bewiesen, daß der Anteil der zweifärbbaren Graphen innerhalb der Klasse der dreiecksfreien Graphen exponentiell schnell gegen 1 konvergiert. Die Beweismethodik ist wesentlich verschieden von den bisher angeführten Argumenten und folgt einer Strategie, die Kleitman und Rothschild kurz zuvor entwickelt hatten, um Strukturaussagen über zufällige partielle Ordnungen zu machen.
Das Resultat von Erdős, Kleitman und Rothschild wurde 1987 von Kolaitis, Prömel und Rothschild dahingehend verallgemeinert, daß für jedes festgewählte ℓ ein zufälliger Graph aus der Klasse aller Graphen, die keine Clique der Größe ℓ + 1 besitzen, fast sicher mit ℓ Farben zu färben ist. Auf dieser Klasse stimmen also chromatische Zahl und Cliquenzahl fast sicher überein. Diese Aussage kann, wie man aus den bereits vorgestellten Ergebnissen bezüglich χ(Gn,1/2) und ω(Gn,1/2) sofort sieht, spätestens für ℓ = 2 log n nicht mehr zutreffen. Die Frage von Erdős aus dem Jahre 1988, wie groß ℓ als Funktion von n werden kann, ohne die Aussage falsch werden zu lassen, ist nach wie vor offen.
Man betrachte nun das Resultat von Erdős, Kleitman und Rothschild von einem evolutionären Standpunkt aus. Wie groß ist die chromatische Zahl eines zufälligen dreiecksfreien Graphen G mit m Kanten? Osthus, Prömel und Taraz zeigten, daß hier gleich zwei Phasenübergänge stattfinden, die in Abbildung 3 dargestellt sind: Zunächst ist ein zufälliger dreiecksfreier Graph fast sicher zweifärbbar, dann fast sicher nicht, dann wieder fast sicher. Interessanterweise ist hier der erste Phasenübergang auf der linken Seite unscharf, der zweite jedoch scharf.
Ein anderes Modell dreiecksfreier Graphen erhält man durch den folgenden Zufallsprozesses. Beginnend mit dem leeren Graphen auf n Knoten wählt man in jedem Schritt ein zufälliges Knotenpaar (gleichverteilt) und fügt dort eine Kante ein, wenn dadurch kein Dreieck entsteht. Paul Erdős, Stephen Suen und Peter Winkler analysierten dieses Verfahren 1995 und zeigten, daß der resultierende Graph am Ende – wenn alle Kanten ihr Glück versucht haben – fast sicher ungefähr n3/2 Kanten hat. Überraschenderweise führt der scheinbar restriktivere Prozeß, bei dem nicht nur Dreiecke, sondern alle Kreise ungerader Länge verboten werden, zu einem mit einer quadratischen Anzahl von Kanten wesentlich dichteren Graphen.
Abbildung 3: Die Wahrscheinlichkeit, daß ein zufälliger dreiecksfreler Graph mit n Knoten und m Kanten zweifärbbar ist.
Zufällige Prozesse dieser Art können als eine Art randomisiertes Verfahren betrachtet werden, um spezielle Graphenklassen zu erzeugen. Dies kann einerseits mit der Absicht geschehen, Zufallsverteilungen zu simulieren und zu studieren, andererseits aber auch unter dem Aspekt probabilistischer Existenzbeweise, wie sie im einleitenden Abschnitt bereits angesprochen wurden. Die grundlegende Problematik bei solch einer iterativen probabilistischen Methode besteht darin, die Analyse in vernünftig gewählten Abschnitten durchzuführen: Versucht man, nach jedem Schritt eine neue Bestandsaufnahme zu machen, so läßt sich kein Fortschritt messen; wartet man zu lange, dann hat man die Kontrolle über den Prozeß verloren. Vojtěch Rödl demonstrierte 1985 mit einer Strategie, die mittlerweile auch Rödl nibble genannt wird, daß diese Gratwanderung möglich ist, und bestätigte auf diese Weise eine alte Vermutung von Paul Erdős und Haim Hanani über Packungen von Mengen aus dem Jahre 1963. Ein weiterer herausragender Satz, der mit Hilfe dieser Methode bewiesen wurde, ist die Bestimmung der eingangs vorgestellten Ramseyfunktion R(3, t). Jeong Han Kim konnte 1995 zeigen, daß R(3, t) die Größenordnung t2/ln2t hat.
Ausblick
Viele der Fragestellungen für zufällige Graphen übertragen sich in natürlicher Weise auf andere zufällige diskrete Strukturen. Naheliegende „Verwandte“ sind beispielsweise zufällige Matrizen oder zufällige partielle Ordnungen. Letztere stellen, ähnlich wie die bereits erörterten dreiecksfreien Graphen, einen Spezialfall von Graphen dar, den man durch eine zusätzliche Nebenbedingung erhält, in diesem Fall durch die Transitivität. Weitere Beispiele für spezielle Ausprägungen zufälliger Graphen, die zu eigenständigen Forschungsgebieten geführt haben, sind Spin-Gläser und Perkolationstheorie.
Die Theorie zufälliger Graphen wird aufverschiedenen Gebieten angewendet. Sie eröffnet beispielsweise die Möglichkeit, komplexe real existierende Strukturen wie Bekanntschaftsnetzwerke (insbesondere das world wide web) zu simulieren und zu analysieren. Darüberhinaus schafft sie durch die Charakterisierung typischer Struktureigenschaften von Graphen die Grundlagen für die average-case Analyse von Graphenalgorithmen und den Entwurf randomisierter Verfahren.
Literatur
[1] Alon, N., Spencer, J., Erdős, P.: The Probabilistic Method. Wiley & Sons New York, 2. Aufl. 2000.
[2] Bollobás, B.: Random Graphs. Academic Press London, 2. Aufl. 2001.
[3] Janson, S., Luczak, T., Ruciński, A.: Random Graphs. Wiley–Interscience New York, 2000.
[4] Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, 1995.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.