Diskussion:Vier-Farben-Satz

Diese Diskussionsseite dient dazu, Verbesserungen am Artikel „Vier-Farben-Satz“ zu besprechen. Persönliche Betrachtungen zum Thema gehören nicht hierher. Für allgemeine Wissensfragen gibt es die Auskunft.

Füge neue Diskussionsthemen unten an:

Klicke auf Abschnitt hinzufügen, um ein neues Diskussionsthema zu beginnen.

• Diskussionsregeln
• Hilfe zu Diskussionsseiten
• Sei sachlich und freundlich!
• Greife niemanden persönlich an!
• Geh von guten Absichten aus.

Ü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 allgemeinen Behauptung auch der Spezialfall des 4-farbensatz bewiesen ist. Und genau dies ist hier falsch !!! (nicht signierter Beitrag von 84.132.224.26 (Diskussion | Beiträge) 15:46, 25. Mai 2005 (CEST))

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)

Mittlerweile ist auch das Missverständnis um die "bewiesene Verallgemeinerung" behoben. --91.32.75.142 11:37, 11. Dez. 2009 (CET)

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

Datei:M4cd.png

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. (nicht signierter Beitrag von 84.159.223.219 (Diskussion | Beiträge) 10:00, 18. Nov. 2005 (CET))

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)

Ein Land mit Enklave kann durchaus zusammenhängend sein. Aber es steht ja mittlerweile korrekt im Artikel (nur Exklaven müssen ausgeschlossen werden). --91.32.75.142 10:43, 11. Dez. 2009 (CET)

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)

Um Missverständnisse auszuschließen: Aus dem Satz kann man leicht folgern, dass bei Vorgabe von nicht zusammenhängenden, blauen Wasserflächen für die Länder nicht mehr als vier weitere Farben benötigt werden, und offensichtlich gibt es Beispiele, in denen vier weitere Farben nötig sind. Insofern wird die Aufgabenstellung nicht dadurch unrealistisch oder mathematisch uninteressant. --91.32.81.54 12:11, 15. Dez. 2009 (CET)

Andere Geometrien

In der niederländischen Wikipedia wird auch erwähnt, dass man auf einem Möbiusband 6, auf einer Torusoberfläche 7 Farben benötigt. Wäre dies nicht auch hier erwähnenswert, incl. der hübschen Karten? --RokerHRO 21:34, 30. Apr. 2009 (CEST)

Das ist die Heawood-Vermutung, deren Teil ohne den Fall des Vier-Farben-Satzes der Satz von Ringel-Youngs ist. Sie wird bereits (seit 20. August 2002) im Artikel erwähnt. Ein Bild (ein etwas besser verständliches aus der englischen Wikipedia) füge ich noch hinzu. --91.32.75.142 11:10, 11. Dez. 2009 (CET)

Habe die Map für den Torus mal sauberer und als SVG neugezeichnet, siehe nebenstehendes Bild und damit mal einen Torus gerendert und animiert Datei:Torus 7color animated.gif. Ich hoffe, ich hab keinen Fehlr in der Map, mir ist jedenfalls erstmal keiner aufgefallen. :-) --RokerHRO 13:12, 11. Dez. 2009 (CET)

Es ist, soweit ich sehe, alles korrekt: Jedes Feld muss mit jedem benachbart sein, der zugehörige Graph ist der vollständige Graph K₇. Ästheten würden vielleicht noch gleich große Felder verlangen, damit es schön Z₇-symmetrisch ist. Am besten wäre ein eigener Artikel Heawood-Vermutung oder Satz von Ringel-Youngs (man könnte sich auf einen von beiden beschränken und den anderen einbauen), in Gerhard Ringel stehen schon ein paar Details. --91.32.75.142 14:21, 11. Dez. 2009 (CET)

Gleiche Größe aller Farbflächen - auf der Map - ist gar nicht so einfach, wenn die Eckpunkte der Polygone auf einem ganzzahligen Gitter liegen sollen (was aus zeichnerischer Sicht halt einfacher wäre). Ich grübel grad, wie das Raster dafür liegen müsste. &mbdash; Eine identische Größe der Flächen auf der Torusoberfläche wäre aber sicher eine richtige Herausforderung! :-) --RokerHRO 15:58, 11. Dez. 2009 (CET)

