Satz von Turán

Satz von Turán

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 m Knoten enthalten zu müssen.

Inhaltsverzeichnis

Der Fall der Dreiecke

Es sei G ein ungerichteter Graph mit n 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 G mit n Knoten keine Dreiecke, so hat er höchstens \left\lfloor \frac{n^2}{4} \right\rfloor Kanten.

Dabei ist \lfloor x \rfloor die größte ganze Zahl, die kleiner gleich x ist.

Für kleine n ist die Aussage klar:

Graphen mit 4 Knoten und mindestens 5 Kanten enthalten mindestens ein Dreieck.
  • n = 1: Dieser Graph hat weder Kanten noch Dreiecke und es ist \left\lfloor \frac{1^2}{4} \right\rfloor = 0.
  • n = 2: Solche Graphen haben keine Dreiecke und höchstens eine Kante; es ist \left\lfloor \frac{2^2}{4} \right\rfloor = 1.
  • n = 3: Solche Graphen haben genau dann ein Dreieck, wenn die Kantenzahl 3 ist; und es ist \left\lfloor \frac{3^2}{4} \right\rfloor = 2.
  • n = 4: Es ist \left\lfloor \frac{4^2}{4} \right\rfloor = 4 und tatsächlich hat jeder 4er-Graph mit 5 Kanten mindestens ein Dreieck.

Für größere n führt man die Aussage auf Graphen mit n − 2 Knoten zurück, was dann einen Induktionsbeweis ermöglicht, wobei man gerade und ungerade n unterscheiden muss. Hier soll nur der Fall für gerade n kurz angedeutet werden:

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

Man entferne eine Kante, die zwei Knoten a und b verbindet, aus G. Der so erhaltene Untergraph enthält ebenfalls keine Dreiecke und nur n − 2 Knoten, also gemäß Induktionsvoraussetzung höchstens \left\lfloor \frac{(n-2)^2}{4}\right\rfloor = \frac{(n-2)^2}{4} Kanten. Der Graph G hat darüber hinaus noch die entfernte Kante und weitere Kanten, die von a oder b ausgehen und in G\setminus\{a,b\} enden. Gehen etwa k von a aus, so müssen die von b ausgehenden Kanten in anderen Knoten von G\setminus \{a,b\} enden, denn anderenfalls enthielte G ein Dreieck, das heißt von b können höchstens n − 2 − k Kanten in G\setminus \{a,b\} endende ausgehen. Die maximal mögliche Kantenzahl von G ist daher  \frac{(n-2)^2}{4}+1+k+(n-2-k) \,=\, \frac{n^{2}-4n+4}{4} + 1 + n - 2 \,=\, \frac{n^2}{4} - n +1 + 1 + n - 2 \,=\, \frac{n^2}{4}. Daraus folgt die Behauptung für gerade n. Der Fall ungerader n kann ganz ähnlich behandelt werden.

Die durch den Satz von Turán angegebene Grenze ist scharf, wie das Beispiel des bipartiten Graphen Kn,n zeigt, denn dieser Graph hat 2n Knoten und n^2 = \frac{(2n)^2}{4} Kanten.

Der Turán-Graph

Ein Dreieck ist der vollständige Graph K3. Es stellt sich daher die Frage, ob man eine Obergrenze für die Anzahl von Kanten eines Graphen, der keinen zu Km 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 T3(7)

Der Turán-Graph Tm(n) ist der vollständige m-partite Graph, der in der k-ten Klasse \lfloor \frac{n+k-1}{m} \rfloor Elemente hat. Beachte dazu, dass

\lfloor \frac{n}{m}\rfloor + \lfloor \frac{n+1}{m}\rfloor + \ldots + \lfloor \frac{n+m-1}{m}\rfloor = n

gilt und Tm(n) daher n Knoten hat. Die Anzahl der Kanten von Tm(n) werde mit tm(n) bezeichnet. Man kann zeigen, dass

t_m(n) = \frac{(m-1)(n^2-r^2)}{2m} + \frac{r(r-1)}{2}

wobei  r \equiv n \,\mathrm{mod} \,m,\,\, 0 \le r < m ist und mod für die Division mit Rest steht.

Der nebenstehende Turán-Graph T3(7) hat demnach  \frac{(3-1)(49-1)}{2\cdot 3} + \frac{1\cdot(1-1)}{2} = \frac {2\cdot 48}{6} = 16 Kanten.

Eine leichte Rechnung zeigt t_m(n) = \frac{n^2}{2}(1-\frac{1}{m} +\frac{r^2}{mn^2}-\frac{r}{n^2}) \le \frac{n^2}{2}(1-\frac{1}{m}). Diese obere Abschätzung der Kantenzahl des Turán-Graphen wird häufig verwendet.

Der allgemeine Fall

  • Satz von Turán[2]: Hat ein Graph G mit n Knoten keinen zu Km isomorphen Untergraphen ( m \ge 3 ), so hat er höchstens tm − 1(n) Kanten. Jeder Graph ohne einen zu Km isomorphen Untergraphen mit n Knoten und tm − 1(n) Kanten ist isomorph zum Turán-Graphen Tm − 1(n).

In der extremalen Graphentheorie definiert man zu einem Graphen H die Zahl ex(n,H) als die maximale Kantenzahl, die ein Graph mit n Knoten und ohne einen zu H isomorphen Untergraphen haben kann. Der Satz von Turán hat daher folgendes Korollar:

 \mathrm{ex}(n,K_m) \,=\, t_{m-1}(n) \le \frac{n^2}{2}\cdot(1-\frac{1}{m-1})

Der Satz von Turán sagt aber mehr aus, nämlich dass je zwei Graphen mit n Knoten ohne einen zu Km isomorphen Untergraphen, die diesen Extremwert realisieren, isomorph zu Tm − 1(n) sind.

