Es zählt zu den besonderen Reizen der Mathematik, daß einige sehr einfach zu formulierende Probleme die besten Köpfe der Welt über Jahrhunderte beschäftigen können – zum Beispiel die Fermatsche Vermutung (Spektrum der Wissenschaft, August 1997, S. 113), das Keplersche Kugelpackungsproblem (Spektrum der Wissenschaft, April 1999, S. 10) oder die Vierfarbenvermutung. Alle drei sind erst in den letzten Jahrzehnten gelöst wurden. Insbesondere die Vierfarbenvermutung zog viele Amateure in ihren Bann, und der Beweis hat ihnen ihr schönstes Hobby geraubt – eigentlich schade.

Gibt es etwa nach den Erfolgen der letzten Jahre gar nichts Interessantes mehr für die Feierabendmathematiker zu tun? Doch.

Zunächst ein paar Worte über die Vierfarbenvermutung, die immerhin fast 150 Jahren den Bemühungen der Amateure wie der Profis widerstanden hat. Sie besagt, daß man jede ebene Landkarte mit nur vier Farben so färben kann, daß keine zwei Länder mit einem gemeinsamen Stück Grenze die gleiche Farbe erhalten. Kenneth Appel und Wolfgang Haken von der Universität von Illinois haben diese Behauptung 1976 mit Computerunterstützung bewiesen.

Der Vierfarbensatz – nun kann man ihn mit Fug einen Satz nennen – gehört zur sogenannten Graphentheorie. Ein Graph besteht aus einer Anzahl von "Ecken", die durch "Kanten" miteinander verbunden sind. Man pflegt Ecken durch Punkte und Kanten durch Linien zwischen diesen Punkten darzustellen; aber es kommt nicht darauf an, wo man die Ecken aufs Papier setzt und wie man die Kanten zwischen ihnen zeichnet. Wesentlich ist nur die abstrakte Struktur.

Eine zweidimensionale Landkarte kann man durch einen Graphen darstellen. Dazu zeichnet man einfach für jedes Land auf der Karte eine Ecke – sagen wir die Hauptstadt des Landes – und verbindet zwei Ecken durch eine Kante, wenn die entsprechenden Länder aneinandergrenzen. Man kann also das Vierfarbenproblem so umformulieren: Zu dem Graphen einer Landkarte ist eine Färbung der Ecken gesucht mit der Eigenschaft, daß nie zwei durch eine Kante verbundene Ecken die gleiche Farbe tragen.

Die Graphentheorie kennt – ähnlich wie die Zahlentheorie – zahllose Probleme, die leicht zu formulieren, aber schwer zu lösen sind. Viele von ihnen betreffen die Kreuzungszahl eines Graphen; das ist die kleinste Anzahl von Kreuzungen zwischen Kanten, mit denen sich ein Graph zeichnen läßt. Im Jahr 1970 schrieben die Mathematiker Paul Erdös und Richard K. Guy: "Fast alle Fragen, die man über die Kreuzungszahl stellen kann, bleiben ungelöst." Das gilt auch heute noch. Hier liegt auch künftig ein reichhaltiges Betätigungsfeld für Hobbymathematiker: Experimentieren Sie mit verschiedenen Graphen und versuchen Sie, die Anzahl der Kantenkreuzungen zu verkleinern. Es ist durchaus denkbar, daß durch solche Experimente eine ungelöste Vermutung widerlegt wird, indem sich ein Graph ergibt, der eine kleinere Kreuzungszahl hat als erwartet.

Graphen mit Kreuzungszahl 0 heißen auch planar: Sie lassen sich in der Ebene zeichnen, ohne daß irgendwelche Kanten sich überkreuzen. Betrachten Sie den ersten Graphen im Bild rechts oben. Zehn Knoten sind durch zehn Kanten miteinander verbunden. Die Kanten kreuzen sich viermal; gleichwohl ist der Graph planar, denn seine Bestandteile lassen sich so herumschieben, daß die Knoten einen Kreis bilden und alle Kreuzungen verschwinden. Graphen dieser Art nennt man Zyklen oder Kreise und bezeichnet sie mit C_n, wobei n die Anzahl der Ecken ist. Der abgebildete Graph ist also C₁₀.

Graph b im Bild rechts ist der vollständige Graph mit fünf Ecken, denn seine zehn Kanten verbinden jede Ecke mit jeder anderen. Dieser Graph wird mit K₅ bezeichnet; der vollständige Graph mit n Knoten heißt K_n. Der Graph K₅ ist nicht planar. Einerlei, wie man die Ecken und Kanten anordnet, stets gibt es mindestens eine Kreuzung. Folglich hat K₅ die Kreuzungszahl 1.

Der dritte Graph ist ein Beispiel für einen vollständigen bipartiten Graphen. Er besteht aus zwei Mengen von jeweils drei Ecken, wobei jede Ecke aus der einen Menge mit jeder aus der zweiten Menge durch eine Kante verbunden ist. Das Symbol für diesen Graphen ist K_3,3. Allgemein ist K_m,n der Graph, in dem jede von m Ecken auf der einen Seite mit jeder von n Ecken auf der anderen Seite durch eine Kante verbunden ist – und mit keinem der eigenen Seite. Auch K_3,3 hat Kreuzungszahl 1. Bekannt ist die folgende Einkleidung des Problems: Drei Häuser sollen an Quellen für Strom, Wasser und Gas angeschlossen werden, ohne daß die zugehörigen Leitungen sich überkreuzen. Das Problem ist unlösbar – es sei denn, man besinnt sich darauf, daß es auf der Erdoberfläche natürliche Brücken wie die berühmten Sandsteinbögen im Arches National Park in Utah gibt – und künstliche sowieso.

