von OlbersD - 15.08.12 16:39 yigg.de

von OlbersD - 15.08.12 17:49 Wenn die Grenzen verschoben werden, so dass einige Länder mehr Nachbarn erhalten verringert sich zwangsläufig für die angrenzenden Länder die Zahl der Nachbarn. Bei einem sich regelmäßig unendlich wiederholenden Muster ist die Zahl der Nachbarn im Mittel immer sechs. Bei endlichen Karten ist die miitlere Zahl geringer. Es gibt daher in einer realen, also endlichen Landkarte immer mindestens ein Land mit nur fünf Nachbarn. Damit ist zunächst klar, dass sechs Farben immer ausreichen.

von OlbersD - 15.08.12 17:55 Wenn sechs Farben zur Verfügung stehen, bleibt in einem Land mit fünf Nachbar eine sechste Farbe übrig. Gäbe es ein Gegenbeispiel, das sieben Farben benötigt, dann kann ein Land mit nur fünf Farben herausgenommen werden. Das kleinste Gegenbeispiel hätte also keine Land mit nur fünf Nachbar. Ein solches Gegenbeispiel kann es jedoch nicht geben.

von OlbersD - 15.08.12 17:59 Jetzt können wir uns überlegen, dass auch fünf Farben immer reichen, weil Länder mit vier Nachbarn nach Umfärbungen nur Nachbarn mit drei verschiedenen Farben haben können.

von OlbersD - 15.08.12 18:01 Dies gilt auch für Länder mit fünf Ländern, so dass diese wiederrum nicht in einem minimalen Gegenbeispiel auftauchen können.

von OlbersD - 15.08.12 18:11 Haben wir ein Land mit vier Nachbarn und den Farben (A;B,C,D). Wir ziegen jetzt, dass wir A in C oder B in D umfärben können. Die übrigen Länder der Landkarte seinen bereits ausgefüllt. Wenn wir Land links in C umfärben, könnte dieses Land Land weitere Nachbarn mit der Farbe C haben. Dann müssten wir diese Länder umfärben. Wir färben dies in A um. Wenn jetzt diese Länder wiederum an Länder mit der Farbe A angrenzen färben wir diese wieder in C um. Wir setzen dieses Spiel solange fort bis es keine Kollisionen mehr gibt. Dies gelingt letzlich immer, spätestens wenn alle Farben (A;C) getauscht sind. Allerdings könnte dann auch das dritte Land von links mit der ursprünglichen Farbe C in A umgefärbt werden müssen. Dann wären es weiterhin vier verschiedene Farben für die vier Länder.

von OlbersD - 15.08.12 18:15 Jetzt können wir aber das zweite Land von B ind D umfärben. Es gibt nämliche eine durchgehende Reihe von Ländern der Färbung (A,C). Es kann dann keine durchgehende Reihe der verschiedenen Farben (B,D) geben von Position 2 nach Poistion 4.

von OlbersD - 15.08.12 18:23 Jetz betrachten wir fünf Länder mit den Färbungen (A,B,C,D,B). Wir versuchen zunächst wieder A in C umzufärben. Dies gelingt nicht, wenn es einen durchgehenden Weg mit den Farben (A,C) gibt. Gelingt es nicht können wir B in D umfärebn. Es bleibt dann aber zunächst die Farbe B in Position 5. Dann versuchen wir A in D umzufärben. Dies gelingt nicht, wenn es einen Weg (A,D) zwischen Position 1 ind Poistion 4 gibt. In diesem Fall können wir aber an Poistion 3 die Farbe C in B umfäreben, weil wir zuvor an Position 2 auf Farbe D gewechselt sind. Daher können wir in jedem Fall mit nur drei Farben auskommen.

von OlbersD - 15.08.12 18:25 Damit sind also die Länder mit fünf Nachbar nicht Bestandteil eines Gegenbeispiels für den Vierfarbensatz. Weil es immer ein Land mit nur fünf Nachbar gibt, ist der Vierfarbensatz beweisen.

von OlbersD - 18.08.12 12:00 Ich glaube die Sache mit dem Land das von fünf Ländern umgeben ist, muss nochmal genauer unter die Lupe genommen werden. Der Rest des Beweises ist wasserdicht. Die Tatsache, dass mindestens ein Land höchstens fünf Nachbar hat wurde zum Beispiel schon mit dem Eulerschen Polyedersatz bewiesen

von OlbersD - 18.08.12 22:21 Die Frage ist, ob durch die Vertauschung (B -> D) an Position 2 eine (B,C) von Position 3 zur Postion 5 hergestellt werden könnte, die es vorhernicht gab. Glaub ich aber nicht, was meint ihr?

von OlbersD - 19.08.12 10:34 Aber es geht einfacher. Wir betrachten dazu ein Land mit sechs Nachbarn und fragen wieder, ob vier verschiedene Farben (1,2,3,4,1,2) erzwungen werden können. Das ist aber unmöglich, weil entweder die '3' in '1' oder aber die '2' in '4' umgefärbt werden können. Das Argument läuft wwieder mit den (1/3)- oder (2/4)-Verbindungswegen, die sich nicht kreuzen können.

von OlbersD - 19.08.12 10:56 Wir wissen jetzt, ein minimales Gegenbeispiel (in der einschlägigen Fachliteratur auch kleinster Verbrecher genannt) darf keine Länder ohne, mit nur einem, zwei, drei, vier oder sechs Nachbarn enthalten.

von OlbersD - 19.08.12 11:02 Wenn wir wieder mit einem Land mit nur fünf Nachbarn beginnen, kann die Zahl der angrenzenden, diese fünf äußeren Länder umringenden Länder nicht kleiner fünf sein, weil sonst eines der fünf Länder überspannt würde und mindestens ein Land nur vier Nachbarn hätte. Ein Land umgeben von fünf die wieder von fünf Ländern umgeben sind kann auch nicht in einem minimalen Verbrecher auftreten, weil die inneren sechs (5 + 1) Länder durch nur eines ersetzt werden könnten. Die inneren fünf Länder werden also von mindestens sechs Ländern umringt.

