Zufallsgraph
# Zufallsgraph

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

## Fragestellungen

Wichtige Fragestellungen bei zufälligen Graphen sind:

* Gegeben eine Eigenschaft $Q$, für welche $p$ bzw. $m$ und ab welcher Graphengröße $n$ besitzen alle Graphen die Eigenschaft $Q$?
* Gegeben eine Eigenschaft $Q$, geht die Wahrscheinlichkeit für $Q$ gegen 1 oder 0 für $n\rightarrow \infty$? Man sagt dann auch, fast alle oder fast gar keine Graphen erfüllen die Eigenschaft $Q$ (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 $k$ gibt es einen Graphen, bei dem sowohl Taillenweite (Länge des kürzesten Kreises) als auch Chromatische Zahl größer als k sind.

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

