Extremale Graphentheorie

Die extremale Graphentheorie i​st ein Teilgebiet d​er Mathematik. Sie untersucht, welche Graphen e​iner gegebenen Klasse (wie d​er Klasse d​er Graphen o​hne Hamiltonkreis) e​inen bestimmten Graphenparameter (wie d​ie maximale Anzahl v​on Kanten o​der die Kantendichte) maximieren o​der minimieren.

Ein Ergebnis der extremalen Graphentheorie ist beispielsweise, dass Graphen mit ${\displaystyle n}$ Knoten, die keinen Kreis der Länge 3 enthalten, höchstens ${\displaystyle n^{2}/4}$ Kanten besitzen. Das ist ein Spezialfall des Satzes von Pál Turán (1941),[1] der die extremale Graphentheorie begründete:

Satz von Turán: Ein Graph mit n Knoten ohne p-Clique (vollständiger Untergraph mit p Knoten), ${\displaystyle p\geq 2}$, hat maximal ${\displaystyle \left(1-{\frac {1}{p-1}}\right){\frac {n^{2}}{2}}}$ Kanten.[2]

Definiert man zu einem Graphen ${\displaystyle H}$ die Zahl ${\displaystyle \mathrm {ex} (n,H)}$ als die maximale Kantenzahl, die ein Graph mit ${\displaystyle n}$ Knoten und ohne einen zu ${\displaystyle H}$ isomorphen Untergraphen haben kann, so lässt sich diese Aussage zu

${\displaystyle \mathrm {ex} (n,K_{p})\leq \left(1-{\frac {1}{p-1}}\right){\frac {n^{2}}{2}}}$

umformulieren, wobei ${\displaystyle K_{p}}$ der vollständige Graph mit ${\displaystyle p}$ Knoten ist. Bezeichnet man mit ${\displaystyle C_{p}}$ den Kreisgraphen mit ${\displaystyle p}$ Knoten, so erhält man als weiteres Beispiel

${\displaystyle K_{5}}$ erweitert um einen Knoten und eine Kante

${\displaystyle \mathrm {ex} (p,C_{p})\,=\,1+{\frac {(p-1)(p-2)}{2}}}$.

Der Graph, der aus ${\displaystyle K_{p-1}}$ durch Hinzunahme eines weiteren Knotens und einer Kante entsteht, hat keinen zu ${\displaystyle C_{p}}$ isomorphen Untergraphen und ${\displaystyle 1+{\frac {(p-1)(p-2)}{2}}}$ Kanten (siehe nebenstehende Zeichnung für ${\displaystyle p=6}$). Die Hinzunahme einer weiteren Kante führt offenbar zu einem zu ${\displaystyle C_{p}}$ isomorphen Untergraphen.

Siehe auch

• Ramsey-Theorie

Literatur

• Béla Bollobás: Extremal graph theory. Academic Press, London 1978, ISBN 0-12-111750-2.
• Frank Harary: Graphentheorie. R. Oldenbourg, München 1974, ISBN 3-486-34191-X.

Einzelnachweise

1. Turán: On an extremal problem in graph theory. In: Math.Fiz.Lapok. Bd. 48, 1941, S. 436.
2. Aigner, Günter M. Ziegler: Proofs from the Book. Springer. In Kapitel 32 werden fünf Beweise gegeben, unter anderem von Turán und Paul Erdős.