von OlbersD - 19.08.12 11:05 Bei sechs umliegenden Ländern ist es aber nicht möglich die sechs Dreiländerecken an den inneren fünf Ländern derart zu verteilen, dass es nicht ein Land der inneren fünf sechs oder maxmal vier Nachbarn hat.

von OlbersD - 19.08.12 11:47 Die umliegenden "Kreise" können niemals kleiner werden, wenn im Innern Länder mit nur vier Nachbar vermieden werden sollen. Es dürfen nämlich keine Länder überspannt werden und an jedem inneren Land muss eine Grenze zwischen zwei äußeren Ländern liegen. Bei nicht kleiner werdenden Kreisen kann aber immer eine Lösung mit nur drei verschiedenen Farben pro Kreis gefunden werden.

von OlbersD - 19.08.12 11:48 Der kleinste Verbrecher wird also unendlich groß und der Vierfarbensatz ist damit bewiesen. behaupte ich.

von OlbersD - 19.08.12 12:48 Der Algorithmus zur Färbung mit nur drei Farben je umliegenden Kreis von Ländern kann wie folgt beschrieben werden. Es werden, so weit möglich nur zwei Farben verwendet und wenige Ausnahmen (1,2,1,2,3) für die fünf zum Beispiel. Im umliegenden Kreis werden hauptsächlich die anderen Farben (3,4) benutzt und Ausnahmsweise die 1 und im nächsten "Kreis" wieder hauptsächlich (1,2) und möglichst wenige Länder der Farbe 3. Bei immer größer werdenden Kreisen funktioniert dies problemlos. Die Ausnahmen können immer in der Nähe der Ausnahmen im inneren Kreis platziert werden.

von OlbersD - 19.08.12 15:02 Entscheidend für den Beweis ist allein die Tatsache, dass Länder mit weniger als als fünf Nachbarn nach eventueller Umfärbung der Umgebung immer mit einer vierten Farbe, die in der Umgebung nach Umfärbung nicht mehr auftritt, gefärbt werden können. Solche Länder können daher in einem Gegenbeispiel mit minimaler Anzahl an Ländern nicht auftreten.

von OlbersD - 19.08.12 15:04 Im Fall von keinen, einem, zwei oder drei angrenzenden Ländern ist dies offenkundig da höchsten drei Farben in der Umgebung auftreten.

von OlbersD - 19.08.12 15:13 Bei vier Nachbarn sind eventuell Umfärbungen nötig. Wir betrachten vier Länder mit den vier verschiedenen Farben (A,B,C,D) die in dieser Riehenfolge angeordnet seinen. Wir können dann immer C in A umfärben oder D in B. Wenn C in A umgefärbt wird könnte ein oder mehrere angrenzende Länder ebenfalls die Farbe A aufweisen. Dann werden diese ebenfalls umgefärbt. Gibt es dann weitere Kollisionen werden die Farben A und C getauscht, bis keine Kollisionen mehr auftreten. Eventuell muss dann auch das Land ganz links in A umgefärbt werden. Dann gibt es einen Weg, alternierend mit den Farben A und C von Position 1 nach Poistion 3. Dieser kann von einem Weg mit den Farben B und D nicht gekreuzt werden. Daher kann in diesem Fall D in B umgefärbt werden ohne die Farbe an Poistion 2 zu verändern.

von OlbersD - 19.08.12 15:33 Der springende Punkt bei dem Beweis ist also, dass sich in der Ebene eine Verbindungslinie von Position 1 nach Position 3 sowie eine Verbindungsline von Position 2 nach Position 4 schneiden müssen. Dies gilt auch auf der Kugeloberfläche nicht mehr jedoch auf einem Torus.

von OlbersD - 22.08.12 09:24 Algorithmus zur Ausfüllung einer beliebigen Karte: Die Färbung wird am einfachsten, wenn wir mit dem Land mit den meisten Nachbarn (meist das "Wasser" am äußeren Rand) beginnen, weil dann bei einem Problem, vier verschiedene Farben bei einem Land, weniger Umfärbungen nötig sind. Bei gleicher Anzahl der Nachbarn, wird das Land dessen unmittelbare Nachbarn wiederum die meisten Nachbarn besitzen vorgezogen. Als nächstes wird ein Nachbarland des zuerst ausgefüllten Landes ausgefüllt. Wiederum wird das Land mit den meisten Nachbarn vorgezogen. Als drittes Land wird das Land mit den meisten Nachbarn von den Nachbarn des als zweites ausgefüllten Landes ausgefüllt. Die Farben seinen (1,2,3,4). Es wird immer zuerst mit der '1' gefärbt, wenn nicht möglich mit der '2' und so weiter. Gibt es keine freie Farbe mehr, werden die bereist ausgefüllten Länder umgefärbt. Liegen an dem "Problemland" vier verschiedenen Länder in Reihe mit den Farben (1,2,3,4), können wir immer '1' - > '3' oder '2' -> '4' umfärben. (wegen den sich nicht kreuzenden (1/3)- und (2/4)-Wegen).

von OlbersD - 22.08.12 10:34 Der Algorithmus kann noch verbessert werden indem Länder mit 6 Nachbarn wie Länder mit 4,5 Nachbarn bewertet werden, weil bei sechs Nachbarn eine Umfärbung immer leicht möglich ist und sie daher als weniger problematisch eingestuft werden können als Länder mit fünf Nachbarn. Die Idee des Verfahrens ist es nämlich die schwiergen Fälle am Anfang abzuwickeln. Am Ende, wenn es schwierig wird, weil es schon viele gefärbte Nachbarn gibt sollen nur noch die einfachen Fälle bleiben.

