Landkarte

Ein neuer Algorithmus färbt jede Landkarte viel schneller mit nur vier Farben

 Dennis Lenz

Ein neuer Algorithmus färbt jede Landkarte viel schneller mit nur vier Farben
Die Karte färbt die rund 210 Gemeinden Sloweniens mit nur vier Farben, ohne dass zwei Nachbargemeinden dieselbe Farbe tragen. Sie veranschaulicht den Vierfarbensatz und stammt nicht aus der Studie. (Foto: © Romanm, Wikimedia Commons)

Vier Farben reichen für jede Landkarte im mathematischen Modell, damit Nachbargebiete entlang gemeinsamer Grenzen verschieden aussehen. Ein internationales Team kann solche Färbungen nun mit erheblich günstiger wachsendem Rechenaufwand bestimmen. Auf ein ausgezeichnetes Verfahren mit nahezu linearer Laufzeit folgt ein Preprint, der sogar eine optimale lineare Laufzeit beschreibt.

Entwickelt haben die Verfahren Mikkel Thorup von der Universität Kopenhagen, Carsten Thomassen von der Technischen Universität Dänemarks und vier Kollegen. Beteiligt sind Ken-ichi Kawarabayashi vom National Institute of Informatics, Bojan Mohar von der Simon Fraser University sowie Yuta Inoue und Atsuyuki Miyashita von der Universität Tokio. Gemeinsam untersuchten sie, welche kleinen Strukturen in einer Landkarte das Färben erleichtern. Ihr erster Beitrag erhielt den Best Paper Award der Informatikkonferenz FOCS und liefert den ersten großen algorithmischen Fortschritt seit rund drei Jahrzehnten. Die Universität Kopenhagen beschreibt ihn in ihrer Mitteilung (https://via.ritzau.dk/pressemeddelelse/15284557/breakthrough-danish-researchers-find-efficient-solution-to-famous-174-year-old-mathematical-headache?lang=en&publisherId=13561237).

Neu ist die Geschwindigkeit, mit der ein Computer eine gültige Farbverteilung finden kann; deren grundsätzliche Existenz war schon bewiesen. Für die praktische Berechnung hilft diese Gewissheit allein allerdings wenig, wenn der Rechenaufwand mit jeder Vergrößerung stark zunimmt. Während bei offenen mathematischen Rätseln zunächst ein allgemeiner Beweis gesucht wird, steht hier ein anderer Arbeitsschritt im Mittelpunkt. Einen Überblick über weiterhin ungelöste Grundfragen bietet der Hintergrund zu den sechs ungelösten Rätseln der Mathematik.

Wie eine Landkarte zu einem Netz wird

Für dieses Problem der Mathematik zählen ausschließlich Nachbarschaften, nicht die tatsächlichen Flächen, Einwohnerzahlen oder Umrisse der dargestellten Gebiete. Jedes zusammenhängende Gebiet wird durch einen Punkt ersetzt, den Mathematiker als Knoten bezeichnen. Eine Verbindung zwischen zwei Knoten zeigt, dass ihre Gebiete ein gemeinsames Stück Grenze besitzen. Berühren sich Regionen lediglich an einer Ecke, müssen ihre Farben dagegen nicht verschieden sein. Aus gezackten Küsten und geschwungenen Grenzlinien entsteht dadurch ein übersichtlicheres Netz, dessen Form für den Algorithmus entscheidend ist.

Solche Netze heißen planare Graphen, wenn sie sich ohne überkreuzende Verbindungen auf einer Ebene zeichnen lassen. Der Vierfarbensatz garantiert für diese Graphen eine Färbung, bei der verbundene Knoten unterschiedliche Farben erhalten. Zusammenhängende Regionen sind dabei eine Voraussetzung der üblichen Kartenfassung. Soll ein Land einschließlich weit entfernter Exklaven zwingend dieselbe Farbe bekommen, kommen zusätzliche Bedingungen hinzu. Auch vorab festgelegte Farben für bestimmte Gebiete gehören nicht automatisch zur Garantie. Mathematisch geht es also um klar definierte Nachbarschaften, nicht um sämtliche Gestaltungswünsche einer politischen Weltkarte.

Ein einfacher Gedanke beschäftigte Generationen

Ausgangspunkt war eine Beobachtung des Engländers Francis Guthrie, der 1852 eine Karte englischer Grafschaften betrachtete. Beim Einfärben genügten ihm wenige Farben, und daraus entstand die Vermutung, dass dies für jede entsprechende Karte funktioniert. Alfred Kempe legte 1879 einen vermeintlichen Beweis vor, in dem später ein Fehler entdeckt wurde. Kenneth Appel und Wolfgang Haken gelangen 1976 schließlich der erste anerkannte Beweis. Dabei prüften Computer zahlreiche mögliche Konfigurationen, weshalb die Nachvollziehbarkeit des Ergebnisses damals intensive Diskussionen auslöste.

Entscheidend war die Verbindung eines allgemeinen mathematischen Arguments mit einer endlichen Menge überprüfbarer Einzelfälle. Ein Computer kann zwar beliebig viele Beispielkarten testen, doch daraus entsteht noch keine Garantie für jede denkbare Karte. Erst ein Beweis, der alle möglichen Gegenbeispiele ausschließt, schließt diese Lücke. Vergleichbare Fragen zur Überprüfung umfangreicher Computerrechnungen spielten später bei der Bestätigung der Kugelstapel-Theorie eine Rolle. Auch die neue Arbeit zum Vierfarbensatz nutzt rechnergestützte Fallprüfungen; ihr Fortschritt betrifft insbesondere die daraus gewonnene Rechenvorschrift.

Viele kleine Muster erleichtern die große Aufgabe

Im Zentrum stehen sogenannte reduzierbare Konfigurationen, also kleine Teile eines Netzes, die sich für eine Vereinfachung eignen. Anschaulich wird ein passendes Stück zunächst herausgenommen, damit ein kleineres Problem übrig bleibt. Nach dessen Färbung lässt sich das entfernte Stück wieder einsetzen und korrekt einfärben, gegebenenfalls nach geeigneten Farbwechseln. Ältere Beweise garantierten eine passende Stelle für diesen Vorgang. Das neue Ergebnis sichert eine mit der Netzgröße wachsende Zahl voneinander getrennter solcher Stellen oder geeigneter kurzer, trennender Zyklen.

Dadurch kann das Verfahren die Aufgabe jeweils um einen festen Anteil verkleinern, statt nur um einen kleinen Betrag. Besonders hilfreich sind große, gleichförmig aufgebaute Bereiche, die die Autoren als „flach“ beschreiben. Gemeint ist eine Eigenschaft des Nachbarschaftsnetzes, die sich aus den Verbindungen der Knoten ergibt. Berge, Täler oder die Höhenlage einer Landschaft spielen dabei keine Rolle. Für ihren Beweis verwenden die Mathematiker einen Katalog von 8.202 reduzierbaren Konfigurationen, dessen Eigenschaften rechnerisch geprüft wurden. Die vollständige Untersuchung erläutert sowohl diese Struktur als auch den Färbungsalgorithmus (https://arxiv.org/abs/2603.24880).

Wie der Aufwand mit der Kartengröße wächst

Den bisherigen Maßstab lieferten Neil Robertson, Daniel Sanders, Paul Seymour und Robin Thomas mit Arbeiten von 1996 und 1997. Ihr Algorithmus benötigte quadratische Zeit, geschrieben als O(n²), wobei n die Anzahl der Knoten bezeichnet. Die ausgezeichnete neue Arbeit senkt diese obere Laufzeitschranke auf O(n log n). Damit wächst der Aufwand nur noch um einen zusätzlichen logarithmischen Faktor stärker als die Größe der Eingabe. Für immer größere Netze verändert das die Skalierung grundlegend.

Im Folgepreprint erreicht das Team schließlich O(n), also lineare Zeit. Thomassen erläutert den Unterschied anhand einer Verzehnfachung: Enthält eine Karte zehnmal so viele Regionen, wächst der Aufwand ungefähr auf das Zehnfache. Beim quadratischen Verfahren entspricht dieselbe Vergrößerung ungefähr dem Hundertfachen. Diese Gegenüberstellung beschreibt das Wachstum des Rechenaufwands, nicht gemessene Sekunden auf einem bestimmten Computer. Die tatsächliche Laufzeit hängt außerdem von der Umsetzung und den konstanten Faktoren ab. Gerade für kleine Karten ergibt sich aus den Formeln deshalb kein pauschaler Geschwindigkeitsgewinn.

Gezielte Farbwechsel beseitigen den letzten Engpass

Für den Schritt von nahezu linearer zu linearer Zeit musste das Team die Verarbeitung bereits gefärbter Bereiche verbessern. Beim Wiedereinsetzen entfernter Stücke müssen teilweise Farben entlang zusammenhängender Ketten getauscht werden. Beispielsweise wechseln in einer passenden rot-blauen Komponente sämtliche roten Knoten zu Blau und alle blauen zu Rot. Weil die gesamte passende Komponente erfasst wird, bleibt die gültige Nachbarschaftsfärbung erhalten. Solche Umfärbungen heißen Kempe-Änderungen und können große Teile des Netzes betreffen, wodurch ihre wiederholte Bearbeitung aufwendig wird.

Neue Datenstrukturen bündeln die erforderlichen Entscheidungen und Farbwechsel so, dass ihr gesamter Aufwand linear bleibt. Der Algorithmus arbeitet deterministisch, benötigt für seine Laufzeitgarantie also kein glückliches Zufallsergebnis. Optimal ist die Größenordnung im verwendeten Rechenmodell, weil schon die vollständige Ausgabe jeder Region eine Farbe zuordnen muss. Diese Weiterentwicklung liegt als Preprint vor und ist von der ausgezeichneten Konferenzarbeit zu unterscheiden. Das Manuskript beschreibt die nötige Vorbereitung und die gemeinsame Verarbeitung der Farbwechsel ausführlich (https://arxiv.org/abs/2610.39753).

Auf Flächen mit Löchern gelten andere Bedingungen

Über Karten hinaus interessiert die Mathematiker, welche Strukturen auf komplizierteren Oberflächen bestehen bleiben. Thorup nennt einen Schwimmring und ein Stück Emmentaler als anschauliche Beispiele für Flächen mit Löchern. Auf solchen Oberflächen können Netze Nachbarschaften besitzen, die sich in der Ebene nicht mehr kreuzungsfrei darstellen lassen. Deshalb gilt dort keine allgemeine Garantie, dass dieselbe Farbanzahl ausreicht. Übertragbar erscheint vielmehr die Suche nach vielen lokalen Stellen, an denen sich ein großes Färbungsproblem gezielt vereinfachen lässt.

Als weiterführendes Ziel beschreiben die Autoren eine genauere Trennung zwischen lokalen Mustern und Schwierigkeiten durch die Form der Oberfläche. Für eine fest vorgegebene Oberfläche wollen sie untersuchen, ob das Entfernen einer begrenzten Knotenmenge eine Vierfärbung ermöglicht. Deren erforderliche Größe soll von der Oberfläche abhängen, statt mit jedem zusätzlichen Knoten des gesamten Netzes zu wachsen. Dieses weiterführende Ergebnis kündigen die Mathematiker als Gegenstand einer geplanten weiteren Arbeit an.

Universität Kopenhagen, Breakthrough: Danish researchers find efficient solution to famous 174-year-old mathematical headache.

Inoue, Kawarabayashi, Miyashita, Mohar, Thomassen und Thorup, The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring; doi:10.48550/arXiv.2603.24880

Inoue, Kawarabayashi, Miyashita, Mohar, Thomassen und Thorup, Four-Coloring Planar Graphs in Linear Time, Preprint; doi:10.48550/arXiv.2610.39753

Mit KI-Unterstützung erstellt

Keine Neuigkeit aus der Forschung verpassen

Wählen Sie Forschung und Wissen bei Google als bevorzugte Quelle oder folgen Sie uns per RSS-Feed.

 Bevorzugte Quelle bei Google  RSS-Feed
Spannend & Interessant
VGWortpixel