06.03.2009 · Mathematische Probleme, die einfach nach Durchprobieren von verschiedenen Varianten klingen, brauchen raffinierte Methoden, um das Durchzählen dieser Varianten auch bewerkstelligen zu können. Jetzt wurde eine besonders effizientes Verfahren dafür entwickelt.
Von Heinrich Hemme
© Max-Planck-Institut für Dynamik und Selbstorganisation
Auf wie viele Weisen lassen sich die Länder einer Landkarte färben, wenn niemals zwei gleichfarbige Länder aneinanderstoßen dürfen? Wie viele verschiedene Sudokus gibt es? Wie viele Möglichkeiten hat man, acht Damen so auf ein Schachbrett zu stellen, dass sie sich nicht gegenseitig schlagen können? Wie viele Grundzustände kann ein Festkörper annehmen?
Zählen ist eine hohe Kunst, wenn es um Fragen dieser Art geht. Marc Timme, Frank van Bussel und Denny Fliegner vom Max-Planck-Institut für Dynamik und Selbstorganisation in Göttingen und Sebastian Stolzenberg von der Cornell University in Ithaca (New York) haben eine neue Methode entwickelt, mit der sie solche Zählungen wesentlich schneller bewältigen können als mit allen bisherigen Verfahren.
Vom Zählen zum Graphen
Um Kombinationen zu zählen, vereinfachen Mathematiker Landkarten, Sudokus, Schachbretter, Festkörper oder was immer sie gerade untersuchen zu Mustern aus Punkten, die durch Linien miteinander verbunden sind. Solche Muster nennen die Mathematiker Graphen, und sie bezeichnen die Punkte als Knoten und die Linien als Kanten. So kann man beispielsweise die Bundesländer Deutschlands durch einen Graphen mit sechzehn Knoten ersetzen, die jeweils paarweise durch eine Kante miteinander verbunden sind, wenn die entsprechenden Länder eine gemeinsame Grenze haben.
© MPI für Dynamik und Selbstorganisation
Zwei von 1152 verschiedenen Möglichkeiten, die Knotenpunkte desselben Netzes mit vier Farben einzufärben. Knotenpunkte, die durch eine Linie verbunden sind, dürfen nicht dieselbe Farbe haben.
Die Frage, auf wie viele Weisen man die Länder mit vier Farben so färben kann, dass nirgendwo zwei gleichfarbige aneinanderstoßen, ist nun gleichwertig mit folgender Frage: Wie viele Möglichkeiten gibt es, die Knoten des Graphen mit vier Farben so zu färben, dass jede Kante nur verschiedenfarbige Knoten miteinander verbindet?
Mit Durchprobieren sind Rechner schnell überfordert
Unabhängig von dieser speziellen Frage suchen die Wissenschaftler nach Verfahren, mit denen sich das folgende allgemeine Problem lösen lässt: Auf wie viele verschiedene Weisen kann man einen beliebigen Graphen mit einer vorgegebenen Zahl von Farben in erlaubter Weise färben? Wobei unter einer erlaubten Färbung verstanden wird, dass die Kanten jeweils nur zwei verschiedenfarbige Knoten verbinden. Welche Bedeutung in einem konkreten Fall die Farben tatsächlich haben, kann recht unterschiedlich sein. Bei der Landkarte sind sie auch wirklich Farben, beim Sudoku stehen sie für Ziffern, und beim Damenproblem sagen sie, ob ein Feld besetzt oder unbesetzt ist.
Das einfachste Verfahren wäre es nun, mit einem Computer für einen Graphen sämtliche Farbkombinationen systematisch durchzuprobieren. Doch das wären schon bei nur vier Farben und den sechzehn Knoten der Deutschlandkarte über vier Milliarden Kombinationen, die überprüft werden müssten. Erhöht man die Zahl der Knoten und die der Farben, kommt man ganz schnell an eine Grenze, oberhalb derer auch die größten und schnellsten Computer der Welt das Problem auf diese Weise in einer akzeptablen Zeit nicht mehr lösen können.
Schritt für Schritt . . .
Anstatt direkt die erlaubten Färbungen zu zählen, geht man bei dem bisher meistens benutzten Verfahren einen Umweg, der dennoch schneller zum Ziel führt. Greift man sich zwei Knoten A und B des Graphen heraus, die durch eine Kante verbunden sind, so müssen sie bei allen erlaubten Färbungen des Graphen natürlich verschiedenfarbig sein. Die Anzahl der erlaubten Färbungen erhält man nun dadurch, dass man im ersten Schritt alle Färbungen zählt, bei denen A und B entweder verschiedenfarbig oder gleichfarbig sind, und anschließend im zweiten Schritt die Färbungen wieder abzieht, bei denen A und B gleichfarbig sind.
Da es bei dem ersten Schritt keine Rolle spielt, ob A und B gleich- oder verschiedenfarbig sind, muss man in dem Graphen die Kante zwischen den beiden Knoten löschen, was sich aber nicht auf die Zählung auswirkt. Beim zweiten Schritt sind A und B gleichfarbig, darum kann man diese beiden Knoten zu einem einzigen zusammenziehen und die Kante verschwinden lassen, ohne dass dies einen Einfluss auf die Zählung hat. Bei beiden Teilschritten wird also der Originalgraph durch zwei neue Graphen ersetzt, die eine Kante weniger haben und deshalb einfacher zu berechnen sind.
. . . den Kanten und Knoten entlang
In dem bisherigen Standardalgorithmus wird dieses Verfahren wiederholt angewandt: Man startet mit einem Graphen, wählt eine Kante und erzeugt damit zwei neue Graphen, die beide diese Kante weniger haben. Für die beiden neuen Graphen wiederholt man das Verfahren und erzeugt dadurch wieder je zwei neue Graphen, also insgesamt vier neue Graphen, die alle um jeweils zwei Kanten kleiner sind als der ursprüngliche Graph. Dieses Verfahren wird so lange wiederholt, bis schließlich nur noch Graphen übrig bleiben, die keine Kanten mehr besitzen und deren Knoten man unabhängig voneinander färben kann. Die Anzahl der Färbungen dieser einfachen Graphen ist das Produkt der Anzahl der Färbungen der einzelnen nicht mehr verbundenen Knoten, woraus man nun leicht die Gesamtzahl der Färbungen des Originalgraphen berechnen kann.
Dieser Algorithmus funktioniert zwar im Prinzip, hat aber den Nachteil, dass aus einem Graphen mit n Kanten bis zu 2n neue Graphen erzeugt werden, was außerordentlich viel Rechenzeit und Speicherplatz erfordert. Bei einem Schachbrettgraph mit 64 Knoten und 112 Kanten würden bis zu fünf Quintilliarden neue Graphen erzeugt und berechnet werden. Dafür würden auch modernste Computer eine Zeit benötigen, die etwa hundertmal so lang ist wie das Alter des Universums.
Von mehreren Milliarden Jahren auf 0,07 Sekunden
Das neue Verfahren von Timme, van Bussel, Fliegner und Stolzenberg geht im Prinzip den umgekehrten Weg. Bei ihm hangelt sich der Computer von Knoten zu Knoten durch den Graphen. Als sei er kurzsichtig, schaut er stets nur auf den nächsten Knoten. Anders als beim Standardverfahren hat er also nicht den gesamten Graphen im Blick. Am ersten Knoten etwa kann er zwar noch keine mögliche Farbe endgültig auswählen, denn dafür müsste er wissen, wie alle anderen Knoten miteinander verbunden sind. Aber anstatt diese Frage sofort zu klären, merkt sich der Computer für den ersten Knoten eine Formel, die diese Unwägbarkeit als unbekannte Größe enthält. Beim Weg durch den Graphen werden nach und nach alle Verbindungen sichtbar, und die Unbekannten entfallen. Ist der Computer schließlich am letzten Knoten angekommen, kennt er den gesamten Graphen.
Mit dem neuen Verfahren der Wissenschaftler aus Göttingen und Ithaca lassen sich jetzt Probleme aus der Mathematik und der Physik lösen, die mit den bisherigen Methoden praktisch unlösbar waren. Die Rechenzeit für den Schachbrettgraphen konnte übrigens von mehreren Milliarden Jahren auf nur 0,07 Sekunden gesenkt werden.