von OlbersD - 22.08.12 10:49 Ein weitere Verbesserung des Algorithmus wäre es Länder mit vielen bereits ausgefüllten Farben bevorzugt auszufüllen. Insbesondere Länder mit bereits drei unterschiedlichen Farben in der Nachbarschaft, wo also nur noch eine Farbe verbleibt, kann diese sofort ausgefüllt werden. Wenn bei einem Land keine Farbe mehr verbleibt, versuchen wir sofort dies durch Umfärben zu korrigieren.

von OlbersD - 22.08.12 11:22 @Apache was meinst du? Mit diesem Verfahren kann eine Landkarte auch ohne Computer immer mit nur vier Farben gefüllt werden. Bei meinen Versuchen bin ich sogar immer ohne Umfärbungen ausgekommen. Also, erst einmal zähle ich für jedes Land die angrenzenden Länder. Die Länder mit maximal vier Nachbar und sechs Nachbar lasse ich erst einmal unausgefüllt. Dann fange ich mit bei dem "größten" (meisten Nachbarn) an und färbe dann die Nachbarn, wobei ich wieder mit dem "größten" beginne.

von OlbersD - 23.08.12 17:20 Also ganz sauber ist der Beweis nicht, weil für ein von fünf Läandern umringtes Land diese fünf Nachbarn vier verschiedene Farben haben können. Es ist nicht unmittelbar klar wie durch Tauschen der Farben, eine der vier Farben eliminiert werden kann. Auch bei sechs Ländern ist die Sache nicht astrein, nur bei vier kann immer mindestens eine Farbe weggetauscht werden.

Die Tatsache, dass mindestens ein Land weniger als sechs Nachbarn haben muss, hilft daher auch nicht viel weiter.

Aber kommen wir nochmal auf die ineinander liegenden Kreise zurück. Bis auf eine Ausnahme können die Länder eines Kreises immer abwechselnd rotgrün gefärbt werden. Die Länder des nächsten Kreises bis auf eine Ausnahme schwarzgelb. Die Ausnahme könnten wir zunächst mit einem Fragezeichen Kennzeichnen. Das Fragezeichen kann an jeder Stelle des Kreises platziert werden. Daher können wir annehmen, dass sich die Fragezeichen berühren.

von OlbersD - 23.08.12 17:23 Das Fragezeichen in den rotgrünen Kreisen färben wir dann schwarz, in den schwarzgelben rot. Eventuell müssen wir dann noch weitere Vertauschungen von Schwarzen und Roten durchführen, aber am Ende geht es immer auf.

von OlbersD - 23.08.12 17:27 Wenn die Kreise nicht geschlossen sind, macht die die Färbung höchstens noch einfacher. Daher brauchen wir uns um den Rand der Landkarte keine Gedanken machen. In Gedanken können wir die offen Kreise auch durch zusätzliche erdachte Länder schließen.

von OlbersD - 24.08.12 10:31 Doch - jetzt habe ich den Beweis gefunden: Der Knackpackt war ja zu zeigen, dass bei einem von fünf Ländern umgebenen Land niemals, eventuell nach Umfärbungen, vier Farben für die fünf umliegenden Länder erzwungen werden kann. Der Rest ist einfach. Mindestens ein Land hat maximal fünf Nachbarn (Beweis mit dem Polyedersatz von Euler). Ein minimales Beispiel kann offensichtlich nicht weniger als vier Nachbar haben, weil immer eine vierte Farbe übrig bleibt. Bei vier verschiedenen Farben von einem Land mit nur vier Nachbarn kann immer eine Farbe durch teilweises Tauschen der Farben eliminiert werden. Die umliegenden Länder (A,B,C,D) mit den Farben (1,2,3,4), können umgetauscht werden, entweder die '3' in '1' oder die '2' in '4'. Dies gilt, weil es nicht gleichzeitig eine Kette von Ländern mit den Farben (1,2) von '1' nach '3' und mit den Farben (2,4) von '2' nach '4' geben kann, da eine Kreuzung ausgeschlossen ist.

von OlbersD - 24.08.12 10:37 So und jetzt kommen wir zu dem Problemfall, fünf Länder die eines umringen. Die Färbung sei o.B.d.A. (1,2,3,4,2). Wenn wir die '2' am linken Rand mal vergessen dann können auch wieder die '3' in '1' oder die '4' in '2'. Kann die '3' in die '1' umgefärbt werden sind wir bereits am Ziel, wenn nicht müssen die beiden '2' noch irgendwie auseinander gezogen werden.

von OlbersD - 24.08.12 10:49 Zum Schluss können wir die '2' am Ende in '3' umfärben, weil keine Verbindung (2,3) bestehen kann, sonst hätten wir schon am Anfang die '4' in '1' umfärben können.

von OlbersD - 24.08.12 12:02 Also wir können voraussetzen, am Anfang (1,2,3,4,2) besteht eine (1,3) und eine (1,4) Verbindung, sonst hätten wir kein Problem. Stimmt, die (1,4) könnte durch die erste Umfärbung an Position 4 getrennt werden. Jetzt gehen wir anders vorgehen und nicht das Land an Position 4 umfärben. sondern (wie schon weiter oben vorgeschlagen) die '2' an der zweiten Poistion. Das Problem wäre wieder gelöst, wenn die (1,4)-Verbindung nicht getrennt und damit eine (2,3)-Verbindung hergestellt wird. Es ist jedoch nicht möglich, dass beide Lösungsansätze scheitern.

