Kreuzungszahl

Vollständige, geradlinige Graphen sind Graphen, bei denen jeder Knoten mit jedem anderen Knoten durch eine gerade Kante verbunden ist. Die kleinstmögliche Anzahl von Kreuzungspunkten, die sogenannte Kreuzungszahl, ist selbst unter vereinfachten Bedingungen – keine Kanten dürfen genau aufeinanderfallen, keine Kante darf durch Knoten laufen, nicht mehr als zwei Kanten dürfen sich in einem Kreuzungspunkt schneiden – für beliebige Knotenzahlen nicht so einfach zu bestimmen, wie es scheinen mag.

Irrtum! Seit 1960 versuchen sich viele Mathematiker dieser Welt an der Lösung, bis zum Jahr 2000 hatte man die Kreuzungszahl für Graphen mit maximal 9 Knoten ausgerechnet. Erst.


In 2000 dann wurde eine Lösung für 10 Knoten gefunden, indem man die möglichen 14 Millionen (!) verschiedenen / ungleichartigen Graphen systematisch erfasste und „durchrechnete“: bei nur zwei der 14 Millionen kam man auf das Minimum von 62 Kreuzungen. Bei 11 Knoten gibt es bereits 2 Milliarden solcher Graphen.

Die Vorgehensweise erinnert an die einzig mögliche Art, NP-vollständige Probleme zu lösen: Durchprobieren, denn es gibt keine deterministische Methode, um in polynominaler Zeit zu einer Entscheidung zu kommen.

Nun war Schluss mit „Durchrechnen“, die Zahl der verschiedenartigen ungleichartigen Graphen mit einer Knotenzahl größer 11 ist dermaßen groß, dass eine systematische Erfassung mit verfügbaren Computern unmöglich ist, trotz Ausschluss solcher Formen, die erfahrungsgemäß für eine minimale Kreuzungszahl sowieso nicht in Frage kommen können. Das „Rectilinear Crossing Number Project“ wurde durch die TU Graz initiiert. Mehr als 7500 Computer in 80 Ländern arbeiten mit.

Von einer allgemeinen Gleichung zur Berechnung für eine beliebige Knotenzahl ist man weit entfernt, „nur“ ungefähre Untergrenzen konnten ermittelt werden. Dies ist derzeit der Stand der Dinge in Sachen Kreuzungszahl:

Knoten Kreuzungszahl
1,2,3 0
4 0
5 1
6 3
7 9
8 19
9 36
10 62
11 102
12 153
13 229
14 324
15 447
16 603
17 798
18 1029
19 1318
20 1652
21 2055

Warum ich hier über dieses Thema schreibe, obwohl ich doch nun wirklich kein Mathematiker bin und auch keine Platinengraphen für elektronische Schaltungen zu entwerfen habe? Ich wollte ‚mal wieder TeXen, doch leider verschluckte sich mimeTeX an der picture-Umgebung, wenn nicht an mehr. Deshalb kein on-the-fly-GIF sondern ein statisches. Nicht geklaut.

(s.a. das Rectilinear Crossing Number Project, gefunden via F.A.Z.-Artikel)

Comments are Disabled