Dieser Text entstand aus einer spontanen Idee heraus und ist eher als
Skizze eines einfachen naiven Gedankengangs als als mathematische
Abhandlung zu verstehen. Wer den Text ganz gelesen hat, darf mir gern
Kommentare schicken.

**********************************************

Gedanken zum 4-Farben-Problem

Ausgehend von einer nicht unterteilten Fläche wird eine topologische
Aufteilung konstruiert durch eine Abfolge der folgende Schritte.


A) Einbettung

eine neue Teilfläche ist vollständig von einer vorhandenen umgeben. Die
ursprüngliche Fläche hat eine bestimmte Farbe; die neue Fläche kann
unter den übrigen 3 beliebig wählen. Es werden keine neue Knoten
gebildet und es gehen keine verloren.


B) Anlagerung an eine Grenze

eine neue Teilfläche lagert sich an die Grenze zwischen 2 Teilgebiete
ein. Die beiden ursprünglichen Flächen haben 2 Farben. Die neue Fläche
kann unter den anderen beiden wählen. Es entstehen 2 neue Knoten und es
gehen keine verloren. (Sonderfall: Anlagerung an die äußere Grenze: es
kann unter 3 Farben gewählt werden)


C) Anlagerung an einen Knoten

eine neue Teilfläche lagert sich an Stelle eines Knotens zwischen 3
Teilgebiete ein. Die 3 ursprünglichen Flächen belegen 3 Farben, damit
ist die Farbe der neuen Fläche festgelegt. Es entstehen 3 neue Knoten
und es geht einer verloren. (Sonderfall: Anlagerung an einen Knoten auf
der Außengrenze: es kann unter 2 Farben gwählt werden)


Eine Fläche, die sich so konstruieren läßt, ist also durch 4 Farben nach
den Regeln des 4-Farb-Problems lösbar.


Zu zeigen wäre, daß sich jede Topologie einer solchen Fläche durch eine
Abfolge der Schritte A, B und C aus einer nicht unterteilten Fläche
erzeugen läßt. Dann wäre das 4-Farben-Problem auf einfache Weise gelöst.
Alternativ könnten weitere Schritte erdacht werden, für die ebenfalls
unmittelbar einsichtig sein sollte, daß sie allgemeingültig lösbar sind.
Alternativ könnte durch diese Schritte eine bestimmte Klasse von
Topologien definiert werden, für die das Vier-Farben-Problem einfach
beweisbar ist.


Beschreibung des Hintergrunds

eine abgeschlossene Fläche ist vollständig durch Teilflächen überdeckt.
Diese Teilflächen haben gemeinsame Strecken als Grenzen. Dabei
entstehende Knoten haben 3 "Ausgänge". Freie Flächen exitieren nicht;
bzw werden als eigene Teilfläche definiert, Überlappungen existieren
nicht. (Beispiel aus der Praxis: Bundesländergrenzen Deutschlands)


Behauptung

die Teilflächen können jeweils Ein-farbig mit Hilfe von insgesamt 4
Farben gefärbt werden, so daß auf der gesamten Fläche keine 2
Teilflächen mit gleicher Farbe eine gemeinsame Grenze haben.

Der Beweis wurde erbracht, in dem alle möglichen Konstellationen
durch "brut force number crunshing" per Computer untersucht wurden.

Die Idee zu diesem Ansatz kam bei der Lektüre von
Simon Singh: Fermats letzter Satz; dtv

###############

bis hier ist die Idee gerade einen Tag in meinem Kopf gewesen und etwa
12h schriftlich festgehalten.


weitere Gedankengänge

die Vorwärts-Konstruktion ist auch nicht viel einfacher als das direkte
Beweisen einer "fertigen" Topologie. Ein mehr versprechender Ansatz ist
es die Konstruktion umzukehren; also die Konstruktionsvorschriften
umzukehren und dazu zu benutzen eine gegebene Konstruktion auf eine
nicht unterteilte Fläche zurückzuführen:

A) eine Teilfläche, die vollständig von einer anderen umgeben ist, kann
entfernt werden.

B) eine Teilfläche, die nur 2 Nachbarn hat, kann entfernt werden.

C) eine Teilfläche, die nur 3 Nachbarn hat, kann entfernt werden.

Es gibt Topologien, die ausschließlich aus Teilfeldern bestehen, die 4
und mehr Nachbarn haben, z.B. 3 konzentrische Kreise, von denen die
beiden äußeren radial geviertelt sind (die  Radien natürlich etwas
gegeneinander verdreht). Diese lassen sich also nicht reduzieren.
Entweder müssen neue Vorschriften gefunden werden, die solche Topolgien
erzeugen können und gleichzeitig allgemein lösbar sind. Oder aber ist
hier die Grenze dieses Ansatzes erreicht und mit diesem Ansatz wird
lediglich ein Unterproblem des 4-Farben-Problems gelöst. Immerhin ist
es eine Lösung, die die Anzahl der Felder nicht einschränkt :-)

to be continued...

(C) 2000-10-14  Emil Obermayr, Braunschweig, Germany
nobs@tigress.com


##############################################################

2001-11-04 

durch erste Gehversuche in Prolog komme ich mal wieder zu diesem alten
Problem zurück:

formuliert man das flächige Problem in ein Graphen-Problem um, erhält
man eine neue Sichtweise:

In einer 2-dimensionalen, Kreuzungs-freien Anordnung von Kanten kann
man jedem Knoten eine von 4 Farben zuordnen, so daß keine Kante 2 Knoten
mit gleicher Farbe verbindet.

Oder anders herum: in einer beliebigen Anordnung von Knoten sind alle
Kreuzungs-freien Kanten erlaubt.

So ein Graph könnte als Inverses einer Karte bezeichnet werden. Dabei
ensteht wieder eine Karte, bei der alle Flächen bei vollständiger
Ausnutzung aller möglichen Verbindungen genau 3 Nachbarn haben.

(Irgendwie erinnert mich das an Festkörperphysik, Kristalle, reziproke
Räume, Fermiflächen... hilft einem das weiter?)

Andererseits kann man in einer gegebenen Anordnung auch "verbotene"
Kanten definieren (welche mit Kreuzung, also solche, die sich nicht als
Karte darstellen lassen) und man findet trotzdem noch eine gültige
Färbung. Trivialerweise geht das natürlich bei Knoten die in einer
gegebenen Färbung eh schon unterschiedliche Farben haben. Interessant
wird es, wenn man verbotenerweise 2 Knoten verbindet, die die gleiche
Farbe haben und dann den Graphen betrachtet. Entweder man findet eine
neue Lösung oder man hat einen "echt" verbotenen Graphen gefunden. Nach
welchen Regeln lassen sich Graphen durch Umordnung der Knoten
Kreuzungs-frei darstellen? Lassen sich alle färb-baren Graphen auch
Knoten-frei darstellen?