von OlbersD - 25.08.12 08:59 Tatsächlich funktioniert mindestens einer der beiden Lösungswege. Vor dem Umfärben der Farben '2' und '4'' gibt es keine (2,3)-Verbindung von Poistion 2 nach Postion 5, die einen erfolgreichen Tausch verhindern könnte. Wichtig ist, dass die (1,3)-Verbindung durch das Umfärben der beiden anderen Farben (2,4) nicht betroffen ist. Lücken in der (2,3)-Verbindung können aber nur auf einer Seite der (1,3)-Verbindung durch neue '2'en geschlossen werden. Die Lücken können also nicht vollständig geschlossen werden oder der andere Lösungsansatz führt zum Erfolg.

von OlbersD - 25.08.12 16:02 Hier habe ich noch was zu diesem Problem gefunden.

nrich.maths.org

von OlbersD - 25.08.12 18:51 Ich denke der Beweis stimmt. Etwas komplizierter ist die Sache nur bei den Umfärbungen im Fall von fünf Nachbarn. Der Rest ist wie gesagt hundert Prozent wasserdicht. Es gibt mindest eine Land mit keinem, einem, zwei drei, vier oder fünf.Nachbarn. Solche Länder mit nur wenigen Nachbarn können aber immer, unabhängig von der Färbung des Rests der Karte mit nur vier Farben eingefärbt werden. Damit können solche Länder mit wenigen Nachbarn in einem minimalen Gegenbeispiel nicht vorkommen. Es gibt also kein solches.

von OlbersD - 25.08.12 19:00 Die Methode des partiellen Zweifarbentauschs: Ein Land wird von Farbe_ALT in Farbe_NEU umgefärbt. Danach können Länder mit Farbe_NEU an das umgefärbt Land angrenzen. Dann wird die Farbe_NEU für diese Länder in Farbe_ALT geändert. An diese Länder können dann wieder Länder der gleichen Farbe, der Farbe_ALT angrenzen. Wir müssen dann erneute die Umfärben. Am Ende gibt es aber keine Kollisionen mehr, denn es es definitiv mögliche auf der gesamten Karte die beiden Farben auszutauschen. Ziel ist es aber den Farbtausch nur in einem Teilbereich der Karte durchzuführen.

von OlbersD - 25.08.12 19:07 Wenn die vier Farben A,B,C,D am einem inneren oder äußeren Rand liegen. Können wir versuchen A in C, nicht aber C in A umzufärben. Dies gelingt wenn des keine Kette von Länder, abwechselnd mit den Farben (A,C) von Poistion 1 nach Poistion 3 gibt. Wenn dies nicht gelingt, dann gelingt es für B und D, weil sich (A,C)-Ketten und (B,D)-Ketten nicht kreuzen können. Dies ist ausgeschlossen weil die Paare (A,C) und (B,D) keine gemeinsame Farbe haben.

von OlbersD - 25.08.12 19:31 Fünf Länder: A,B,C,D,B

Falls es keine (A;C)-Kette oder (A;D)-Kette gibt kann die vierte Farbe eliminiert werden. Wir gehen also davon aus, dass es solche Ketten gibt. Es gibt dann keine (B,D)-Kette. Wir versuchen daher 'B' an Poistion 2 in 'D' zufärben und anschließend 'B' an Position 5 in 'C' zu tauschen. Falls dies nichtgelingt, versuchen wir 'D' in 'B' zu tauschen und anschließend.'B' an Poistion 5 in 'C' zu tauschen.

von OlbersD - 25.08.12 19:34 Einer der beiden letzen Ansätze könnte scheitern, weil die (B.C) durch die erste Umfärbung geschlossen wird. Zu Beginn kann sie wegen der (A,C)-Kette nicht existieren.

von OlbersD - 26.08.12 11:01 Einer der beiden letzen Ansätze könnte scheitern, weil die (B.C) durch die erste Umfärbung geschlossen wird. Zu Beginn kann sie wegen der (A,C)-Kette nicht existieren. Die (A,C)-Kette bleibt der ersten Umfärbung (B und D) unverändert. Ursprünglich gibt es keine (B,C)-Kette, sie könnte aber durch den (B,D)-Tausch geschlossen werden. Dies kann jedoch nur gelingen, wenn die fehlenden B-Länder nur auf einer Seite der (A,C)-Kette liegen. Aber einer der Ansätze führt in jedem Fall zum Erfolg, weil der Tausch auf unterschiedlichen Seiten der (A,C)-Kette stattfindet.

von OlbersD - 26.08.12 20:32 Hmmm, ich gebe zu der Beweis bei den Umfärbungen mit fünf Nachbarn ist etwas kompliziert, aber er stimmt, denke ich. Egal, denn es gibt eine einfache Methode zum Färben mit nur vier Farben, die eigentlich immer funktioniert und das Färben auch ohne Computer ermöglicht. Wir beginnen mit einem Land, färben die angrenzenden Länder, anschließend die diese Länder wiederum angrenzenden Länder und so fort. In ersten "Kreis" verwenden wir zwei Farben im nächsten die beiden anderen. Nur bei einer ungeraden Zahl der Länder im Kreis, müssen wir eine Ausnahme machen und ein Land mit einer dritten Farbe färben. im nächsten Kreis müssen wird dann ebenfalls eine dritte Farbe einführen. Aber mit drei Farben pro Kreis kommen wir immer aus. Daher ist auch ein großes Land außen ein Problem. Wir können natürlich versuchen die Sache möglichst einfach zu machen, indem möglich nur Kreise mit gerader Länderzahl auftritt. Am besten beginnen wir mit der Färbung der kleinsten Kreise mit den wenigsten Ländern. Statt mit einem Land können wir auch damit beginnen, eine Anzahl, zum Beispiel den inneren Bundesländern, Hessen, Thüringen und Sachsen-Anhalt, beginnen und dann die umliegenden Bundesländer färben. Auf diese Weise ist die Färbung eigentlich ein Kinderspiel.

von OlbersD - 27.08.12 16:04 Länder:Farben

