Mathematik

Ebene Graphen – eine Herausforderung für Computer

Von Heinrich Hemme

07. Februar 2007 Die Mathematiker beschäftigen sich oft mit Problemen, die für die Realität keine Bedeutung zu haben scheinen. Zum Beispiel in der Graphentheorie.

Ein Graph ist eine Figur, die nur aus Punkten besteht und aus Linien, die einige dieser Punkte miteinander verbinden. Die Punkte nennt man Knoten, und die Linien heißen Kanten. Für den Mathematiker ist nur die topologische Struktur der Graphen von Bedeutung, nicht die exakte Anordnung der Elemente. Man kann sich deshalb die Knoten als Perlen vorstellen und die Kanten als Gummifäden. Man darf die Perlen anordnen, wie man möchte, und die Fäden beliebig verschlingen, ohne dass sich der Graph dadurch verändert. Zwei Graphen können also ganz unterschiedlich aussehen, aber tatsächlich nur zwei verschiedene Darstellungen ein und desselben Graphen sein.

Vergleich mit Leiterbahnen

Bei näherem Hinschauen erkennt man die Verwandtschaft mit einer elektronischen Schaltung. Diese besteht aus Bauelementen mit dünnen Kupferschichten, in die Leiterbahnen geätzt sind, die die einzelnen Elemente verbinden. Mathematisch gesehen, sind die Leiterbahnen Kanten eines Graphen und die Lötstellen die Knoten.

Die genaue Linienführung der Leiterbahnen ist meistens nur von untergeordneter Bedeutung, solange sie nur die richtigen Bauelemente miteinander verbinden. Die Platinengraphen dürfen sich allerdings physisch nicht kreuzen; denn sonst gibt es Kurzschlüsse zwischen den Leiterbahnen. Im Falle der ebenen – zweidimensionalen – Graphen der Mathematik dagegen kann es Kreuzungspunkte geben, nämlich die Schnittstellen von Kanten, und diese sind für die Theoretiker von besonderem Interesse. Bei dem Versuch, eines der Probleme zu lösen, sind sie jetzt selbst an die Grenzen moderner Computer gelangt.

Gesucht: Die Kreuzungszahl

Zum Thema

Homepage des Projekts „Rectilinear Crossing Number”

Die Mathematiker haben sich dabei einer besonderen Gruppe unter den ebenen Graphen zugewendet – den vollständigen geradlinigen Graphen, bei denen jeder Knoten mit jedem anderen Knoten durch eine gerade Kante verbunden ist. Sie interessierte die kleinstmögliche Anzahl von Kreuzungspunkten eines Graphen, die sogenannte Kreuzungszahl, und zwar unter der Voraussetzung, dass keine Kanten genau aufeinanderfallen, keine Kanten durch Knoten laufen und sich nicht mehr als zwei Kanten in einem Kreuzungspunkt schneiden.

Man könnte meinen, wenn man das allgemeine Kreuzungszahl-Problem so stark einschränkt und vereinfacht, sollte es doch leicht möglich sein, die Kreuzungszahl für beliebige Knotenzahlen zu bestimmen. Aber das ist ein Irrtum. 1960 blies deshalb der bekannte englische Mathematiker Richard K. Guy mit einem Artikel in der Zeitschrift Nabla zur Jagd auf die Kreuzungszahlen. Viele Mathematiker folgten dem Ruf, dennoch war die Beute gering: Bis zum Jahr 2000 hatte man erst die Kreuzungszahlen für Graphen mit höchstens neun Knoten ermittelt.

Rasch zunehmende Zahl

Graphen mit nur einem, zwei oder drei Knoten können grundsätzlich keine Kreuzungspunkte besitzen. Auch vier Knoten kann man so anordnen, dass sich die sechs Kanten des Graphen nirgendwo schneiden. Erst bei einem Graphen mit fünf Knoten gibt es mindestens einen Kreuzungspunkt. Mit höher werdender Knotenzahl steigt die Kreuzungszahl rasch an: Bei sechs Knoten beträgt sie 3, bei sieben Knoten 9, bei acht Knoten 19 und bei neun Knoten 36.

Im Jahre 2000 schließlich gelang es Alex Brodsky, Stephane Durocher und Ellen Gether von der University of British Columbia in Vancouver, für Graphen mit zehn Knoten die Kreuzungszahl zu bestimmen. Unabhängig davon und mit einem anderen Verfahren sind Oswin Aichholzer, Franz Aurenhammer und Hannes Krasser von der Technischen Universität Graz zu demselben Ergebnis gelangt.

