Diskussion:Vier-Farben-Satz

Wer den alten Beweisversuch von sigi (und das getrolle und die Diskussion dazu sucht, bitte hier: Diskussion:Vier-Farben-Satz/Beweis. Der Übersichtlichkeit wegen ;) und da solche neue Ideen, so oder so nicht in einen Artikel in der WP gehören. Für alle Interessierten: Es gibt dort auch eine neue Widerlegungvon PatrickU! --mirer 19:44, 25. Mai 2005 (CEST)

Überholung

Der Artikel bedarf dringend einer Ueberholung, mal ganz abgesehen vom Streit um den (Pseudo)Beweis.

• Es fehlt der damalige 5-Farbensatz von Heawood (im geschichtlichen Teil).
• Ausserdem sollte man die Heawoodsche Vermutung (bzw. Ringel -Youngs) nicht so salopp

als bewiesene Verallgemeinerung darstellen, den dies legt den Schluss nahe das mit dem Beweis der algemeinen Behauptung auch der Spezialfall des 4-farbensatz bewiesen ist. Und genau dies ist hier falsch !!!

Den Fünf-Farben-Satz habe ich im Geschichtsteil mal erwähnt und auch drumherum mehr beschrieben. Macht es Sinn in diesem Artikel auf den Beweis (Idee in Prosa) einzugehen oder eher nicht?! --mirer 19:39, 25. Mai 2005 (CEST)

Quelle zum Zitat

quellenangabe für "Ein guter Beweis liest sich wie ein Gedicht - dieser sieht aus wie ein Telefonbuch!" fehlt --hofoen

Wurde wohl aus der englischen Wikipedia übersetzt. Dort wird der Satz als "Paraphasierung damaliger Kommentare" bezeichnet (vielleicht kann jemand das etwas sauberer übersetzen). Übrigens gibt es dort sehr schöne Grafiken zur Veranschaulichung. --Kurt Jansson 18:56, 5. Jun 2003 (CEST)

Abbildung

Dort steht, dass die Abbildung verdeutlicht, dass man 5 Farben benötigt. Das widerspricht nicht nur dem Satz, verdeutlicht vor allem aber nix. Ich finde es in der Abbildung sogar sehr leicht nachvollziehbar, dass man dort nur 4 Farben braucht, auch wenn in der Abbildung natürlich 5 verwendet werden. Stern !? 19:03, 8. Sep 2004 (CEST)

Löschen war Richtig ;) --mirer 02:58, 9. Sep 2004 (CEST)

Den Absatz "Zweifel an der Korrektheit des Beweises" sollte man ganz löschen, da er völliger Schwachsinn ist. Die dort aufgestellten Gedanken, die alle mit "vielleicht" abgeschwächt werden, sind nicht zu Ende gedacht. Wenn man die Farben in der Abbildung ein wenig verschiebt, kommt man immer zum Ergebnis, dass doch 4 Farben ausreichend sind. Und das auch wenn außen rum noch ein Feld wäre. Das dort klingt wie philosophische Gedanken eines Kleinkindes und hat bei einem seriösen Thema wie diesem nichts verloren.

computer-beweis

zwei meiner dozenten hatten unabhaengig voneinander mal behauptet, dass die ersten veroeffentlichten computer-gestuetzten beweise zum vier-farben-problem fehlerhaft gewesen seien, was man lange zeit jedoch nicht gemerkt habe. ich konnte im web allerdings nichts konkretes dazu finden. vielleicht weiss jemand anders mehr dazu? --84.56.237.109 2. Jul 2005 18:37 (CEST)

das weiß ich nicht, aber die autoren des letzten neueren beweises behaupten, dass selbst der part, der nicht vom computer erzeugt wurde nie vollständig von einer person alleine geprüft wurde, weil er so komplziert war, soll heißen, nur die autoren des beweses selbst haben diesen bis ins letzte detail verstanden. das allein ist schon recht problematisch. im übrigen war das die motivation für den neuen einfacheren beweis. --Coma 2. Jul 2005 21:11 (CEST)

Vielleicht meinten deine Dozenten nicht die Computergestützten Beweise, sondern die Beweise von Kempe und Tait? --Coma 3. Jul 2005 09:17 (CEST)