1:A 2:B 3:C 4:D 5:B

Es gibt Kette-(1:A nach 3:C) und (1:A nach 4:D), sonst Tausch 3:C -> 3:A oder 4:D -> 1:A.

Es kann daher keine Kette (2:B -> 4:D) oder (3:C -> 5:B) geben, weil sich Ketten ohne gemeinsame Farbe nicht kreuzen können.

von OlbersD - 27.08.12 16:11 Erster Ansatz:
Tausch (2:B -> 2:D) anschließend (5:B->5:C)
Zweiter Ansatz:
Tausch (4:D -> 4:B) anschließend (5:B->5:C)

Beim Tausch (2:B -> 2:D) oder (4:D -> 4:B) bleibt die Kette mit den Farben (A,C) unverändert. Einer der beiden Ansätze gelingt, weil nur auf einer Setie der Kette-(A,C) die unvollständige Kette (3:C,5:B) mit fehlenen B-Ländern ergänzt werden kann.

von OlbersD - 27.08.12 18:50 Jetzt gibt es aber im mindestens ein Land mit weniger als sechs Nachbarn. Wenn es ein Gegenbeispiel gäbe, könnten diese Länder mit weniger als sechs Nachbar herausgenommen werden. Es gäbe also ein noch kleineres Gegenbeispiel und ein noch kleineres, ein noch kleineres und so fort. Das ist natürlich absurd und es gibt gar kein Gegenbeispiel.

von OlbersD - 27.08.12 18:52 Also, es geht immer bei vier oder fünf angrenzden Ländern kann durch Umfärben erreicht werden, dass am Ende nur noch drei verschiedene Farben angrenzen und damit eine vierte Farbe übrig bleibt. Bei weniger als vier Grenzländern brauchen wir nicht einmal umfärben.

von OlbersD - 28.08.12 10:20 In einer unendlichen "Mauer", ein Stein links, einer rechts, zwei unten und oben, gibt es immer sechs Nachbarn. Am Rand sind es weiniger. Wird ein Grenzpunkt (Dreiländereck) verschoben bekommt ein Land einen Nachbar mehr, ein anderes einen weniger. Im Mittel bleiben es sechs, mit Rand weniger. Ein Land, mindestens ein Land, hat daher immer weniger als sechs Nachbarn.

von OlbersD - 28.08.12 16:36 Wird am Rand ein neues Land hinzugefügt, erhöht sich die Summe der Grenzländer, summiert über alle Länder der Karte, um maximal sechs, wenn wir den Rahmen als ein Land betrachten. Die Zahl der Grenzen steigt für die Umgebung um eins, ebenso wie für zwei Länder am Rand, wo das neue Land hinzukommt. Zusätzlich erhöht sich die Summe um die drei Länder an die das neue Land angrenzt. Wenn es an mehr als drei Länder angrenzt, wird dafür die Zahl der Grenzländer des Rahmenlandes in gleichem Maße verringert. Die mittlere Zahl der angrenzenden Länder ist also immer kleiner sechs (Vollständige Induktion).

von OlbersD - 28.08.12 23:59 Ach was, Kempe-Kette, ich dachte das wären Olbers-Ketten. Jedenfalls sind diese Ketten und dass verschiedene Ketten ohne eine gemeinsame Farbe sich nicht kreuzen könen, wesentlicher Teil meines Beweises.

matheplanet.com

www-history.mcs.st-andrews.ac.uk

von OlbersD - 29.08.12 00:03 Ach was - ist der Beweis von Kempes wirklich falsch und unvöllständig? Ich jedenfalls behaupte ein Land mit weniger als sechs Nachbarn ist tatsächlich unvermeidbar und dies ist auch Basis für meinen Beweis. Mir scheint, er ähnelt dem KEmpes sehr stark, obwohl ich damit bisher nicht eingehend befasst habe.

von OlbersD - 29.08.12 10:14 Die Sache wird noch einfacher, wenn wir Mehrländerecken mit vier oder mehr Ländern ausschließen, da diese zur Konstruktion eines Gegenbeispiels offenbar wertlos sind. Ein Mehrländerpunkt könnte nämlich zu einem Land erweitert werden, was die Lösung keinesfalls vereinfacht.

von OlbersD - 29.08.12 10:22 Auch bei einem Dreiländereck könnten wir den Dreiländerpunkt zu einem Land ausweiten. Die Summe aller Grenzen, summiert über alle Länder, erhöht sich dabei um sechs (siehe oben), Mittelwert bleibt kleiner. Weiten wir das Land aus, indem wir Dreiländerecke verschieben, ändert sich die mittlere Zahl der Grenzen pro Land nicht und bleibt folglich kleiner sechs. Es ist also klar, mindestens ein Land hat weniger als sechs Nachbarn. Da beißt keine Maus den Faden ab.

von OlbersD - 30.08.12 20:06 Ich habe noch einmal etwas gegoogelt. Der Begriff Kempe-Kette scheint sich tatsächlich im Sinne der olberschen Kette von Ländern mit alternierend zwei Farben in Fachkreisen durchgesetzt zu haben. Nennen wir die Kette als Kempe-Kette.

Bei vier Ländern (1,2,3,4) mit den Farben (A;B;C,D) die an ein Land grenzen und dieses umschließen, kann Land 3 in A umgefärbt werden, sofern keine Kempe-Kette mit den Farben (A,C) von 1 nach 3 existiert. Falls eine solche existiert kann aber keine Kempe-Kette von 2 nach 4 exitieren, die eine Umfärbung von Land 4 in B verhindern könnte, da sich zwei Kempe-Ketten ohne gemeinsame Farbe nicht schneiden können. Damit ist der Fünffarbensatz bewiesen und die Vierfarbensatz kann durch eine etwas komplizierte Überlegung bei fünf Ländern auch bewiesen werden.

