Allgemein, Mathematik, Was ist...?

Was ist… der Vier-Farben-Satz?

Über den Vier – Farben – Satz wollte ich schon lange mal schreiben, heute ist es endlich so weit!

Die Aussage ist ganz einfach zu verstehen: Wie viele unterschiedliche Farben sind minimal nötig, um jede beliebige Karte einzufärben? Bedingung: Die Kanten von gleichfarbigen Ländern dürfen sich nicht berühren, Ecken schon.

Europakarte
Wie viele Farben braucht man minimal, um eine beliebige Karte einzufärben – ohne, dass gleichfarbige Bereiche sich an einer Kante berühren?

Der Name des Satzes gibt offensichtlich einen Spoiler… Es sind genau vier Farben!

Aber warum ist das so und warum ist der Beweis zu diesem Satz so besonders?

Fangen wir vorne an: Formuliert wurde die Vermutung, dass man minimal vier Farben bräuchte das erste Mal von Francis Guthrie. Guthrie war Jurastudent aus Südafrika und kam auf die Idee, als er eine Karte der englischen Grafschaften einfärbte. Er brauchte dafür nur vier Farben und vermutete, dass man jede beliebige Landkarte auf diese Weise einfärben könnte. Glücklicherweise war sein Bruder Frederick Mathematikstudent in London und gab die Frage an seinen Professor, den Mathematiker Augustus de Morgan weiter. Das war im Jahre 1852. De Morgan war sehr erstaunt, als er die Frage erhielt, stellte fest, dass er diese Vermutung noch nie gesehen hatte, sie auch nicht leicht zu beweisen war und gab sie an seinen irischen Kollegen William Hamilton weiter. Dieser probierte ebenfalls erfolglos, die Vermutung zu beweisen.

VierFarbenSatz - ungefaerbt

Einen signifikanten Fortschritt beim Beweis wurde 1890 von Percy Heawood gemacht. Heawood hatte im gleichen Jahr eine größere Lücke im vermeintlichen Beweis von Alfred Kempe von 1889 gefunden, die nicht leicht zu lösen war. Heawood gelang es dann aber, einen Beweis dafür vorzulegen, dass maximal fünf Farben zum Färben jeder beliebigen Landmarke nötig sind!

Ab da gab es immer mal wieder Fortschritte beim Beweis, aber der eine, schöne wurde erst einmal nicht gefunden… Philip Franklin konnte die Vermutung für eine Karte mit bis zu 25 Regionen 1922 beweisen. Es folgten Oystein Ore und Joel Stemple 1970 mit bis zu 39 Regionen und Jean Mayer konnte den Vier – Farben – Satz 1976 für bis zu 95 Regionen beweisen. In der Mathematik reicht es aber nicht, eine Vermutung für endlich viele Fälle zu beweisen und dann einfach zu glauben, dass der Rest schon auch gut gehen würde.

Ein Satz gilt nur als bewiesen, wenn er tatsächlich für ALLE Fälle und beliebig viele Regionen bewiesen ist.

VierFarbenSatz-gefaerbt

In den 1960er und 70er Jahren entwickelte der Mathematiker Heinrich Heesch einen Entwurf für einen Beweis mit Computerhilfe vor, da er keinen Zugang zu einem leistungsstarken Rechner hatte, konnte er ihn aber nicht umsetzen. Sein ehemaliger Student Wolfgang Haken wiederum konnte den Entwurf mit seinem Kollegen Kenneth Appel noch verbessern und reduzierten die zu überprüfenden Fälle auf 1936 – später sogar auf 1476. Diese Fälle konnten sie an der Universität von Illinois 1977 von einem Computer prüfen lassen, der bestätigte, dass alle Fälle der Vier – Farben – Vermutung entsprechen! Er brauchte dafür 1200 Stunden Rechenzeit! Es hagelte einige Kritik, nachdem, Appel und Haken ihren Beweis vorgestellt hatten, denn hier war der erste Computerbeweis der Mathematikgeschichte vorgelegt worden, was vielen Mathematikern nicht gefiel – und auch bis heute einigen Bauchschmerzen bereitet. Der Beweis wurde schließlich 1989 veröffentlicht unter dem Titel „Every planar map is four-colorable“, inklusive 400 seitigem Anhang auf Mikrofilm!

Inzwischen wurden noch weitere Bestätigungen durch Computerbeweise zu diesem Satz gebrbracht, beispielsweise 1996 von Neil Robertson, Daniel Sanders, Paul Seymour und Robin Thomas, die die zu untersuchenden Flle auf 633 reduzieren konnten. Oder auch 2005 durch Georges Gonthier und Benjamin Werner, die einen Beweis des Satzes mit dem Beweisassistenten Coq (der noch einen eigenen Artikel wert wäre?!) lieferten.

Ist ein Computerbeweis nun genauso viel wert oder genauso aussagekräftig, wie einer von Menschenhand?