Es war wohl so, daß nach der Veröffentlichung des Beweises das Programm eingehend untersucht wurde und dabei Bugs entdeckt worden sind. Die wurden dann korrigiert und das Programm nochmal ausgeführt. Das Ergebnis war wieder, daß der Satz gilt. Bugs im Programm bedeuten natürlich, daß der Computer falsche Schlüsse macht und somit der erste Beweis falsch war. Genaueres ist sicher beim Zentralblatt zu finden. --MlaWU 3. Jul 2005 17:23 (CEST)

Zunächstmal enthält jedes Programm, dass nicht aus ein paar Zeilen Code besteht, irgendwelche Fehler. Es wäre zu klären, wie schwerwiegend diese Fehler ausfallen. Unabhängig davon muss natürlich auch der Compiler (bzw. Interpreter) korrekt arbeiten, der das Programm übersetzt. Und der Compiler und die Compilergeneartoren, die diesen Compiler übersetzt haben müssen auch korrekt arbeiten. Das ergibt eine ziemlich lange Kette, in der garantiert ein Programm fehlerhaft ist. Das ist übrigens auch einer der Hauptkritikpunkte an "Computerbeweisen". Die Berechnung und Verifikation mittels Computer an sich ist es nicht. Schließlich ist es ja die eigentliche Aufgabe der Mathematik Aussagen so zu beweisen, dass sie Verifizierbar werden, indem man dem Beweis folgt. Aber ich glaube ich komme grad vom Thema ab... :-) --Coma 3. Jul 2005 19:33 (CEST)

Ich habe jetzt nur eine Zusammenfassung dazu gefunden: [1], jetzt müßte man nur noch wissen, was Fehler ersten und dritten Grades sind. Die Zeitschrift selbst gibt es in der bibo natürlich wieder nur seit '92. Immer ganz toll sowas. --MlaWU 3. Jul 2005 22:51 (CEST)

Die ersten beiden (nicht computergestützten) "Beweise" waren falsch, und wurden jew. 11 Jahre lang nicht als fehlerhaft erkannt. Es ist einfach so, dass die 100%ige Beweissicherheit, die jeder Mathematiker gerne hätte, nie erreichbar ist. Wieviele Bugs hat ein Gehirn? Ein zuverlässiger Computer kann Billionen und Billiarden ganzer Zahlen ohne einen einzigen Rechenfehler verarbeiten. Welcher Mensch bekäme das auch nur ansatzweise hin, selbst in einem ganzen Erdenleben? Die Wahrscheinlichkeit eines Fehlers 2. Art, die immer größer Null ist, hängt meines Erachtens nicht davon ab, ob ein Beweis computergestützt nachvollzogen wurde, oder nicht, sondern von seiner Komplexität und dem Aufwand, der betrieben wurde, um ihn zu verifizieren. Natürlich wäre ein Beweis, der auf ein DIN A4-Blatt passt, und von einem Sechsjährigen verstanden werden kann, als vertrauenswürdiger anzusehen. Momentan ist aber nunmal der einzige (nicht bereits widerlegte) Beweis derart komplex, dass ihn ein Mensch ohne Hilfsmittel nicht überprüfen kann. Nur verwechseln viele die Ursache des Problems (Komplexität des Beweises) mit einem Symptom (ein Hilfsmittel ist erforderlich, um ihn effizient nachzuvollziehen). Darüber hinaus gibt es einige Möglichkeiten, um die Zuverlässigkeit der Beweisführung zu erhöhen:

1. Der Algorithmus des Beweisprogramms muss selbstverständlich offengelegt werden. Besser ist aber auch noch die Offenlegung der Implementierung, also des konkreten Computerprogramms.
2. Die Implementierung sollte portabel sein, so dass sie auf verschiedenen Plattformen (Hardware, Betriebssystem, etc.), mit verschiedenen Implementierungen der verwendeten Programmiersprache, ausgeführt werden kann. Die Wahrscheinlichkeit, dass Fehler in allen verwendeten Plattformen übersehen werden, wird so reduziert.
3. Mehrere Implementierungen können erstellt werden, bevorzugt wiederum mittels verschiedener Programmiersprachen.
4. Hilfsmittel zum Erstellen beweisbar korrekter Software sollten zum Einsatz kommen.