Nicht diesen Reifen, Mathematiker nehmen fast immer [0,1] × [0,1] :-) Kann man ausrechnen: Es muss eine Fläche 1/7 sein, also zum Beispiel 1/3 × 3/7, das ist 7/21 × 9/21. Somit im Raster 21 × 21 zum Beispiel die Punkte (9, 3) × n und (0, 7) + (9, 3) × n (mod 21) für n = 0, ..., 6. --91.32.75.142 22:21, 11. Dez. 2009 (CET)

Ich binde die Bilder schon mal ein, nicht? Neue Versionen könnt ihr ja noch basteln. Denke aber, für die Anschauung ist das, was da vorliegt, bereits völlig ausreichend.--goiken 00:28, 12. Dez. 2009 (CET)

Danke. Hab das Bild mal entsprechend deiner "Bastelanleitung" geändert. Nun nur noch den Torus neu rendern. :-) --RokerHRO 10:29, 14. Dez. 2009 (CET)

Erledigt. :-) --RokerHRO 10:52, 14. Dez. 2009 (CET)

Sehr schön! --91.32.85.181 21:08, 14. Dez. 2009 (CET)

Wenn ich nichts übersehen habe, dann behauptet dieser Artikel etwas Unzutreffendes über die Heawood-Vermutung, und macht von diesem Nonfaktum in entscheidender Weise Gebrauch: Der Artikel zur Heawood-Vermutung sagt, dass diese nur eine obere Schranke für die Zahl der Farben behauptet, und nicht, dass diese die kleinste obere Schranke ist. Sieben als kleinste obere Schranke für den Torus wird dann per Beispiel illustriert. Doch es fehlt der Verweis auf eine anerkannte mathematische Veröffentlichung eines entsprechenden Beweises. Insbesondere ist dies laut Artikel nicht die Heawood-Vermutung. Natürlich braucht Wikipedia keine Literaturverweise für vollkommen offensichtliche mathematische Tatsachen wie 3x3=9 anzugeben. Doch gerade weil selbst große Mathematiker sich bei dieser Art von Problem so oft geirrt haben, kann hier nicht von einer offensichtlichen mathematischen Tatsache die Rede sein. Das Risiko, dass Behauptungen offensichtlich wahr scheinen und auf verborgene Weise doch falsch sind, ist einfach zu groß. --2003:DE:23E8:D625:7949:2451:66B8:8432 14:16, 2. Okt. 2017 (CEST)

Einfach noch mal den Satz von Ringel Youngs lesen ... da ist dies erklärt und auch dass dies sehr wohl eine Formel für die "minimale Anzahl der Farben" die benötigt werden ist.

Ansonsten ist Wikipedia nicht der Ort für private Untersuchungen & Vermutungen. Hier wird etabliertes Wissen auf Basis reputabler Sekundäliteratur dargestellt, keine eigenen Ideen & Theorien. Falls dir etwas falsch erscheint, dann diesen Satz/Abschnitt mit einem Verweis auf die entsprechende reputable Sekundärliteratur zur Diskussion stellen. Wenn dir etwas unbelegt erscheint, dann bitte auch einen konkreten Abschnitt benennen - allerdings bitte nicht nur aufgrund dessen, dass man es selbst nicht verstanden hat. --mirer (Diskussion) 19:12, 2. Okt. 2017 (CEST)

Algorithmus für 4-Färbung

Ich suche einen möglichst einfachen bzw. eleganten Algorithmus um eine 4-Färbung ausgehend von einer Adjazenzmatrix zu finden. --Skraemer 20:27, 8. Okt. 2009 (CEST)

hier wird das beschrieben. --goiken 11:45, 11. Dez. 2009 (CET)

Riegel im euklidischen Raum

Das Beispiel mit den Riegeln ist meines Erachtens Blödsinn. Ich kann einfach die unteren Riegel abwechselnd blau und rot färben und die oberen abwechselnd grün und gelb, wo ist da das Problem? (nicht signierter Beitrag von 79.227.22.154 (Diskussion | Beiträge) 16:20, 23. Dez. 2009 (CET))

Denk das nochmal durch. Es berührt tatsächlich jeder Riegel vom unteren Block jeden Riegel von oben (und zusätzlich seine Nachbarn). Deine vorgeschlagene Färbung passt nicht.--goiken 16:22, 23. Dez. 2009 (CET)

