Extremale Graphentheorie

Die extremale Graphentheorie ist ein Teilgebiet der Mathematik. Sie untersucht, welche Graphen einer gegebenen Klasse (wie der Klasse der Graphen ohne Hamiltonkreis) einen bestimmten Graphenparameter (wie die maximale Anzahl von Kanten oder die Kantendichte) maximieren oder minimieren.

Ein Ergebnis der extremalen Graphentheorie ist beispielsweise, dass Graphen mit n {\displaystyle n} Knoten, die keinen Kreis der Länge 3 enthalten, höchstens n 2 / 4 {\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), p ≥ 2 {\displaystyle p\geq 2} , hat maximal ( 1 − 1 p − 1 ) n 2 2 {\displaystyle \left(1-{\frac {1}{p-1}}\right){\frac {n^{2}}{2}}} Kanten.[2]

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

e x ( n , K p ) ≤ ( 1 − 1 p − 1 ) n 2 2 {\displaystyle \mathrm {ex} (n,K_{p})\leq \left(1-{\frac {1}{p-1}}\right){\frac {n^{2}}{2}}}

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

K 5 {\displaystyle K_{5}} erweitert um einen Knoten und eine Kante
e x ( p , C p ) = 1 + ( p − 1 ) ( p − 2 ) 2 {\displaystyle \mathrm {ex} (p,C_{p})\,=\,1+{\frac {(p-1)(p-2)}{2}}} .

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