Also, nach über hundert Jahren gibt es endlichen einen Beweis!

von OlbersD - 02.09.12 23:18 Jede Landkarte hat mindestens ein Land mit weniger als fünf Nachbarn. Solche Länder können jedoch am Ende, nachdem die restlichen Lände gefärbt wurden ausgefüllt werden. Für weniger als vier Nachbarn ist die offensichtlich, für vier oder fünf Nachbarn kann gezeigt werden, dass die Zahl der verschiedenen Farben der Nachbarn auf drei reduziert werden kann. Entscheidend dabei, zwei sogenannte Kempe-Ketten mit unterschiedlichen Farben (keine gemeinsame Farbe) sich nicht kreuzen können.

Doch, der Beweis ist völlig korrekt. Ich vermute bereits Kempe hatte den Satz vor über hundert Jahren in etwa so bewiesen. Die ganze Grafentheorie ist dagegen ohne erkennbaren Nutzen. Das erinnert an Einstein, der meinte Newton widerlegen zu können und die Gravitation mit der Krümmung der vierdimensionalen Raumzeit erklären zu können. Auch die Allgemeine Relativitätstheorie ist völlig nutzlos.

von OlbersD - 02.09.12 23:19 Sorry, Graphentheorie, Graf ist ein Adelstitel.

von OlbersD - 03.09.12 10:25 Zum Nutzen des Beweises. Der Nutzen des Beweises als solches ist eher gering, weil ohnehin klar war, dass es höchsten fünf Farben sind, die eventuell nötig wären und in den meisten Fällen vier reichen.

Aber die grundlegende Beweisidee von Kempes Beweis kann für viele Optimierungsprobleme genutzt werden. Kempe sagt, es gibt bestimmte unvermeidbare Konfigurationen, die in jeder Karte auftreten müssen, nämlich Lander mit weniger als sechs Nachbarn. Er zeigt in diesen Fällen kann immer eine Lösung gefunden werden, sofern dies für den Rest der Karte gilt. Damit können dieses Länder auch weggelassen werden und das vermeintliche Gegenbeispiel ist zumindest nicht das kleinste denkbare Gegenbeispiel. Wenn es immer noch ein kleineres Gegenbeispiel gibt, kann es gar keine geben.

Diese Grundidee kann in ähnlicher Form häufig genutzt werden, der Beweis ist somit lehreich. Der Computerbeweis, oder sonst irgend ein "Beweis" den niemand versteht, ist in Wahrheit einfach nur nutzlos, wie zum Beispiel auch die Allgemeine Relativitätstheorie.

von OlbersD - 03.09.12 13:48 Ein wesentlicher Teil des Beweises ist zu zeigen, dass es mindestens ein Land gibt mit weniger als sechs Nachbarn. Diese Aussage gilt jedoch, im Gegensatz zum Vierfarbensatz, allgemein als bewiesen. Siehe zum Beispiel

de.wikipedia.org

von OlbersD - 25.12.12 10:03 Ja, aber die Sache mit den Kempe-Ketten im Falle von fünf Ländern ist nicht astrein. Doch ich habe mir was Neues ausgedacht.

Ein minimales Gegenbeispiel ist unendlich.

Also ein Gegenbeispiel mit minimaler Zahl an Ländern kann keine Länder mit vier, drei, zwei oder keinem Nachbarn enthalten, da
diese Land am Ende immer mit einer vierten Farbe eingefärbt werden kann. Bei vier Nachbar ist dazu eventuell eine Umfärbung nötig (Kempe-Kette {1,3} {2,4}). Bei weniger Ländern ist es sofort klar, dass noch eine vierte Farbe übrig bleibt.

von OlbersD - 25.12.12 10:09 Also, wir versuchen ein minimales Gegenbeispiel zu konstruieren. Es gibt immer ein Land mit weniger als sechs Nachbarn (Beweis zum Beispiel mit dem Eulerschen Polyedersatz). In einem minimalen Gegenbeispiel kann es auch kein Land mit vier oder weniger Nachbarn geben. Es gibt in einem minimalen Gegenbeispiel also mindestens ein Land mit fünf Nachbarn. Wir betrachten also dieses Land mit seinen fünf Nachbarn.

von OlbersD - 25.12.12 10:11 Die fünf Nachbarn haben dann ohne die weitere Umgebung zunächst drei Nachbarn, das Zentrum, einen Linken und einen Rechten.

von OlbersD - 25.12.12 10:16 In der äußeren Umgebung müssen daher noch mindestens zwei weitere Nachbarn hinzukommen. Sind es genau zwei und nicht mehr, dann haben wir einen weiteren "Fünfer", als eine der Nachbarn des Zentrums hat ebenfalls nur fünf Nachbar. Ist dies nicht der Fall, dann treten wieder Länder in der Umgebung der fünf Nachbarn auf, die zunächst wiederum nur drei Nachbarn haben. Die müssen wieder mindestens zwei weitere Nachbarn haben und haben dann entweder wiederum nur fünf Nachbarn oder es treten weitere Länder auf, die zunächst nur drei Nachbarn haben.

von OlbersD - 25.12.12 10:18 Jedes der Länder mit nur fünf Nachbarn kann aber als Startpunkt genommen werden, so dass immer weitere "Fünfer" hinzukommen.

von OlbersD - 25.12.12 10:20 Also das Gegenbeispiel wird unendlich groß oder anders ausgedrückt, es gibt gar kein (endliches) Gegenbeispiel, der Vierfabensatz stimmt also!