Wenn man die Stärken und Schwächen des menschlichen Gehirns und von elektronischen Recheneinheiten einigermaßen objektiv betrachtet, kommt man schnell zu dem Schluss, dass unter Einhaltung obiger Sicherheitsvorkehrungen der Einsatz eines Computers nicht die Zuverlässigkeit des Nachvollzugs mindert, sondern dramatisch verbessert. Das Grundproblem der hohen Beweiskomplexität bleibt bestehen, aber die Vertrauenswürdigkeit eines derart mit elektronischer Hilfe geprüften Beweises liegt um Größenordnungen höher als die Vertrauenswürdigkeit eines ähnlich komplexen Beweises, der nicht unter Zuhilfenahme elektronischer Hilfsmittel verifiziert wurde. Aragorn2 15:02, 27. Apr 2006 (CEST)

allgemeine anmerkungen

Hallo, sagt mal, Enklaven dürfen doch sehr wohl vorkommen, nur Exklaven explizit nicht, oder? Die Enklave darf eben nicht Exklave sein, aber wenn Exklave ausgeschlossen sind, dann ist für diesen Fall ja gesorgt. Korrigiert mich wenn ich falsch liege.

Wenn ich den Definitionen unter Enklave und Exklave folge genügt es tatsächlich Exklaven auszuschließen. --Coma 11:13, 18. Nov 2005 (CET)

Straße durch alle Länder

Im allgemeinen können vier Farben nicht genügen. Angenommen es gäbe eine Straße, die durch alle Länder führt. Dann könnte man sich vorstellen, dass diese Straße - etwa wie früher die Autobahn nach Westberlin - nicht zu dem jeweiligen Land gehört sondern ein weiteres eigenen Land bildet. Offensichtlich wäre für dieses neue Land ein fünfte Farbe erforderlich, da es Grenzen zu allen anderen Ländern besitzt. Auch fünf Farben genügen im Allgemeinen nicht, da eine weitere Straße oder zur Abwechselung mal eine Eisenbahnline durch alle Länder gebaut werden könnte.

Benutzer:Fsswsb 05.06.2006

Wie im Artikel steht, werden Exklaven (die durch die Straße/Eisenbahnlinie entehen würden) ausgeschlossen. --Andreas ?! 18:48, 5. Jun 2006 (CEST)

Eine Straße durch alle Länder ist sicher nicht als eine Exklave zu bezeichnen. Eine Exklave ist durch die fehlende Verbindung zum Mutterland ausgezeichnet. Die Straße durch alle Länder ist aber ein zusammenhängendes Gebiet. Man könnte vielleicht einwenden, dass die übrigen Länder durch die Straße nicht mehr zusammenhängend sind. Ok, dann betrachte ich eben die durch Straße entstanden Teile als getrennte Länder.(nicht signierter Beitrag von Fsswsb (Diskussion | Beiträge) Andreas ?! 19:25, 5. Jun 2006 (CEST))

Und wo liegt dann das Problem? Dann können ja die Farben entsprechend neu verteilt werden. --Andreas ?! 19:25, 5. Jun 2006 (CEST)

Falls möglichst wenige Farben verwendet werden sollen, ist es sicherlich optimal für die durch die Straße getrennten Landesteile oder neuen Länder weiterhin die gleiche Farbe zu verwenden - was im Falle einer echten Exklave auch möglich ist. Dadurch werden jedoch keineswegs weniger verschiedene Farben benötigt. Alle Grenzlinien, die schon vor dem Straßenbau und der Länderteilung vorhanden waren, bestehen ja weiterhin. Falls für die Länder zuvor 4 Farben erforderlich waren sind danach fünf erforderlich, weil die Straße durch alle Länder, die ein eigenes Land bildet, durch alle Länder (bzw. neue Landesteile) führt und daher eine von allen bisherigen Landesfarben verschiedene Farbe haben muss.

Ließ nochmal bei Exklave nach. Deine Straße ist ein Land, daß den Großteil der anderen Länder in einen Hauptteil und mindestens eine Exklave zerlegt. -- MlaWU 20:49, 5. Jun 2006 (CEST)

Wenn es alles so offensichtlich ist, gib doch einfach mal ein konkretes Beispiel, für das fünf Farben nötig sind. Andernfalls lass das Getrolle. Danke! --Andreas ?! 22:37, 5. Jun 2006 (CEST)

Ok, ihr habt wohl recht und ich habe mich geirrt. Auch wenn es jedenfalls für mich sehr erstaunlich ist, bei zusammenhängenden Gebieten genügen - auch wenn ich es nicht wirklich beweisen kann - tatsächlich immer vier Farben.Benutzer:Fsswsb 06.06.2006