Verschiedene Formen

Den Mathematikern um Aichholzer ging es zunächst um etwas ganz anderes. Sie wollten die verschiedenen Formen eines vollständigen, ebenen, geradlinigen Graphen mit einer bestimmten Knotenzahl ermitteln. Von Graphen mit einem, zwei oder drei Knoten gibt es jeweils nur eine Form. Erst Graphen mit vier Punkten treten in zwei verschiedenartigen Formen auf. Bei der einen Form liegen die vier Knoten auf den Ecken eines konvexen Vierecks, und die sechs Kanten sind seine Seiten und Diagonalen. Dabei kreuzen sich die Diagonalen in einem Punkt. Bei der anderen Form bilden drei Knoten und die sie verbindenden Kanten ein Dreieck. Der vierte Knoten liegt im Inneren dieses Dreiecks. Die insgesamt sechs Kanten kreuzen sich an keiner Stelle.

Mit wachsender Knotenzahl nimmt die Zahl der ungleichartigen Graphen rasant zu. Bei zehn Punkten sind es schon 14 Millionen Graphen. Aichholzers Gruppe hat sie alle systematisch erfasst und dabei – gewissermaßen als Nebenprodukt – herausgefunden, dass die kleinste Anzahl von Kreuzungspunkten 62 beträgt und bei nur zwei der 14 Millionen ungleichartigen Graphen möglich ist. Alle anderen Formen haben mehr Kreuzungspunkte. Ermutigt durch diesen Erfolg, wandten sie ihr Verfahren auf Graphen mit elf Knoten an. Sie fanden über zwei Milliarden ungleichartige Graphen und entdeckten, dass die Kreuzungszahl 102 beträgt.

Netz aus 7500 Computern

Mit dem Ergebnis war die Grenze des Verfahrens erreicht. Die Zahl der verschiedenen ungleichartigen Graphen mit mehr als elf Knoten ist so groß, dass es auch mit den leistungsfähigsten Computern der Welt unmöglich ist, sie alle systematisch zu erfassen. Doch Aichholzer und seiner Gruppe ist es gelungen, ihr Verfahren so zu verfeinern, dass man von vornherein einen Großteil der Formen, die mit Sicherheit nicht die kleinstmögliche Kreuzungspunktzahl haben, ausschließen kann.

Auch für ihre Untersuchung wird aber eine so große Computerleistung benötigt, dass sie die Technische Universität Graz nicht aufbringen konnte. Deshalb rief Aichholzer 2004 das „Rectilinear Crossing Number Project“ ins Leben, bei dem jeder über das Internet der Gruppe Rechenkapazität auf seinem eigenen Computer zur Verfügung stellen kann (http://dist.ist.tugraz.at/cape5/). Inzwischen arbeiten mehr als 7500 Computer in 80 Ländern an dem Projekt.

Ein Graph mit 18 Knoten

Die Suche hatte schon bald Erfolg. In den folgenden zwei Jahren konnten die Kreuzungszahlen K für 12 bis 17 Knoten berechnet werden: K(12) = 153, K(13) = 229, K(14) = 324, K(15) = 447, K(16) = 603 und K(17) = 798. Von einer allgemeinen Gleichung, mit der man für beliebige Knotenzahlen die Kreuzungszahl berechnen kann, ist man allerdings noch weit entfernt.

Jedoch gelang es Aichholzer, Gleichungen zu entwickeln, mit denen man Untergrenzen für die Kreuzungszahlen bestimmen kann. Da er für die Knotenzahlen 19 und 21 Beispiele fand, deren Kreuzungszahlen genau gleich den Untergrenzen waren, konnte er auch K(19) = 1318 und K(21) = 2055 ermitteln. Im Dezember vergangenen Jahres ist es Aichholzer und seiner Gruppe schließlich gelungen, mit einer weltweiten Computerkapazität von 10 000 CPU-Stunden pro Tag auch die Kreuzungszahl für Graphen mit 18 Knoten zu berechnen. Sie beträgt, wie im Januar rechnerisch bestätigt worden ist, 1029.

Text: F.A.Z.
Bildmaterial: F.A.Z.

Lesermeinungen zum Beitrag [1]