von OlbersD - 25.12.12 10:54 Ich denke der Beweis ist jetzt wirklich astrein. Aus jedem "Fünfer" werden fünf "unvollständige Dreier". Aus jedem "unvollständigen Dreier" wird entweder mindestens ein weiterer oder ein "Fünfer". Zum Schluss ergeben sich bei einer endlichen Landkarte mindestens fünf weitere "Fünfer". Diese neuen "Fünfer" ergeben dann, wenn sie zum Zentrum gemacht werden, wieder fünf neue "Fünfer". Ok, die könnten jetzt theoretisch auch wieder die Alten sein oder?

@meinefinanzanlagen was meinst du?

von OlbersD - 25.12.12 18:23 Der Großteil des Beweises ist hier

de.wikipedia.org

zu finden.

von OlbersD - 27.12.12 19:03 Ok, es gibt endliche Karten, wo jedes Land mindestens fünf Nachbarn hat, sogar eine Karte aus 12 Ländern mit je fünf Nachbarn (doppeltes Fünfeck mit innerer und äußerer Umgebung).

von OlbersD - 27.12.12 19:16 Es gibt aber in einem minimalen Gegenbeispiel mindestens sechs Fünfer.

von OlbersD - 02.01.13 21:26 Es gibt mindestens ein Land mit fünf Nachbarn. Soweit ist die Sache klar. Wenn immer durch Umfärbungen aus vier Farben der fünf Nachbarländer nur drei verschiedene Farben gemacht werden können, bleibt eine vierte Farbe für das mittlere Land.

Also die fünf Nachbar hätten in dieser Riehenfolge die Farben 1,2,3,4 und 2. Gibt es eine Kette der Farben (1,3) von Position eins nach drei, kann Poistion 3 nicht in 1 umgefärbt werden, ohne auch die 1 in 3 zu färben. Eine solche (1,3)-Kette muss also bestehen, wenn es unmöglich sein soll die Farbe '3' zu eliminieren. Ebenso muss eine (1,4)-Kette bestehen. Wenn eine (1,3)-Kette besteht, kann die 2 an Position 2 in 4 umgefärbt werden, ohne auch die 4 in zwei zu färben.

Wenn dann noch die (1,4)-Kette besteht, kann auch noch die 2 an Position fünf in 3 gefärbt werden. Allerdings könnte die (1,4)-Kette durch die erste Umfärbung aufgelöst werden und eine (2,3)-Kette aufgebaut werden. Dies ist aber nur möglich, wenn die Länder, die die fünf unmittelbar umgeben, alle Farben enthalten.

Wenn dies der Fall ist, könnte das zentale Land und seine fünf Nachbar auch durch ein einziges Land ersetzt werden und es ergäbe sich wieder ein Gegenbeispiel das fünf Farben erfordert. Dann kann das ursprüngliche Gegenbeispiel kein minimales sein. Damit ist der Vierfarbensatz bewiesen.

von OlbersD - 03.01.13 09:43 Der Vierfarbensatz sei falsch. Dann gibt es Gegenbeispiel mit minimaler Zahl an Ländern, so dass eine Karte mit weniger Länder mit vier Farben gefärbt werden kann. Jede Karte hat ein Land mit nur fünf Nachbarn (siehe oben), als auch jedes minimale Gegenbeispiel.

Wir betrachten ein Land mit fünf Nachbarn in einem minimalen Gegenbeispiel. Es gibt eine Färbung mit nur vier Farben der Umgebung. Die fünf Nachbar müssen dabei vier verschiedene Farben erhalten, sonst läge kein Gegenbeispiel inklusive dem Zentrum vor.

O.B.d.A. seinen die Farben der fünf Nachbaren im Uhrzeigersinn 1,2,3,4,2

Es folgt:

Es gibt eine (1,3)-Kette (sonst Umfärbung 1,3)
Es gibt eine (1,4)-Kette (sonst Umfärbung 1,4)

Wegen der (1,3)-Kette kann 2(Pos 2)->4 getauscht, werden, wegen der (1,4)-Kette 2 (Pos. 5).

Einwand:

Nach dem ersten Tausch könnte die (1,4)-Kette nicht mehr bestehen und eine (2,3)-Kette entstanden sein.

Dann muss es jedoch eine Land mit Farbe '2' neben dem Land mit Farbe '3' geben. Es gibt keine direkte Verbindung (1,3) oder (1,4), weil sonst Länder mit nur vier Nachbar auftreten würden. In der Umgebung der fünf umgebenden Länder liegen daher in jedem Fall die Farben '1','3', und '4'. Wenn auch die '2' hinzukommt alle vier Farben. Damit ergäbe sich aber ein kleineres Gegenbeispiel durch Vereinigung der fünf Länder und des Zentrums.
.

von OlbersD - 03.01.13 17:49 Die Reihenfolge beim Tausch könnte auch umgekehrt werden, erst 2->3 an Position fünf, dann 2->4 an Position zwei. Liegt die (1,4)-Kette über der (1,3)-Kette gelingt der Tausch immer.

von OlbersD - 15.01.13 12:10 Wir zeigen den Vierfarbensatz, indem wir zeigen, es ist unmöglich ein Gegenbeispiel zum Vierfarbensatz zu konstruieren.

Gibt es ein Gegenbeispiel, muss es auch ein minimales Gegenbeispiel geben, so dass für alle Karten mit weniger Ländern vier Farben reichen. Ein solches minimales Gegenbeispiel kann kein Land mit nur vier oder weniger Nachbarn beinhalten. Es muss mindestens ein Land mit nur fünf Nachbarn enthalten.

Daraus folgt:

Die Umgebung dieser dieser (5 + 1) Länder ist mit nur vier Farben zu färben und zwar derart, dass die fünf Länder auf vier verschiedene Farben gezwungen werden, es muss auch eine solche Färbung geben, die mit nur vier Farben in der direkten Umgebung der (5 + 1) auskommt, sonst könnten die (5+1) durch nur ein Land ersetzt werden.

