Satz von Turán

mathematischer Satz

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 DreieckeBearbeiten

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):[1] 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:

 
Graphen mit 4 Knoten und mindestens 5 Kanten enthalten mindestens ein Dreieck.
  •  : 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:

 
Entfernt man a und b aus G so verbleiben nur die schwarzen Kanten.

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-GraphBearbeiten

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 

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 FallBearbeiten

  • Satz von Turán:[2] 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.

LiteraturBearbeiten

  • 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)

EinzelnachweiseBearbeiten

  1. Frank Harary: Graphentheorie. R. Oldenbourg, München 1974, ISBN 3-486-34191-X.
  2. Béla Bollobás: Graph Theory, An Introductory Course. Springer Verlag, New York 1979, ISBN 0-387-90399-2, IV, §2, Theorem 6