Direkt zum Inhalt

Lexikon der Mathematik: Kreuzungszahl

minimale Anzahl von Kreuzungen in einer normalen Einbettung eines Graphen in die Ebene ℝ2.

Da jeder Graph eine solche Einbettung besitzt, ist die Kreuzungszahl wohldefiniert. Oft sind für die Kreuzungszahl spezieller Graphen nur obere Schranken bekannt, die durch Angabe einer konkreten Einbettung bewiesen werden.

Die Kreuzungszahl des vollständigen Graphen Kn beträgt so höchstens \begin{eqnarray}\frac{1}{4}\lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \lfloor \frac{n-2}{2}\rfloor \lfloor \frac{n-3}{2}\rfloor,\end{eqnarray}

und die Kreuzungszahl des vollständigen bipartiten Graphen Kn,m beträgt höchstens \begin{eqnarray}\lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \lfloor \frac{m}{2}\rfloor \lfloor \frac{m-1}{2}\rfloor.\end{eqnarray}

Die Frage nach dem genauen Wert der Kreuzungszahl des vollständigen bipartiten Graphen ist als „Turán’s brick-factory problem“ bekannt.

Die oben angegebene Schranke wurde 1954 von K.Zarankiewicz bewiesen.

Abbildung 1 zum Lexikonartikel Kreuzungszahl
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Eine normale Einbettung des vollständigen bipartiten Graphen K4,5 in die Ebene ℝ2 mit \(\lfloor \frac{4}{2}\rfloor \lfloor \frac{3}{2}\rfloor \lfloor \frac{5}{2}\rfloor \lfloor \frac{4}{2}\rfloor =8\) Kreuzungen.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.