Ist m = 3 und n gerade, so ist  0 \equiv n \,\mathrm{mod}\, 2 und daher t_2(n) = \frac{(2-1)(n^2-0^2)}{2\cdot 2} + 0 = \frac{n^2}{4}. Ist n ungerade, so ist  1 \equiv n \,\mathrm{mod}\, 2 und daher t_2(n) = \frac{(2-1)(n^2-1^2)}{2\cdot 2} + 0 = \frac{n^2-1}{4} = \lfloor \frac{n^2}{4}\rfloor . Daher ist  \mathrm{ex}(n,K_3) \,=\, \lfloor \frac{n^2}{4} \rfloor und man erhält den bereits oben besprochenen Spezialfall der Dreiecke.

Die im Satz vorgenommene Einschränkung m\ge 3 kann zu m\ge 2 abgeschwächt werden, auch wenn der dadurch entstehende Fall nicht sonderlich interessant ist. Ein Graph ohne einen zu K2 isomorphen Untergraphen ist ein kantenloser Graph und tatsächlich ist t1(n) = 0 für alle n. Auch die Fälle m \ge n müssen nicht ausgeschlossen werden. Für m = n ist r = 1 in der oben für tm(n) angegebenen Formel, und es ist daher t_{n-1}(n) = \frac{(n-2)(n^2-1)}{2(n-1)}+0 = \frac{(n-2)(n+1)}{2} = \frac{n(n-1)}{2} - 1; man erhält daher die triviale Aussage, dass ein Graph mit n Knoten genau dann einen zu Kn isomorphen Untergraphen enthält, wenn er vollständig ist, denn Kn hat \frac{n(n-1)}{2} Kanten. Ist m = n + 1, so ist r = 0 und daher t_m(n) = \frac{n(n-1)}{2}, ist m > n + 1 so ist r = n und daher ebenfalls t_{m-1}(n) = \frac{r(r-1)}{2} = \frac{n(n-1)}{2}; das heißt, in den Fällen m > n kann der Graph so viele Kanten wie möglich haben, was klar ist, da er ohnehin keinen zu Km isomorphen Untergraphen enthalten kann.

Einzelnachweise

  1. Frank Harary: Graphentheorie. R. Oldenburg, 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

Literatur

  • K. Wagner: Graphentheorie, Bibliographisches Institut AG, Mannheim (1970), ISBN 3-411-00248-4
  • P. Turan: Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok. 48 (1941), Seiten 436-452 (Ungarisch)

Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Satz von Erdös-Kac — Der Satz von Erdős–Kac [ˈɛrdøːʃ kaʦ] von Paul Erdős und Mark Kac ist ein Satz aus der Zahlentheorie und besagt, dass die Anzahl der verschiedenen Primfaktoren ω(n) einer zufällig gezogenen Zahl n aus der Menge für große annähernd normalverteilt… …   Deutsch Wikipedia

  • Satz von Erdős–Kac — Der Satz von Erdős–Kac [ˈɛrdøːʃ kaʦ] von Paul Erdős und Mark Kac ist ein Satz aus der Zahlentheorie und besagt, dass die Anzahl der verschiedenen Primfaktoren ω(n) einer zufällig gezogenen Zahl n aus der Menge für große annähernd normalverteilt… …   Deutsch Wikipedia

  • Satz von Erdős-Kac — Der Satz von Erdős–Kac [ˈɛrdøːʃ kaʦ] von Paul Erdős und Mark Kac ist ein Satz aus der Zahlentheorie und besagt, dass die Anzahl der verschiedenen Primfaktoren ω(n) einer zufällig gezogenen Zahl n aus der Menge für große annähernd normalverteilt… …   Deutsch Wikipedia

  • Pál Turán — Pál Turán, 1955 Pál Turán (auch: Paul Turán; * 18. August 1910 in Budapest; † 26. September 1976 ebenda)[1] war ein u …   Deutsch Wikipedia

  • Das BUCH der Beweise — (engl. Proofs from THE BOOK) ist ein Buch der Mathematiker Martin Aigner und Günter M. Ziegler, das besonders schöne Beweise enthalten soll. Es wurde 1998 auf Englisch und 2002 auf Deutsch herausgegeben sowie in weiteren Sprachen veröffentlicht.… …   Deutsch Wikipedia

  • Liste mathematischer Sätze — Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A Satz von Abel Ruffini: eine allgemeine Polynomgleichung vom …   Deutsch Wikipedia

  • Extremale Graphentheorie — Die extremale Graphentheorie ist ein Teilgebiet der Mathematik. Sie untersucht, welche Graphen einer gegebenen Klasse (wie die Klasse der Graphen ohne Hamiltonkreis) einen bestimmten Graphenparameter (wie die maximale Anzahl von Kanten)… …   Deutsch Wikipedia

  • Paul Erdős — auf einem Seminar in Budapest (Herbst 1992) Paul Erdős [ˈɛrdøːʃ] (ungarisch Erdős Pál; * 26. März 1913 in Budapest, Österreich Ungarn; † 20. September …   Deutsch Wikipedia

  • Paul Erdos — Paul Erdős auf einem Seminar in Budapest (Herbst 1992) Paul Erdős [ˈɛrdøːʃ] (ungarisch: Erdős Pál) (* 26. März 1913 in Budapest, Ungarn; † 20. September 1996 in Warschau, Polen) war …   Deutsch Wikipedia

  • Paul Erdös — Paul Erdős auf einem Seminar in Budapest (Herbst 1992) Paul Erdős [ˈɛrdøːʃ] (ungarisch: Erdős Pál) (* 26. März 1913 in Budapest, Ungarn; † 20. September 1996 in Warschau, Polen) war …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”