imported>FranzR am 24. August 2014 um 13:59 Uhr

2014-08-24T13:59:52Z

Neue Seite

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

Ein Ergebnis der extremalen Graphentheorie ist beispielsweise, dass Graphen mit <math>n</math> Knoten, die keinen Kreis der Länge 3 enthalten, höchstens <math>n^2/4</math> Kanten besitzen. Das ist ein Spezialfall des Satzes von [[Pál Turán]] (1941),<ref>Turán: ''On an extremal problem in graph theory.'' In: ''Math.Fiz.Lapok.'' Bd. 48, 1941, S. 436.</ref> der die extremale Graphentheorie begründete:

[[Satz von Turán]]: Ein Graph mit n Knoten ohne p-[[Clique (Graphentheorie)|Clique]] (vollständiger Untergraph mit p Knoten), <math>p \geq 2</math>, hat maximal <math>\left(1- \frac {1}{p-1}\right) \frac {n^2}{2}</math> Kanten.<ref>Aigner, [[Günter M. Ziegler]]: [[Das Buch der Beweise|''Proofs from the Book.'']] Springer. In Kapitel 32 werden fünf Beweise gegeben, unter anderem von Turán und [[Paul Erdős]].</ref>

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

:<math>\mathrm{ex}(n,K_p) \le \left(1-\frac{1}{p-1}\right)\frac{n^2}{2}</math>

umformulieren, wobei <math>K_p</math> der vollständige Graph mit <math>p</math> Knoten ist. Bezeichnet man mit <math>C_p</math> den Kreisgraphen mit <math>p</math> Knoten, so erhält man als weiteres Beispiel

[[Datei:K5PlusEineKante.PNG|mini|300px|<math>K_5</math> erweitert um einen Knoten und eine Kante]]

:<math>\mathrm{ex}(p,C_p) \,=\, 1 + \frac{(p-1)(p-2)}{2}</math>.

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

[[Kategorie:Graphentheorie]]

Extremale Graphentheorie - Versionsgeschichte

imported>FranzR am 24. August 2014 um 13:59 Uhr