Das Vierfarbenproblem hat mich seit vielen Jahren fasziniert. Ich habe mich inzwischen ausgiebig mit der Materie befasst und stelle hier das Ergebnis meiner Betrachtungen von „Lösungen“, dh. von gültigen Kantendrei- bzw. Flächenvierfärbungen beliebiger Landkarten vor. Ich habe einen graphischen Editor entwickelt, mit dessen Hilfe sich eine Fülle von interessanten Tatsachen und Zusammenhängen anschaulich darstellen lassen. Wegen der mit der Flächenzahl exponentiell steigenden Menge der Färbungsmöglichkeiten wird die Suche nach Lösungen als np-schweres Problem eingestuft. Suchalgorithmen sind weiter unten beschrieben. Man kann das Problem eines Beweises, das einen festen Platz in der modernen Graphentheorie erworben hat, aber auch ohne viel Mathematik in Worte fassen und verständlich darstellen, Mathematik zum Anfassen also.
Schon Leonhard Euler, Altmeister der Graphentheorie versuchte zu beweisen, dass für jede Karte wenigstens eine Lösung existieren müsste.
Ich gehe davon aus, dass alle Landkarten Lösungen haben und werde versuchen nachzuweisen, dass es keine solche ohne eine einzige Lösung geben kann. Siehe weiter unten unter "Beweis".
Appel und Haken haben einen „Computerbeweis“ vorgelegt, der inzwischen von der Fachwelt akzeptiert wird. Es bleibt aber ein gewisses Unbehagen, denn ein einfacher, klassischer Beweis „mit Papier und Bleistift“ steht nach wie vor aus. Die im Folgende beschriebenen Erkenntnisse und daraus abgeleiteten Schlussfolgerungen habe ich selbst erarbeitet. Ausser einigen allgemein bekannten und bewiesenen Formeln und Sätzen habe ich keine fremden Darstellungen benützt und deshalb auf Quellenangaben verzichtet.
Jede Landkarte kann durch Strecken der Grenzabschnitte in einen ebenen Graphen überführt werden. Natürliche Landkarten haben bis auf ganz wenige Ausnahmen nur Dreiländerecken und sind dann drei-regulär. Sie enthalten nur Dreier-Ecken, und sind per Definition immer eben und kreuzungsfrei. Jeder ebene Graph kann drei-regulär gemacht werden, indem alle Ecken, an denen mehr als 3 Kanten zusammentreffen durch "Miniflächen" ersetzt werden. Anschaulicher: Man denke sich die Ecken des isomorphen Polyeders, an denen mehr als drei Kanten zusammentreffen abgeschnitten. Die so entstandenen Schnittflächen, die jetzt dreiregulär sind, werden nach erfolgreicher Färbung wieder zu einer Ecke zusammengezogen. Dann treffen zwar gleiche Flächenfarben an Ecken, aber nicht an Kanten zusammen.
Folgende Synonyme werden nebeneinander verwendet:
Man kann eine reale Landkarte falten, zusammenrollen, verzerren oder zusammenknüllen, ohne dass die Relation ihrer Elemente untereinander verändert wird, vorausgesetzt sie hat danach keine Löcher oder Risse. Das Gleiche gilt für die Projektion eines beliebigen Graphen g. Dieser enthalte nur n-Ecke mit einer Kantenzahl k≥4. Nullecke (Enklaven), Zweiecke (Doppelkanten) und Dreiecke kommen zwar in realen Landkarten vor, sind aber ohne Belang für die spätere Färbung und werden im Folgenden ausgeschlossen. Stellt man sich den Graphen als ein aus dehnbaren Gummifäden geknüpftes Netz vor, so kann man dieses in der Ebene aufspannen, indem man die Knoten einer Masche auf einem Kreis, z.B. einem runden Tisch an dessen Rand in etwa gleichen Abständen befestigt. Alle übrigen Knoten werden sich so auf der Tischplatte anordnen, dass Kräftegleichgewicht an ihren drei dort zusammentreffenden Fäden herrscht. Das Netz kann auch durch jede seiner Maschen kreuzungsfrei über eine Kugel gespannt werden. Wenn man die Kanten, die jetzt Kreisbögen sind, durch Geraden ersetzt, entsteht ein räumliches Stabwerk, das durch Verschieben der Ecken auf der Kugeloberfläche in einen isomorphen, konvexen Polyeder mit ebenen Flächen transformiert werden kann. Dabei ergeben sich genau so viele isomorphe Sichten auf den selben Graphen, wie das Netz Maschen hat. Das n-Eck, durch das die Projektion erfolgte, wird in der Ebene zur den Graphen umgebenden, ins Unendliche reichenden Fläche und muss in den folgenden Formeln immer mitgezählt werden. Eine Landkarte oder deren korrespondierender Graph G werden nicht als statische Objekte sondern das Ergebnis vielfältiger topologischer Prozesse betrachtet.
Der Eulersche Polyedersatz:
k–e = f–2
Mit k=Kantenzahl, e=Eckenzahl und f=Flächenzahl wird:
f'= (f-2) → e = 2f'; k = 3f' → f' : e : k = 1 : 2 : 3
Die Flächenzahl f ist das Mass für die „Grösse“ eines Graphen.
Genesis eines dreiregulären Graphen
Die Entstehung eines solchen Graphen lässt sich am besten auf der Kugeloberfläche veranschaulichen. Schliesslich beziehen sich ja alle Landkarten auf die Erdoberfläche. Am Anfang steht deren gesamte, ungeteilte Oberfläche: f=0; k=0; e=0 mit f=Anzahl der n-Ecke dieses Graphen. Im ersten Schritt wird diese durch eine geschlossene Linie zweigeteilt: f=2 (die "Urflächen"); k=0; e=0. Durch Einfügen einer Kante in eine der beiden Kugelschalen entsteht der erste dreireguläre "Urgraph, das Drei-Zweieck" mit f'=f-2 → f'=1; e=2: k=3. Im nächsten und allen folgenden Schritten wird jeweils eine Fläche durch Einziehen einer weiteren Kante zweigeteilt: f'=2; e=4: k=6 usw. Dadurch verschwinden bzw. entstehen bei jedem Schritt zusätzlich eine Fläche, zwei Ecken und drei Kanten: die entfernte bzw. eingefügte plus die beiden durch Teilung der Anschlusskanten entstandenen. Der Eulersche Polyedersatz ist also in allen Schritten erfüllt.
Lösungen
Eine Lösung λi auf g sei eine Kanten-3-Färbung, bei der alle Kanten gefärbt sind und an keiner Ecke Kanten gleicher Farbe zusammentreffen. Die Abbildung einer Kanten-Dreifärbung mit den Farben {x,y,z} auf ihre äquivalente Flächen-Vierfärbung mit den Farben {a,b,c,d} ist umkehrbar und wird durch das Tetraederschema definiert:
Zu lesen:
Kantenfarbe x trennt
Flächenfarben a und b oder d und c,
usw. für die Kantenfarben y und z
Teilkreise
Wenn man in einer Lösung auf g, beginnend an einer beliebigen Ecke einem Kantenzug mit abwechselnd zwei der drei Kantenfarben, z.B. {x,y} folgt, so werden im Ausnahmefall alle Ecken in einem einzigen Zug durchlaufen und man erhält den klassischen Hamiltonkreis, (z. B. Im nächsten Bild der Teilgraph g-x). In der Regel schliessen sich aber bereits Teilkreise, bevor alle Kanten einmal durchlaufen sind. Man beginnt dann erneut an einer noch freien Ecke, bis alle Kanten einmal durchlaufen sind. Die Teilkreise haben alle eine gerade Kanten- und Eckenzahl und bilden zusammen eine Gruppe mit 3 Elementen.
Reduktion und Expansion
Jeder dreireguläre Graph g kann durch schrittweises Entfernen einer beliebigen Kante auf die Projektion des Tetraeders oder eine andere Grundform mit wenigen Flächen reduziert werden. Umgekehrt kann g durch Einfügen von Kanten innerhalb seiner Flächen "von Kante zu Kante" expandiert werden. Dadurch verschwinden bzw. entstehen bei jedem Schritt jeweils eine Fläche, zwei Ecken und drei Kanten: die entfernte bzw. eingefügte plus die beiden durch Teilung der Anschlusskanten entstandenen. Es gibt keine anderen Möglichkeiten, Kanten kreuzungsfrei in g einzufügen.
10.Okt.2020, Neustadt/Weinstrasse
Klaus Klose
Keine Kommentare:
Kommentar veröffentlichen