Diskussion:Vier-Farben-Satz

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis 1 Überholung 2 Quelle zum Zitat 3 computer-beweis 3.1 Allenfalls eine Widerlegung 4 allgemeine anmerkungen 5 Anfrage (aus den Entsperrwünschen hierher verschoben)

Ü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)

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)

Allenfalls eine Widerlegung

Das mit dem Compter-Beweis ist doch offensichtlicher Unfug. Mit einem Computer könnte für eine vorgegebene Landkarte eine Lösung mit nur vier Farben gefunden werden. Im einfachsten Fall könnte ein solches Programm für jedes Land alle vier Farben – dargestellt durch die Zahlen 0,1,2 und 3 – durchtesten und dann überprüfen, ob zwei angrenzende Länder die gleiche Farbe aufweisen.

Beim falschen Gegenbeweis könnten für den Kreis im Zentrum Z, die angrenzenden umliegenden Länder A,B,C,D, der äußere Kreis E,F,G,H und die Umgebung U die Farben geschachtelten Schleifen durchlaufen werden.

Eine C-Implementierung könnte etwa wie folgt aussehen:

main(){

int z,a,b,c,d,e,f,g,h,u;
int cnt=0;
for (z=0;z<4;z++)
 for (a=0;a<4;a++)
  for (b=0;b<4;b++)
    for (c=0;c<4;c++)
      for (d=0;d<4;d++)
        for (e=0;e<4;e++)
          for (f=0;f<4;f++)
            for (g=0;g<4;g++)
             for (h=0;h<4;h++)
               for (u=0;u<4;u++){

                  if (z==a || z==b || z==c || z==d) continue;
                  if (u==e || u==f || u==g || u==h) continue;
                  if (a==b || b==c || c==d || d==a) continue;
                  if (e==f || f==g || g==h || h==e) continue;
                  if (a==e || a==f || b==f || b==g) continue;
                  if (c==g || c==h || d==h || d==e) continue;
                  printf ("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d\n",
                  z,a,b,c,d,e,f,g,h,u);
                  cnt++;
               }
 printf("Es wurden %d Loesungen gefunden\n",cnt);

}

Dieses Programm findet alle 192 Lösungen in Sekundenbruchteilen. Da die Rechnenzeit jedoch exponentiell wächst, kann dieses Vorgehen für etwa 20 bis 30 Länder umfassende Karten angewendet werden. Es jedoch nicht möglich, mit einem ähnlichen Programm die Lösung für das Bild

hier zu finden. M4c 15:16, 2. Aug. 2007 (CEST)

Für 100 und mehr Länder ist eine Überprüfung aller Färbungen völlig ausgeschlossen. Es ist daher nicht möglich mit einem einfach Programm für eine solche vorgegebene Karte zu zeigen, dass eine Färbung mit vier Farben möglich ist. Dies für jede beliegbige Landkarte mittels eines Computerbeweises zu zeigen ist absurd. M4c 15:26, 2. Aug. 2007 (CEST)

Viel Spaß beim Publizieren. (Als Hinweis: Hier geht es nur um den Inhalt des Artikels, nicht um eigene Meinungen und Ideen dazu.) --Scherben 15:59, 2. Aug. 2007 (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)

Es geht doch um zusammenhängende Fläche und ein Land, das eine Exklave oder Enklave hat, ist keine zusammenhängende Fläche. Coma hat natürlich recht, weil die Menge der Exklaven auch die Enklaven enthalten. -- Amtiss, SNAFU ? 12:40, 9. Dez. 2006 (CET)

Falls jedes Land mit jedem anderen eine Grenze besitzt, wären die Farben der Länder paarweise verschieden und daher ebensoviele Farben erforderlich wie Länder vorhanden sind. Daher wäre der Vier-Farben-Satz sofort zu widerlegen, falls ein gemeinsamer Grenzpunkt aller Länder oder Exklaven jedes Landes in allen anderen Ländern erlaubt wären. M4c 16:12, 2. Aug. 2007 (CEST)

Anfrage (aus den Entsperrwünschen hierher verschoben)

Der Artikel muss nicht entsperrt werden. Ich interessiere mich allerdings dafür, ob Gewässer, die auf Landkarten grundsätzlich die Farbe blau tragen und damit haufenweise farblich festgelegte En- und Exklaven bilden, in diesem Problembeweis berücksichtigt wurden. Das kam für mich in dem Artikel nicht klar rüber. Dies nur als Info. Gruß --85.179.23.102 11:12, 6. Sep. 2007 (CEST)

Nein. Wasser ist nicht vorgesehen. --Scherben 22:04, 6. Sep. 2007 (CEST)