Dazu gibt es sehr unterschiedliche Meinungen und es gibt – wie meist – gute und nachvollziehbare Gründe für beide Seiten: Pro Computerbeweis könnte man beispielsweise sagen, dass hier eben keinerlei Kreativität oder „inhaltliche Denkarbeit“ vom Computer gefordert wurde. Er hatte einen klaren und vor allem endlichen Auftrag, die eingegebenen Fälle wurden geprüft und das Ergebnis ausgegeben. Die theoretische Vorarbeit wurde von Menschen gemacht, das Überprüfen von Hand hätte nur einfach sehr lange gedauert. Contra Computerbeweis ist da immer eine Restunsicherheit: Wir Mathematiker haben gern zumindest theoretisch die Möglichkeit, jeden Schritt eines Beweises nachzuprüfen. Wenn der Computer einen wichtigen Teil davon übernimmt, wissen wir nicht, was genau da passiert, ob nicht doch irgendwo gerundet wurde oder ein anderer Fehler auftrat, der letztlich das Ergebnis verfälscht.

Was meint ihr? Seid ihr eher pro oder contra Computerbeweis?

~~~~~~~~~~~~~~~~~~~~~~~~~

Hamilton ist uns übrigens auch schon mal in anderem Kontext begegnet: Nach ihm ist der Hamiltonkreis benannt. Was das ist, erfahrt ihr HIER!
Francis Guthrie wurde übrigens später noch Professor für Mathematik in Kapstadt. Ob dieser Satz für den Fachwechsel mitverantwortlich war, weiß ich allerdings nicht.

Wie einige von euch wissen, betreibe ich schon seit einigen Jahren zwei Food Blogs, einer davon verfolgt das Konzept einer kulinarischen Weltreise und dort starte ich im Moment einen kleinen Re-Launch. Ihr findet dort jede Menge Rezepte aus aller Welt und entsprechende Buchtipps. Die Karte, die ich euch oben gezeigt habe, ist also ganz bewusst noch nicht fertig eingefärbt, denn jedes Land ird erst angemalt, wenn wir mindestens ein Rezept daraus getestet haben. Wer uns bei dieser Reise verfolgen möchte, klickt also gerne rüber auf den Blog!

~~~~~~~~~~~~~~~~~~~~~~~~~

Quellen & weitere Literatur:
Kenneth Appel, Wolfgang Haken (with the collaboration of J. Koch): Every Planar Map is Four-Colorable. In: Contemporary Mathematics. Band 98. American Mathematical Society, Providence, RI 1989
Der Creativity Code von Marcus du Sautoy – Meine Rezension zu diesem Buch findet ihr hier, kaufen könnt ihr das Buch beispielsweise hier.
Das Mathematik – Buch – Meine Rezension zu diesem Buch findet ihr hier, kaufen könnt ihr das Buch beispielsweise hier.
The Great Mathematical Problems von Ian Stewart – Wenn ihr eine Rezension zu dem Buch möchtet, hinterlasst mir einen entsprechenden Kommentar, kaufen könnt ihr das Buch beispielsweise hier.
Professor Stewart’s Cabinet of Mathematical Curiosities von Ian Stewart – Wenn ihr eine Rezension zu dem Buch möchtet, hinterlasst mir einen entsprechenden Kommentar, kaufen könnt ihr das Buch beispielsweise hier.

2 Gedanken zu „Was ist… der Vier-Farben-Satz?“

  1. Ich verstehe das so, dass Hamilton und Appel zeigten, dass die unendlich vielen Fälle durch endlich viele dargestellt werden konnten und haben diese dann mit dem Computer ausprobieren lassen. Da hat der Computer ja nur die Fleißarbeit übernommen.

    Vielleicht findet ja mal jemand einen eleganteren Beweis, das wäre vor allem: schöner.

    Gefällt mir

    1. Ja, genau: Es gibt nicht unendlich viele Kombinationen, sondern die beiden konnten zeigen, dass man nur eine endliche Zahl von Fällen durchschauen muss und diese Fleißarbeit wurde vom Computer übernommen.
      Deswegen wird der Beweis inzwischen auch bei den meisten anerkannt. Das Gegenargument ist halt immer nur, dass man nicht weiß, ob das Programm wirklich so arbeitet, wie es soll oder doch irgendwo rundet o.ä.

      Schöner wäre ein klassischer Beweis sicherlich, aber ich denke auch, dass der Beweis beim Vier-Farben-Satz schon korrekt sein wird. Inzwischen wurde er von den verschiedensten Programmen ebenfalls durchgerechnet und bestätigt.

      Gefällt mir

Ich freue mich auf deinen Kommentar!

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden /  Ändern )

Google Foto

Du kommentierst mit Deinem Google-Konto. Abmelden /  Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden /  Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden /  Ändern )

Verbinde mit %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.