In sämtlichen nicht-planaren Graphen steckt einer dieser beiden einfachsten Graphen mit unvermeidbarer Überkreuzung. Das besagt ein Satz des polnischen Mathematikers Kazimierz Kuratowski (1896–1980): Ein Graph ist genau dann planar, wenn er keinen Teilgraphen enthält, der gleich K₅ oder K_3,3 ist.

Kreuzungszahlen für Lastkarren und Graphen

Angeblich kam der ungarische Mathematiker Paul Turán auf die Idee, den Begriff der Kreuzungszahl einzuführen, als er 1944 in einer Ziegelei in der Nähe von Budapest arbeitete. In der Fabrik gab es eine Reihe von Brennöfen für die Ziegel und eine Anzahl Lagerplätze. Von jedem Ofen zu jedem Lagerplatz verliefen Schienen. Die Arbeiter luden die Steine auf kleine Wagen, schoben diese auf den Schienen zu einem Lagerplatz und entluden sie. Diese Aufgabe war eigentlich einfach, außer an den Schienenkreuzungen. Dort sprangen die Wagen oft aus den Gleisen, und die Steine fielen heraus.

Ein Ingenieur hätte wahrscheinlich versucht, die Schienenkreuzungen nachzubessern. Turán, als Mathematiker, überlegte sich dagegen, wie man durch einen anderen Schienenverlauf die Anzahl der Kreuzungen reduzieren könnte. Nach einigen Tagen hatte er festgestellt, daß es in dieser Fabrik in der Tat eine Reihe vermeidbarer Schienenkreuzungen gab; und das allgemeine Problem ließ ihn nicht los. Wenn zwischen m Brennöfen und n Lagerplätzen jeweils eine Schienenverbindung verlaufen soll, dann heißt die abstrakte Formulierung: Bestimme die Kreuzungszahl für den vollständigen bipartiten Graphen K_m,n.

Dieses Problem ist bis heute ungelöst. Nadine C. Myers von der Hamline-Universität in St. Paul (Minnesota) schrieb im "Mathematics Magazine" vom Dezember 1998, daß Kreuzungszahlen nur für Graphen mit wenigen Ecken bekannt sind: für vollständige Graphen K_n mit n ­ 10 und vollständige bipartite Graphen K_m,n mit 3 ­ m ­ 6. Für Graphen mit größeren Eckenzahlen ist sehr wenig bekannt.

Zu einem anderen Graphentyp gehört das rechteckige Gitter auf einem Torus (Bild links). Es besteht aus zwei Familien von Kreisen: acht vertikale Kreise mit je sieben Ecken (C₇) und sieben horizontale – die vertikalen überkreuzende – Kreise mit je acht Ecken (C₈). Diesen Graphen kann man auf der Oberfläche eines Torus (Autoschlauchs) kreuzungsfrei zeichnen; die Kreise schneiden sich dann nur in den Ecken. Wenn man aber diesen Graphen – man bezeichnet ihn mit C₇ x C₈ – in die Ebene projiziert, produziert jeder der acht vertikalen Kreise 5 Kreuzungen: zusammen 40 Stück.

Das kann man auf m horizontale und n vertikale Kreise verallgemeinern; wir folgen der Konvention m ­ n. Jeder vertikale Kreis trifft den innersten und den äußersten horizontalen Kreis jeweils genau einmal, und zwar in einem Knoten. Die anderen m–2 Horizontalkreise schneidet er zweimal: einmal in einem Knoten, was einem echten Treffpunkt auf dem Torus entspricht, und einmal zwischen zwei Knoten, was von der Projektion in die Ebene herrührt. Also trägt jeder Vertikalkreis m–2 Kreuzungen bei; insgesamt hat der projizierte Graph n(m–2) Kreuzungen.

Man glaubt allgemein, daß es gar nicht besser geht. Die Kreuzungszahl von C_m x C_n würde also n(m–2) betragen. Aber diese (m,n)-Vermutung ist bisher nicht bewiesen. Man weiß, daß sie für 3 ­ m ­ 6 und für m = n = 7 zutrifft. Der kleinste unklare Fall ist C₇ x C₈. Für diesen Graphen wird die Kreuzungszahl 40 vermutet. Finden Sie eine Möglichkeit, den Graphen mit 39 oder weniger Kreuzungen zu zeichnen? Dann wäre die (m,n)-Vermutung widerlegt. Es klingt vielleicht unglaublich, aber dieses Problem widersteht seit Jahren den vereinten Kräften aller Mathematiker.

Im Jahre 1997 bewies Gelasio Salazar von der Charleton-Universität in Ottawa (Kanada), daß die Kreuzungszahl von C_m x C_n jedenfalls nicht weit unterhalb von n(m–2) liegen kann. Aber damit bleibt durchaus noch die Möglichkeit offen, daß die (m,n)-Vermutung falsch ist; das würde erklären, warum sie bis dato niemand beweisen konnte. Oder es ist so wie bei Fermats letztem Satz, dem Kepler-Problem oder der Vierfarbenvermutung: Sie ist zwar richtig, aber sehr schwer zu beweisen!


Aus: Spektrum der Wissenschaft 12 / 1999, Seite 128
© Spektrum der Wissenschaft Verlagsgesellschaft mbH