Ich hatte das "verbunden" überlesen, und wer Überlesen kann ist klar im Nachteil (nicht signierter Beitrag von 79.227.22.154 (Diskussion | Beiträge) 16:23, 23. Dez. 2009 (CET))

:-) --goiken 16:24, 23. Dez. 2009 (CET)

Das Beispiel hinkt meines Erachtens trotzdem, weil ich für die n Quader der unteren Ebene maximal 4 Farben brauche. Wenn ich dann eine Ebene drauflege, bin ich bei acht, unabhängig von der Anzahl der Quader. Also zumindest für diese Quader-Bauklötzchen (und zwei ebenen wie in dem "Beweis"-Beispiel) gilt dann, dass man immer mit maximal 8 Farben auskommt. Martino 10:37, 9. Mär. 2010 (CET)

Die Riegel werden in Paaren verschmolzen, das heißt, es werden immer zwei Riegel, je einer aus der unteren und einer aus der oberen Ebene, zu einem Körper zusammengefasst (diese Paare müssen also einheitlich mit der gleichen Farbe gefärbt werden). Sonst käme man, wie bemerkt, sogar schon mit vier Farben aus. Da das ständig missverstanden wird: Wie könnte man das im Artikel besser formulieren, oder gibt es ein einfacheres Beispiel? --91.32.76.97 10:52, 9. Mär. 2010 (CET)

Danke! Jetzt habe auch ich das Prinzip verstanden. Vielleicht genau so schreiben wie hier erklärt? --Martino 22:20, 9. Mär. 2010 (CET)

George Spencer-Brown

Da selbst nach dem wiki-artikel über ihn niemand den Beweis von George Spencer-Brown zur Kenntnis nimmt geschweige denn anerkennt habe ich ihn ganz entfernt.--Claude J 13:00, 7. Jan. 2010 (CET)

Großartige Begründung! Vor allem, da sich scheinbar keiner eingehend damit auseinander gesetzt hat. (nicht signierter Beitrag von 82.113.106.34 (Diskussion) 18:49, 8. Mai 2012‎ (CEST))

Es ist nicht unsere Aufgabe, eingereichte Arbeiten zu prüfen, siehe auch WP:NOR. Ebensowenig können wir hier verkannten Genies zu ihrem Recht verhelfen, siehe auch WP:NPOV. --84.130.163.76 19:04, 8. Mai 2012 (CEST)

Mea culpa! Dachte (fälschlicherweise) Kauffmans "Reformulating the map theorem" wäre eine ernstzunehmende Verteidigung von Spencer-Browns Ansatz. Ich wollte nicht als Apologet wirken und keinem auf den Schlips treten. Natürlich kenne und akzeptiere ich WP:NOR und WP:NPOV. -- (nicht signierter Beitrag von 89.204.130.156 (Diskussion) 12:01, 26. Jun. 2012 (CEST))

(unbenannt)

Mir ist aufgefallen, dass die Formalisierung nicht richtig ist: "Man fragt, ob die Knoten jedes planaren Graphen mit maximal vier Farben so gefärbt werden können, dass keine benachbarten Knoten die gleiche Farbe tragen." Das ist aber sowieso nicht der Fall: Nimm zum Beispiel einen vollständigen planaren Graphen mit fünf Knoten. Für diesen benötigt man genau fünf Farbe, um diesen gemäß der Fragestellung zu färben (da jeder Knoten ist mit jedem anderen durch eine Kante verbunden ist). Es fehlt hier also dringend eine Präzisierung. Wie die genau aussieht weis ich auch nicht. Ich werde mich mal schlau machen, und den Artikel dann dementsprechend ändern. -- Rodriguez1820 17:12, 8. Jan. 2010 (CET)

Es geht bei der Färbung nur um planare Graphen.

Der vollständige Graph K₅, siehe rechts, ist nicht planar. --RokerHRO 22:28, 8. Jan. 2010 (CET)

Alles klar, ich hatte eine falsche Definition des Begriffes "planar" im Kopf. -- Rodriguez1820 08:02, 14. Jan. 2010 (CET)

Dieser Abschnitt kann archiviert werden. RokerHRO 08:50, 14. Jan. 2010 (CET)

Die dritte Dimension

Hallo zusammen,

Wenn mich nicht alles täuscht, hat sich beim "Riegel im Euklidischen Raum" ein Fehler eingeschlichen:

