Der Satz von Turán (nach Pál Turán) ist eine Aussage aus dem mathematischen Teilgebiet der Graphentheorie. Er macht eine Aussage über die maximale Anzahl von Kanten, die ein Graph mit gegebener Knotenzahl haben kann, ohne einen vollständigen Untergraphen mit Knoten enthalten zu müssen.
Der Fall der Dreiecke Bearbeiten
Es sei ein ungerichteter Graph mit Knoten. Ein Untergraph aus drei Knoten heißt in naheliegender Weise ein Dreieck, wenn je zwei dieser drei Knoten durch eine Kante verbunden sind. Der Satz von Turán präzisiert die Aussage, dass der Graph, wenn er keine Dreiecke enthalten soll, nicht zu viele Kanten haben kann:
- Satz von Turán (Dreiecke): Hat ein Graph mit Knoten keine Dreiecke, so hat er höchstens Kanten.
Dabei ist die größte ganze Zahl, die kleiner gleich ist.
Für kleine ist die Aussage klar:
- : Dieser Graph hat weder Kanten noch Dreiecke und es ist .
- : Solche Graphen haben keine Dreiecke und höchstens eine Kante; es ist .
- : Solche Graphen haben genau dann ein Dreieck, wenn die Kantenzahl 3 ist; und es ist .
- : Es ist und tatsächlich hat jeder 4er-Graph mit 5 Kanten mindestens ein Dreieck.
Für größere führt man die Aussage auf Graphen mit Knoten zurück, was dann einen Induktionsbeweis ermöglicht, wobei man gerade und ungerade unterscheiden muss. Hier soll nur der Fall für gerade kurz angedeutet werden:
Man entferne eine Kante, die zwei Knoten und verbindet, aus . Der so erhaltene Untergraph enthält ebenfalls keine Dreiecke und nur Knoten, also gemäß Induktionsvoraussetzung höchstens Kanten. Der Graph hat darüber hinaus noch die entfernte Kante und weitere Kanten, die von oder ausgehen und in enden. Gehen etwa von aus, so müssen die von ausgehenden Kanten in anderen Knoten von enden, denn anderenfalls enthielte ein Dreieck, das heißt von können höchstens Kanten in endende ausgehen. Die maximal mögliche Kantenzahl von ist daher . Daraus folgt die Behauptung für gerade . Der Fall ungerader kann ganz ähnlich behandelt werden.
Die durch den Satz von Turán angegebene Grenze ist scharf, wie das Beispiel des bipartiten Graphen zeigt, denn dieser Graph hat Knoten und Kanten.
Der Turán-Graph Bearbeiten
Ein Dreieck ist der vollständige Graph . Es stellt sich daher die Frage, ob man eine Obergrenze für die Anzahl von Kanten eines Graphen, der keinen zu isomorphen Untergraphen enthält, angeben kann. Um diese Frage beantworten zu können, wird der so genannte Turán-Graph wie folgt definiert:
Der Turán-Graph ist der vollständige m-partite Graph, der in der k-ten Klasse Elemente hat. Beachte dazu, dass
gilt und daher Knoten hat. Die Anzahl der Kanten von werde mit bezeichnet. Man kann zeigen, dass
wobei ist und für die Division mit Rest steht.
Der nebenstehende Turán-Graph hat demnach Kanten.
Eine leichte Rechnung zeigt . Diese obere Abschätzung der Kantenzahl des Turán-Graphen wird häufig verwendet.
Der allgemeine Fall Bearbeiten
- Satz von Turán: Hat ein Graph mit Knoten keinen zu isomorphen Untergraphen (), so hat er höchstens Kanten. Jeder Graph ohne einen zu isomorphen Untergraphen mit Knoten und Kanten ist isomorph zum Turán-Graphen .
In der extremalen Graphentheorie definiert man zu einem Graphen die Zahl als die maximale Kantenzahl, die ein Graph mit Knoten und ohne einen zu isomorphen Untergraphen haben kann. Der Satz von Turán hat daher folgendes Korollar:
Der Satz von Turán sagt aber mehr aus, nämlich dass je zwei Graphen mit Knoten ohne einen zu isomorphen Untergraphen, die diesen Extremwert realisieren, isomorph zu sind.
Ist und gerade, so ist und daher . Ist ungerade, so ist und daher . Daher ist und man erhält den bereits oben besprochenen Spezialfall der Dreiecke.
Die im Satz vorgenommene Einschränkung kann zu abgeschwächt werden, auch wenn der dadurch entstehende Fall nicht sonderlich interessant ist. Ein Graph ohne einen zu isomorphen Untergraphen ist ein kantenloser Graph und tatsächlich ist für alle . Auch die Fälle müssen nicht ausgeschlossen werden. Für ist in der oben für angegebenen Formel, und es ist daher ; man erhält daher die triviale Aussage, dass ein Graph mit Knoten genau dann einen zu isomorphen Untergraphen enthält, wenn er vollständig ist, denn hat Kanten. Ist , so ist und daher , ist so ist und daher ebenfalls ; das heißt, in den Fällen kann der Graph so viele Kanten wie möglich haben, was klar ist, da er ohnehin keinen zu isomorphen Untergraphen enthalten kann.
Literatur Bearbeiten
- K. Wagner: Graphentheorie. Bibliographisches Institut, Mannheim 1970, ISBN 3-411-00248-4
- P. Turan: Eine Extremalaufgabe aus der Graphentheorie. In: Mat. Fiz. Lapok., 48, 1941, S. 436–452 (ungarisch)
Einzelnachweise Bearbeiten
- Frank Harary: Graphentheorie. R. Oldenbourg, München 1974, ISBN 3-486-34191-X.
- Béla Bollobás: Graph Theory, An Introductory Course. Springer Verlag, New York 1979, ISBN 0-387-90399-2, IV, §2, Theorem 6