Sind die 5 Länder 1,2,3,4,2 gefärbt, gibt es einen (1,3)-Weg und einen (1,4)-Weg, weil sonst nach Umfärbung nur noch drei Farben benötigt werden.

von OlbersD - 08.02.13 15:33 Es gibt aber keinen wirklich vollständigen Beweis. Sechs Länder die (5 + 1) umgeben, können bei einer Färbung mit nur drei Farben, vier verschiedene Farben der 5 erzwingen, so dass keine Farbe für das Zentrum bleibt.


m4 = range(4)
m3 = range(3)

def l3_3(s1,s2,s3,s4,s5,s6):
m3 = range(3)
for f1 in m3:
if f1 not in [s6,s1,s2]:
for f2 in m3:
if f2 not in [s2,s3,f1]:
for f3 in m3:
if f3 not in [s3,s4,f2]:
for f4 in m3:
if f4 not in [s4,s5,f3]:
for f5 in m3:
if f5 not in [s5,s6,f4,f1]:
return true
return not true

def l3_0(s1,s2,s3,s4,s5,s6):
m3 = [1,2,3]
for f1 in m3:
if f1 not in [s6,s1,s2]:
for f2 in m3:
if f2 not in [s2,s3,f1]:
for f3 in m3:
if f3 not in [s3,s4,f2]:
for f4 in m3:
if f4 not in [s4,s5,f3]:
for f5 in m3:
if f5 not in [s5,s6,f4,f1]:
return true
return not true

def l3_1(s1,s2,s3,s4,s5,s6):
m3 = [0,2,3]
for f1 in m3:
if f1 not in [s6,s1,s2]:
for f2 in m3:
if f2 not in [s2,s3,f1]:
for f3 in m3:
if f3 not in [s3,s4,f2]:
for f4 in m3:
if f4 not in [s4,s5,f3]:
for f5 in m3:
if f5 not in [s5,s6,f4,f1]:
return true
return not true

def l3_2(s1,s2,s3,s4,s5,s6):
m3 = [0,1,3]
for f1 in m3:
if f1 not in [s6,s1,s2]:
for f2 in m3:
if f2 not in [s2,s3,f1]:
for f3 in m3:
if f3 not in [s3,s4,f2]:
for f4 in m3:
if f4 not in [s4,s5,f3]:
for f5 in m3:
if f5 not in [s5,s6,f4,f1]:
return true
return not true

def l3(s1,s2,s3,s4,s5,s6):
x = l3_0(s1,s2,s3,s4,s5,s6) or l3_1(s1,s2,s3,s4,s5,s6)
x = x or l3_2(s1,s2,s3,s4,s5,s6)
x = x or l3_3(s1,s2,s3,s4,s5,s6)
return x

def l4(s1,s2,s3,s4,s5,s6):
m4 = range(4)
for f1 in m4:
if f1 not in [s6,s1,s2]:
for f2 in m4:
if f2 not in [s2,s3,f1]:
for f3 in m4:
if f3 not in [s3,s4,f2]:
for f4 in m4:
if f4 not in [s4,s5,f3]:
for f5 in m4:
if f5 not in [s5,s6,f4,f1]:
return True
return False


cnt = 0
cnt2 = 0
for s1 in m3:
for s2 in m3:
if s1!=s2:
for s3 in m3:
if s3!=s2:
for s4 in m3:
if s4!=s3:
for s5 in m3:
if s5!=s4:
for s6 in m3:
if s6 not in [s1,s5]:
if (not l3(s1,s2,s3,s4,s5,s6)) and l4(s1,s2,s3,s4,s5,s6):
cnt = cnt + 1
print s1, s2, s3, s4, s5, s6
print cnt

von OlbersD - 10.02.13 11:43 Also halten wir mal fest, was eindeutig gezeigt ist und auch in der einschlägigen Fachliteratur und Wikipedia zu finden ist:

Die mittlere Anzahl der angrenzenden Länder ist kleiner als sechs. Es gibt daher immer mindestens ein Land mit weniger als sechs Nachbarn. Länder mit vier oder weniger Nachbarn können in einem minimalen Gegenbeispiel (minimale Anzahl an Ländern) nicht auftreten.

In einem minimalen Gegenbeispiel gibt es daher immer ein Land mit fünf Nachbarn. Die fünf Nachbarn können dort mit vier nicht aber mit drei verschiedenen Farben gefärbt werden.

Es kann in einem minimalen Gegenbeispiel auch keine (5+1) Länder mit einem, zwei, drei, vier oder fünf Nachbarn der 5 äußeren Länder geben. Die 5 äußeren Länder müssen also mindestens sechs Nachbarn haben.

von OlbersD - 10.02.13 11:48 Jetzt gibt es aber weit mehr Möglichkeiten der Färbung der 6 äußeren Länder bei einem (5+1)-Kern, im Vergleich zu einem einzigen Kernland oder zwei oder drei Kernländern im Innern der 6 Länder. Dies gilt um so mehr bei mehr als 6 Ländern um den (5+1)-Kern.

von OlbersD - 10.02.13 11:49 Ich denke daher der Vierfarbensatz stimmt tatsächlich.

von OlbersD - 10.02.13 12:01 Zum Beispiel:

Kreis aus 6 Ländern ohne Kernländer: 732 Färbemöglichkeiten

Kreis aus 6 Ländern mit einem Kernland: 264 Färbemöglichkeiten

Kreis aus 6 Ländern mit (5+1) Kernlandern: 528 Färbemöglichkeiten

von OlbersD - 10.02.13 20:35 Kreis aus 6 Ländern zwei Kernländer: 348 Färbemöglichkeiten

Kreis aus 6 Ländern drei Kernländer 408 Färbemöglichkeiten

Kreis aus 7 Ländern ohne Kernland 2184 Färbemöglichkeiten

Kreis aus 7 Ländern mit einem Kernland 504 Färbemöglichkeiten