Habe ich eine "Riegel-Ebene" mit 8 verschiedenen Farben und lege darauf die selbe Ebene um 90° gedreht, berührt jeder Riegel der oberen Ebene jeden Riegel der unteren, ergo reichen 8 verschiedene Farben nicht aus, es müssten also mindestens 16 (also 2*n) verschiedene Farben sein, nicht nur 8 wie im Beitrag genannt.

Zitat: Da jeder Körper jeden anderen berührt, braucht man zum Färben so viele Farben wie Riegel (hier 8).

Grüsse

 Geldsyndrom

--Geldsyndrom 19:42, 25. Jan. 2010 (CET)

Deswegen steht ja unter dem Bild (und ähnlich auch im Text): "Nach dem Zusammenfügen in der rechten Grafik sind jeweils die beiden gleichfarbigen „Riegel“ verbunden und bilden einen Körper." Wenn man die Verschmelzung der Riegel nicht macht, genügen vier Farben (zwei oben und zwei unten). --91.32.77.83 19:59, 25. Jan. 2010 (CET)

Ich bin auf das Bild auch schon hereingefallen - sogar mehrfach ;) Da muss noch einer der verbundenen Körper einzeln abgebildet werden, dann wird das besser erkennbar sein. Michael Schumacher 14:07, 27. Jan. 2010 (CET)

Fehlerhafte Gegenbeweise

Wenn ich mich nicht täusche, kann man das Beispiel in den Bildern mit dem Umfärben von drei Regionen auf vier Farben reduzieren, nicht wie angegeben mit "mindestens vier Regionen". Beispielsweise so:

- Zentrum von Blau nach Grün

- im inneren Ring von Grün nach Rot

- im äußeren Ring von Rot nach Grün

Gruß

-- jens (nicht signierter Beitrag von 153.100.131.14 (Diskussion) 10:39, 9. Jun. 2010 (CEST))

Dann wären es immer noch fünf Farben. Die umgebende Fläche (blau) gehört dazu. --91.32.78.198 10:49, 9. Jun. 2010 (CEST)

Ah, okay. Sorry. -- jens (nicht signierter Beitrag von 153.100.131.14 (Diskussion) 10:56, 9. Jun. 2010 (CEST))

Dieser Abschnitt kann archiviert werden. RokerHRO 12:21, 9. Jun. 2010 (CEST)

"Viele andere, hauptsächlich von Amateuren entwickelte, sind niemals veröffentlicht worden." Gehört solch eine Trivialität in eine "Enzyklopädie"? --(nicht signierter Beitrag von 88.67.178.132 (Diskussion) 17:26, 23. Jun. 2011 (CEST))

warum kein beweis

angesichts der komplexität bestehender beweise kann ich zwar sehen dass die art und weise wie ich mir das mit "bauchgefühl" erklärt hab falsch sein muss, aber der formale knackpunkt weshalb das so sein muss ist mir nie klargeworden.

Ich stelle mir das so vor: ich starte mit einer fläche und stelle sie mir als knotenpunkt in einem graph vor. Wenn ich nun eine zweite berührende fläche hinzutue dann verbinde ich die beiden. Will ich nun eine weitere fläche hinzutun, dann will ich damit die menge an schon berührenden flächen maximieren, denn nur dann kann ich versuchen zu erzwingen dass beim nächsten mal eine weitere farbe hinzugetan werden muss. Also verbinde ich farbe drei mit 1 und 2. Nun kommt farbe 4 die ich mit 1, 2 nud 3 verbinden muss. da 1, 2 und 3 ja schon ein "dreieck" ergeben, muss am ende ein graph dabei herauskommen bei dem 2 in der mitte liegt. Da diese farbe nun "unerreichbar" ist, kann ich sie "streichen" und beim jeden hinzufügen eines neuen knotenpunkte ergibt sich wieder die konstellation eines dreiecks, so dass ich für die äussere farbe die zuvor aus dem inneren entfernte nehmen kann. Wo ist hier der denkfehler? (nicht signierter Beitrag von 213.61.9.75 (Diskussion) 17:35, 16. Aug. 2011 (CEST))

Zum Abschnitt Bemerkung

