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?