"Nach dem Satz von Kuratowski gibt es nur genau zwei äußerst übersichtliche Graphen, die diese Eigenschaft zerstören können." Das ist nicht vollständig. Auch Unterteilungen des K4 und des K3,3 sind in einem planaren Graph nicht enthalten. (Schreibfehler: Im letzten Satz muss es heißen "K5", nicht "K4".--Anjolo (Diskussion) 10:42, 28. Sep. 2012 (CEST)) Außerdem ist der Satz merkwürdig formuliert. "Nur genau zwei" ist doppelt gemoppelt, denn "genau zwei" heißt schon "zwei und nur zwei". Und dann gehört die subjektive Wertung "äußerst übersichtliche" nicht in die objektive Existenzaussage. Gehörte sie nämlich dazu, dann gäbe es neben den "nur genau zwei äußerst übersichtlichen" noch weitere, weniger übersichtliche.

Ich würde die Sache so formulieren: "Nach dem Satz von Kuratowski gibt es bestimmte Untergraphen, die die Planarität von Graphen unmöglich machen. Es sind dies genau zwei Grundformen, der K4 und K3,3, und darüber hinaus ihre Unterteilungen." Vielleicht sollte dazu ein Bild einer einfachen Unterteilung eines der beiden Graphen ergänzt werden. (Ich würde diese Änderungen gerne selber anbringen, bin aber noch ziemlich neu hier und wage es nicht).

Wo ich gerade dabei bin, kann ich auch gleich weiter nörgeln: "Durch eine Wahl geschickter Datenstrukturen kann erreicht werden, ...". Ich habe noch nie geschickte Datenstrukturen kennengelernt. Werfen ungeschickte Strukturen ihre Teetassen um? Gemeint ist doch sicher: "Durch eine geschickte Wahl der Datenstruktur kann erreicht werden, ..."

Und dann kommt dieses Monstrum: "indem man jede Kante und jeden Knoten nur konstant oft betrachtet". Was, bitte, heißt das? "Betrachten": schön, ich schaue hin. Und dann? Ich schaue drei mal hin; ist das schon konstant oft? Also diesen ganzen Nebensatz streichen oder, besser, klären, was da gemeint ist, wenn das im Rahmen eines Enzyklopädie-Artikels sinnvoll ist.

Und zum Schluss noch eine Bitte. Øystein Ore stellt einem seiner Bücher (ich glaube The theory of graphs oder Graphs and their uses einen hübschen, etwas kryptischen Vers voran, den ich aber nicht mehr wörtlich im Kopf habe. Er lautet etwa so:

Who thought K4 and K3.3?

For those who thought ?????

Was nothing but planarity.

Hat jemand die Bücher zur Hand und kann mir helfen?--Anjolo 06:53, 26. Feb. 2012 (CET)

Ist nicht in seinen beiden Graphentheorie Büchern, aber wahrscheinlich meinst du sein Buch über das Vierfarbenproblem von 1967.--Claude J 09:25, 26. Feb. 2012 (CET)

Schade, aber vielen Dank für's Nachsehen--Anjolo 08:11, 28. Feb. 2012 (CET)

To KASIMIR KURATOWSKI
Who gave K5 and K3,3
To those who thought planarity
Was nothing but topology.

ist dem Buch "Graph Theory (1969)" von Frank Harary vorangestellt... Grüsse vom unsignierten Beiträger (nicht signierter Beitrag von 89.204.135.50 (Diskussion) 18:47, 7. Jan. 2013 (CET))

Danke für das Zitat. Frank Harary statt Oystein Ore und K5 statt K4. Da habe ich viele Fehler gemacht. Auch in meinem Beitrag davor muss überall K5 statt K4 stehen. Ich will das nicht nachträglich korrigieren.--Anjolo (Diskussion) 07:22, 11. Jan. 2013 (CET)

Noch einmal zum Abschnitt "Bemerkung"

Ich hatte im Abschnitt „Bemerkung“ den Nebensatz: „..., indem man jeden Knoten und jede Kante nur konstant oft betrachtet“ schon einmal gelöscht, weil er mir völlig unverständlich erscheint. Ich weiß nicht, was „konstant oft“ bedeuten soll, und ich weiß nicht, worauf man beim „Betrachten“ achten sollte. Jetzt hat Benutzer:0g1o2i3k4e5n6 den Satz wieder eingefügt mit der Begründung, „Dass man die Minoren *irgendwie* finden kann, liegt auf der Hand. Der Witz von der Aussage war, dass das mit Linearzeitmethoden geht.“ Dadurch wird der Satz oben nicht verständlicher und ich möchte ihn gerne wieder streichen. Aber dies rein, raus, rein, raus macht ja auch keinen Sinn. Also, lieber 0g1o2i3k4e5n6, bitte versuche doch, den tieferen Sinn des Satzes für schlichte Gemüter wie mich zu erläutern. --Anjolo (Diskussion) 10:31, 3. Okt. 2012 (CEST)

Worauf man beim Betrachten achten sollte, fällt dann schon unter die algorithmischen Details der Planaritätstests, die hier mMn gar nicht hin gehören. Trotzdem scheinen mir die algorithmische Grundidee – Das Suchen dieser Minoren – und die Ergebnisse von Interesse zu sein: Nämlich, dass man auf Planarität genauso schnell testen kann wie auf Zusammenhang oder Kreisfreiheit. --goiken 13:43, 3. Okt. 2012 (CEST).

Hi, goiken, Dank für Deine Antwort. Aber es bleibt dabei: der Satz ist unverständlich und muss 'raus. "konstant oft" ist eine sinnlose Konstruktion (Du versuchst ja auch gar nicht, sie zu erklären) und die Erklärung zum "Betrachten", wie Du sie hier gegeben hast, fehlt dem Leser des Artikels. Da es auch noch keinen Artikel zu Planaritätstests gibt, kann man auch nicht darauf verweisen. Es sei denn, Du schreibst selbst etwas dazu oder wir finden jemand, der das macht. Ich kann's nicht in endlicher Zeit, meine Beschäftigung mit der Graphentheorie (Diplomarbeit) liegt viel, viel zu lange zurück und über Literatur verfüge ich hier nicht so ohne Weiteres, es sei denn, Du nennst mir hilfreiche Titel. Mein Vorschlag: "Durch eine geschickte Wahl der Datenstrukturen kann man diese „Untergraphen“ finden bzw. feststellen, dass es sie nicht gibt. Dazu stehen relativ einfache Planaritätstests zur Verfügung". Na also, das ist doch eine Lösung: Du nennst mir Literatur und ich schreibe den Artikel, dann können wir aus den roten Planaritätstests blaue machen. Was hälst Du davon?--Anjolo (Diskussion) 18:36, 4. Okt. 2012 (CEST)

Die Formulierung ist mir letztlich gar nicht so wichtig: Ich fände halt noch eine Angabe zu der Laufzeit der Tests hilfreich. Dass wir uns von der Nichtexistenz eines Artikels davon abhalten lassen, darauf zu verweisen ist mir eigentlich neu. Mit der Floskel, dass die Tests mit jedem Knoten „konstant oft“ oft irgend etwas machen hab’ ich versucht zu sagen, dass für einen guten Test nur $c\cdot n$ Elemetaroperationen benötigt werden, wobei $c\in \mathbb {N}$ eine Konstante und $n$ die Anzahl der Knoten ist. Mit anderen Worten, es lassen sich Tests mit einer asymtotischen Laufzeit von ${\mathcal {O}}(n)$ angeben.

Ich weiß grad’ gar nicht, ob es dazu ein gutes Lehrbuch gibt. In der englischsprachigen WP gibt’s unter en:Planarity testing zumindest schon einmal einige Paper. In Adrian Bondy, U.S.R. Murty: Graph Theory (= Graduate Texts in Mathematics). 2008. Auflage. Springer, 2010, ISBN 1-84996-690-7.  findet man ein Kapitel zur Planarität einen einfachen Algorithmus (Sie geben die Laufzeit nicht explizit an, aber vom schnellen Draufschaun, sieht das erst mal langsamer aus, als ${\mathcal {O}}(n)$). --goiken 15:44, 5. Okt. 2012 (CEST)

Revert von Nutzer Mirer ohne vorherige Diskussion auf der Diskussionsseite

Wieso hat die weltweite Verkündung des Beweises des Vier-Farben-Satzes durch die Urheber des Beweises des Vier-Farben-Satzes keine Beziehung zu diesem Lemma Vier-Farben-Satz? Das erschließt sich mir leider nicht. Außerdem zeigte die Abbildung gar keine Briefmarke, sondern den Poststempel der Poststelle des Mathematischen Instituts der UIUC. --TeesJ (Diskussion) 06:47, 29. Nov. 2015 (CET)

Nutzer Mirer hat außerdem genauso <Frechheit/Unterstellung entfernt --mirer (Diskussion) 01:26, 30. Nov. 2015 (CET) > meine Präzisierung einer Bildunterschrift mitrevertiert. Was soll das eigentlich? <Frechheit/Unterstellung entfernt --mirer (Diskussion) 01:26, 30. Nov. 2015 (CET) > --TeesJ (Diskussion) 07:34, 29. Nov. 2015 (CET)

Immer mit der Ruhe. Der Poststempel ist als historisches Dokument auch in verschiedenen Büchern abgebildet, zum Beispiel dem (sehr guten) Aufsatz von Appel und Haken selbst zum Vierfarbenproblem in Steen "Mathematics today", Springer 1978, S. 154 (da ist es noch mit einer Umrahmung mit dem Zusatz "Announcement of success" versehen, was aber anscheinend nicht zum Poststempel gehört). Würde auch hier gut reinpassen.--Claude J (Diskussion) 08:28, 29. Nov. 2015 (CET)

Danke für den Kommentar. Diese Mehrfachfrankierung habe ich damals selber aus Urbana erhalten (siehe Datum). Wikipedia hatte das Dokument noch nicht. Ob man Deinen erweiterten Vorschlag aus den erwähnten Schriften einfach kopieren kann, weiß ich leider nicht. --TeesJ (Diskussion) 08:43, 29. Nov. 2015 (CET)

Vorweg wenn Du ernstgenommen werden möchtest, solltest Du die unverschämte Überschrift und die Unterstellungen im zweiten Beitrag ändern bzw. zurücknehmen. Diese Einfügung von Dir wurde bereits einmal rückgängig gemacht, daher der Hinweis auf die Disk und nicht eine stille Wiedereinfügung im Rahmen einer kleinen vermeintlichen Verbesserung. Das "irrelevant" in meiner Zusammenfassungszeile ist in der Tat falsch - gemeint war dass es als Artikelbild m. E. nicht taugt. Hier sollte selbstverständlich - wie bisher - eine Illustration des Problems stehen und nicht die Verkündung der Lösung per Poststempel. Ich finde das Bild nur an der Stelle unpasssend. --mirer (Diskussion) 17:52, 29. Nov. 2015 (CET)

<Frechheit/Unterstellung entfernt --mirer (Diskussion) 01:26, 30. Nov. 2015 (CET) > <Frechheit/Unterstellung entfernt --mirer (Diskussion) 01:26, 30. Nov. 2015 (CET) >, warum mein Beitrag bereits einmal revertiert worden ist, dann hättest Du gefunden: Der Artikel sei mit Bildern bereits überfrachtet. <Frechheit/Unterstellung entfernt --mirer (Diskussion) 01:26, 30. Nov. 2015 (CET) > Da ich beim Wiedereinfügen die Anzahl der Bilder konstant gehalten habe, entfällt wohl dieses Argument, logisch oder? Woher nimmst Du also das Recht, Dich als Vorwand für Deinen Revert auf diesen Revert zu beziehen? -- Dass Du die Einfügung des Poststempeldokuments als relevant, aber unpassend empfindest, ist Deine Privatmeinung, andere sehen es sicherlich anders. <Frechheit/Unterstellung entfernt --mirer (Diskussion) 01:26, 30. Nov. 2015 (CET) > Mit kollegialen Grüßen --TeesJ (Diskussion) 19:23, 29. Nov. 2015 (CET)

In dem Ton, in dem Du schreibst, kannst Du die "kollegiale Grüße stecken lassen. Ich werde Deine weiteren Unterstellungen nun selbst entfernen. Ansonstne bin ich hier raus, mit solchen Leuten diskutiere ich nicht. Artikelverschlechterungen werde ich weiter revertieren. Wenn Du einen Poststempel passender als eine inhaltliche Illustration des zugrundeliegenden Problems findest, dann ist wohl auch eine sachliche inhaltliche Diskussion überflüssig. --mirer (Diskussion) 01:26, 30. Nov. 2015 (CET)

Exklavenproblem

Ich arbeite gerade hobbymäßig an einer Variante, bei der eine Anzahl an Exklaven vorgegeben ist und ich - durch Gegenbeispiele, vielleicht später auch durch Beweise - zeigen will, wie viele Farben maximal notwendig sein können, um solche Karten zu färben. Zum Beispiel lassen sich mit 4 Exklaven bereits 8 Farben erzwingen (die trivial größtmögliche Anzahl Farben, die mit nur 4 Exklaven erzwungen werden kann: 4+4=8).

Mich wundert, dass das Exklavenproblem anscheinend nirgens behandelt wird - nicht hier und auch nirgendwo sonst. Ist das Problem etwa noch nie wirklich behandelt worden? 92.203.204.179 21:12, 23. Mai 2017 (CEST)

Wenn du Exklaven gestattest, machst du die Planarität des drunter liegenden Graphen kaputt. Du bist dann im allgemeinen Färbungsproblem. Dazu gibt es meterweise Literatur. --goiken 16:59, 24. Mai 2017 (CEST)

Ich finde da jetzt nichts zu einer Variante, bei der Gleichfarbigkeiten vorgegeben sind. Insofern wäre das Problem dann schon neu, oder? Oder wo muss ich suchen? 92.203.172.107 23:03, 25. Mai 2017 (CEST)

Halbkreise auf gemeinsamer Basis?

Was schließt denn aus, dass ich eine Landkarte aus Halbkreisen wie bei einem Regenbogen aufbaue und noch ein Land unten dran packe?

Jedes der "Regenbogenländer" berührt das "Basisland" und damit brauche ich so viele Farben wie Länder. --(nicht signierter Beitrag von 2A02:810A:1440:53A6:65DC:60F6:3576:6FB3 (Diskussion) 11:05, 26. Apr. 2018 (CEST))

Nein, denn der innerste Halbkreis berührt z.B. nicht den drittinnersten, so dass Du den drittinnersten mit der Farbe des innersten färben kannst. Ebenso berührt der zweitinnerste Halbkreis nicht den viertinnersten, so dass auch da die Farben gleich sein können. Insgesamt brauchst Du für den "Regenbogen" nur zwei Farben, die Du abwechselnd einsetzt, und dann eine dritte Farbe für das "Basisland". --Mark (Diskussion) 11:14, 26. Apr. 2018 (CEST)

Kandidatur auf WP:KALP im Januar 2020 (keine Auszeichnung)

 Exzellent Auch für Nicht-Mathematiker hervorragend dargestelltes Thema mit allem, was man sich wünscht: gute Abbildungen, klare Sprache, ein wenig Geschichte drumrum. Ein Artikel, den man gerne bis zum Ende liest, auch wenn man sich eigentlich nur kurz zum Thema informieren wollte. (nicht signierter Beitrag von ReiKi (Diskussion | Beiträge) 10.52, 13.01.2020)

 keine Auszeichnung Der Artikel ist als Einführung für Nicht-Mathematiker vielleicht nicht schlecht, aber auch weit davon entfernt, auszeichnungswürdig zu sein. Dafür müsste auf jeden Fall die Idee des Beweises dargestellt werden. Auch die Ideen der falschen Beweise von Kempe und Tait kann man dafür erwarten, ebenso wie eine Erklärung der Funktionsweise des Algorithmus. Davon abgesehen ist der Aufbau des Artikels mäßig. Der Abschnitt „Bemerkung“ sollte mit dem Abschnitt „Formalisierung“ zusammengeführt werden. Ein Abschnitt „Sonstiges“ gehört definitiv nicht in einen guten Artikel. Der Inhalt sollte, sofern relevant, in den Abschnitt Geschichte integriert werden. Die Auswertung der Literatur und die Angabe von Referenzen ist ebenfalls mäßig. Es gibt mehrere Monografien zu dem Thema, wirklich ausgewertet wurden die offensichtlich nicht. --Redrobsche (Diskussion) 19:32, 13. Jan. 2020 (CET)

 keine Auszeichnung Im wesentlichen wie eins drüber. Die Darstellung sollte mindestens auf dem Stand einer der allgemeinverständlichen Einführungen sein, wie Kenneth Appel, Wolfgang Haken, The four color problem, in: Lynn Arthur Steen (Hrsg.) Mathematics today, Springer 1978, S. 153-180, oder dem Scientific American Artikel der beiden von 1977, plus Ergänzungen zu den Entwicklungen seitdem. Dazu müssten eventuell aber auch neue Grafiken erstellt werden, falls noch nicht in commons.--Claude J (Diskussion) 11:48, 18. Jan. 2020 (CET)

Mit 1x  Exzellent und 2x  keine Auszeichnung bleibt der Artikel vorerst ohne Auszeichnung.
Übertragen von KALP durch --Krib (Diskussion) 18:13, 25. Jan. 2020 (CET)