Stern Mathematik: Das 4-Farben Problem
Released by matroid on Do. 05. Juni 2014 22:10:47 [Statistics]
Written by Ueli - 5927 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)

Einleitung

Oft ist es sehr viel leichter ein mathematisches Problem zu stellen, als es zu lösen. Dies gilt beispielsweise für die Goldbach Vermutung und auch für das 4-Farben Problem. Aber ist das Färben von Landkarten in irgendeiner Weise relevant für die Mathematik? Als David Hilbert im Jahr 1900 seine 23 ungelösten Probleme der Mathematik [1] vorstellte, dachte er, dass die Beschäftigung mit diesen Fragen die Mathematik voranbringen würden. In seiner Rede am zweiten internationalen Mathematikerkongress in Paris hat er auch zum Ausdruck gebracht, dass ein vollkommenes mathematisches Problem einfach zu fassen sein soll [2]. Dies gilt sicher auch (oder gerade) für das 4-Farben Problem. Dieses wurde allerdings nicht in die Liste der großen Probleme aufgenommen. Es schien wahrscheinlich zu isoliert in der mathematischen Landschaft zu stehen und die Lösung besteht auch nur in der einfachen Erkenntnis, dass die Vermutung richtig ist. In Hilbert's Nachlass wurde allerdings ein 24. Problem [3] gefunden. Darin geht es um die Kriterien für einfache Beweise und die Beziehung zwischen verschiedenen Beweisen für ein Problem. Dazu bietet der 4-Farben Satz ein lehrreiches Beispiel. Ausserdem war das 4-Farben-Problem oft Anlass für die Beschäftigung mit planaren Graphen und Topologie und hat daher diese Disziplinen weiter gebracht gemäß dem Stichwort: "Der Weg ist das Ziel". In diesem Artikel werde ich einige historische Versuche aufzeigen das Problem zu lösen und auch wesentliche Schritte, welche zur Lösung führten. [1]: Hilberts 23 Probleme: Wikipedia [2]: Hilberts Rede am Mathematiker-Kongress in Paris, S1-2: ps-Datei [3]: Hilberts 24. Problem: Wikipedia

Euler und die Polyederformel

Eines der wichtigsten Ergebnisse zur Lösung des Vier-Farben Problems hat Euler beigesteuert und dies obwohl das Problem damals noch gar nicht entdeckt war. Es ist der Polyedersatz, den Euler 1750 in einem Brief an Goldbach erwähnt hat. Den Satz soll allerdings auch schon Descartes gefunden haben. Demnach besteht die Beziehung: |E|-|K|+|F|=2 E bezeichnet die Ecken, K die Kanten und F die Flächen des Polyeders. Um die Formel etwas konkreter werden zu lassen, kann man sich zum Beispiel einen Würfel denken. Dieser hat 8 Ecken, 12 Kanten und 6 Flächen. Bei diesen platonischen Körpern ist der Satz schnell überprüft. Ein etwas komplizierteres Polyeder; ein Dodekaeder, bei dem die Ecken abgeschliffen sind zeigt das folgende Bild:
Polyeder Beim Zählen der Ecken und Kanten muss man hier schon gut aufpassen. Das Wort Polyeder ist etwas missverständlich. Man kann sich nicht konvexe Polyeder vorstellen, für die der Satz nicht gilt. Dazu nimmt man zum Beispiel ein beliebiges Polyeder und schneidet in einer Fläche ein Stück heraus.
Nicht konvexes Polyeder Bei diesem Körper funktioniert die Formel nicht. Um dies zu sehen stellen wir das räumliche Polyeder in der Ebene dar: \begin{tikzpicture}[scale=0.8, >=latex] \coordinate (A) at (0,0); \coordinate (B) at (10,0); \coordinate (C) at (10,8); \coordinate (D) at (0,8); \coordinate (A1) at (1,1); \coordinate (B1) at (9,1); \coordinate (C1) at (9,7); \coordinate (D1) at (1,7); \coordinate (A2) at (2,2); \coordinate (B2) at (8,2); \coordinate (C2) at (8,6); \coordinate (D2) at (2,6); \coordinate (A3) at (3,3); \coordinate (B3) at (7,3); \coordinate (C3) at (7,5); \coordinate (D3) at (3,5); \draw[thick] (A)--(B)--(C)--(D)--cycle; \draw[thick] (A1)--(B1)--(C1)--(D1)--cycle; \draw[thick] (A2)--(B2)--(C2)--(D2)--cycle; \draw[thick] (A3)--(B3)--(C3)--(D3)--cycle; \draw[thick] (A)--(A1); \draw[thick] (B)--(B1); \draw[thick] (C)--(C1); \draw[thick] (D)--(D1); \draw[thick] (A2)--(A3); \draw[thick] (B2)--(B3); \draw[thick] (C2)--(C3); \draw[thick] (D2)--(D3); \draw[dashed] (C1)--(C2); %\draw[->, thick] (O) -- (C) node[near start, above, sloped]{$\vec{a} + \vec{b}$}; %\draw[->, thick] (A) -- (B) node[near start, above, sloped]{$\vec{b} - \vec{a}$}; %\draw[densely dashed] (C) -- (B) node[midway, right]{$$}; %\draw[thin] (O) -- (A1) node[midway, right]{$$}; %\draw[] plot[mark=*, mark size=1.5pt, mark options={fill=white}] (0,0) node[]{$$}; %\draw[] plot[mark=*, mark size=1.5pt, mark options={fill=white}] (10,0) node[]{$$}; %\draw[] plot[mark=*, mark size=1.5pt, mark options={fill=white}] (10,8) node[]{$$}; %\draw[] plot[mark=*, mark size=1.5pt, mark options={fill=white}] (0,8) node[]{$$}; %\draw (0,0)--(10,0)--(10,8)--(0,8)--cycle; \end{tikzpicture} Nicht konvexes Polyeder, ebene Darstellung Obige geplättete Figur (ohne die gestrichelte Kante) hat 16 Ecken, 24 Kanten und 11 Flächen. Bei den Flächen ist zu berücksichtigen, dass die Bodenfläche des Polyeders zur Aussenfläche in der Ebene wird, also die entstandene Figur umschliesst. Dies führt zu einem ersten Kriterium um die Polyederformel anzuwenden: Die Aussenfläche des ebenen Graphen wird mitgezählt Wenden wir nun den Polyedersatz an: 16-24+11=3 Das ist offensichtlich falsch. Fügt man aber die gestrichelte Kante ein, so ergibt sich als Summe 2, wie vom Polyedersatz vorausgesagt. Diese Beobachtung führt zu einem weiteren Kriterium: Der Graph muss zusammenhängend sein

Beweisskizze

Um den Polyedersatz zu beweisen kann man mit einem einfachen Graphen beginnen und ihn induktiv erweitern. Da der Graph zusammenhängend sein muss, kann man einer Ecke eine Kante mit Endecke anfügen. Dies verändert die Bilanz nicht. Man kann sich nun leicht überlegen, was passiert, wenn man einen Kreis schliesst. Damit hat man bereits die zwei Möglichkeiten untersucht mit denen sich ein ebener Graph erweitern lässt und damit ist die Polyederformel verifiziert. \begin{tikzpicture}[scale=0.8, >=latex] \coordinate (A) at (0,0); \coordinate (B) at (-2,2); \coordinate (C) at (2,2); \coordinate (D) at (3,4); \coordinate (E) at (5,1); \coordinate (F) at (4,0); \draw[thick] (A)--(B)--(C)--cycle; \draw[thick] (C)--(D)--(E)--(F); \draw[dashed] (F)--(C); %\draw[->, thick] (O) -- (C) node[near start, above, sloped]{$\vec{a} + \vec{b}$}; %\draw[->, thick] (A) -- (B) node[near start, above, sloped]{$\vec{b} - \vec{a}$}; %\draw[densely dashed] (C) -- (B) node[midway, right]{$$}; %\draw[thin] (O) -- (A1) node[midway, right]{$$}; %\draw[] plot[mark=*, mark size=1.5pt, mark options={fill=white}] (0,0) node[]{$$}; %\draw[] plot[mark=*, mark size=1.5pt, mark options={fill=white}] (10,0) node[]{$$}; %\draw[] plot[mark=*, mark size=1.5pt, mark options={fill=white}] (10,8) node[]{$$}; %\draw[] plot[mark=*, mark size=1.5pt, mark options={fill=white}] (0,8) node[]{$$}; %\draw (0,0)--(10,0)--(10,8)--(0,8)--cycle; \end{tikzpicture} Zum Beweis der eulerschen Formel Im dritten Link unten gibt es eine ganze Liste von weiteren Beweisen:

Links

Zum Polyedersatz von trunx Polyedersatz (D) Beweise (E)

Das Vier-Farben-Problem

Tausende von verschiedenen Farben zu drucken ist heute kein Problem mehr. Wer sich schon einmal mit traditionellen Drucktechniken befasst hat weiss, dass früher jede zusätzliche Farbe einiges an Aufwand generiert hat. Vielleicht war dies ein Grund warum man auf die Idee kam eine Landkarte mit möglichst wenigen Farben zu färben. So fragte Frederick Guthrie 1852 seinen Professor De Morgan am University College in London, ob es immer möglich sei eine Landkarte mit vier Farben zu färben so, dass benachbarte Länder immer verschieden gefärbt sind. (Die Frage stammte allerdings ursprünglich nicht von Frederick selbst, sondern von seinem Bruder Francis). De Morgan schrieb an Hamilton, weil er es eine interessante Frage fand, doch Hamilton war an diesem Problem nicht interessiert oder er hat schnell erkannt, dass der Aufwand gross und der mathematische Ertrag eher klein sein dürfte. Auch De Morgan schrieb, dass es nicht einfach sei und er sich nicht sicher sei über mögliche Verwicklungen.
Francis Guthrie Das Problem wurde schnell verbreitet, nachdem es Cayley 1878 an einer Sitzung der Londoner Mathematischen Gesellschaft vorgestellt hatte. Ein Jahr später fand ein Rechtsanwalt einen vermeintlichen Beweis. Der Rechtsanwalt hiess Kempe und er ist damit Namensgeber für die Kempe-Ketten (Abwechselnd mit zwei Farben gefärbte Ecken auf einem Kantenzug). Sein Beweis wurde anerkannt und Kempe zum "Fellow of the Royal Society" gewählt. 1890 fand Heawood allerdings einen Fehler in der Beweisführung Kempes und stellte fest, dass der Beweis nur zeigte, dass man eine Landkarte mit fünf Farben in gegebener Weise färben kann. Kempes Beweis bildet trotzdem eine Grundlage für den späteren Computerbeweis und ist immer noch ein schöner Beweis für den Fünf-Farben-Satz.

Von der Landkarte zum Graphen

Betrachtet man eine Landkarte, so "sieht" man sofort einen Graphen. Dessen Kanten bestehen aus den Landesgrenzen und man bezeichnet ihn als Gerüstgraphen, im Bild links.
Gerüstgraph und dualer Graph Nebst dem Gerüstgraphen hat es sich als nützlich erwiesen den Dualen Graphen zu betrachten (rechte Seite der Graphik). Seine Ecken bestehen aus den Ländern (bzw. Flächen) und zwei angrenzende Länder sind durch eine Kante verbunden. Was wir hier betrachten sind ebene oder planare Graphen. (Die Begriffe werden hier gleichwertig verwendet. Manchmal wird nur die ebene Zeichnung eines planaren Graphen als ebener Graph bezeichnet.) Einfach gesagt gibt es bei einem ebenen Graphen keine unvermeidbaren Überkreuzungen der Kanten. Dies (die Planarität) sieht man einem Graphen aber nicht so einfach an, ausser er liegt in einer ebenen Zeichnung vor.

Von vier zu fünf Farben

In diesem Abschnitt gehe ich etwas genauer auf Kempes Beweis ein und warum aus dem "Vier-Farben-Satz" zunächst ein "Fünf-Farben-Satz" wurde.

Vorbereitung

Zunächst eine Definition: Eine Landkarte heisse normal, falls ihr Gerüstgraph (Graph mit den Grenzen als Kanten) zusammenhängend ist, weder Schlingen noch Brücken enthält und sich in jeder Ecke mindestens 3 Kanten treffen. Aus der Polyederformel kann eine Ungleichung abgeleitet werden, welche sich als sehr nützlich erweisen wird. Man betrachtet dabei den dualen Graphen, die Ecken entsprechen also den Ländern. Es handle sich um einen zusammenhängenden, einfachen ebenen Graphen (jedes Land hat mindestens 3 Grenzen): \sum_{v\in E} (6-d(v))\ge12 Dabei ist: v eine Ecke aus der Menge E aller Ecken im Graph d(v) ist der Grad einer Ecke, also die Anzahl der Kanten, welche von ihr weggehen. Daraus folgt sofort, dass jeder ebene Graph Länder mit höchstens 5 Grenzen haben muss. Ein Beweis steht zum Beispiel hier (Satz 4.62). Dieses Ergebnis wird für viele Beweise und Beweisversuche des Vierfarbensatzes verwendet.

Veranschaulichung

Obigen Satz kann man an einem Beispiel illustrieren. Auf den ersten Blick scheint es möglich eine Bienenwabe auf einer Kugel einzubetten, also so zu biegen, dass eine geschlossene Fläche entsteht. Dazu betrachten wir zunächst einmal einen Torus, welcher mit Sechsecken dekoriert werden kann:
Dekorierter Torus Um nun eine Kugel zu dekorieren habe ich ein Stück des Torus mit 3*6 Sechsecken ausgeschnitten:
Ausschnitt, um eine Kugel zu formen Versucht man nun die beiden Enden zu schliessen, so muss man immer Kanten zusammenlegen, so dass aus den Sechsecken am Rand Fünfecke entstehen. Es ist somit auch mit verbiegen der Sechsecke nicht möglich die Kugel zu dekorieren. Auch eine Art Deckel aus einem Sechseck auf die Enden zu legen ist nicht möglich.

Kempes "Beweis"

Wir betrachten kurz den zur Landkarte dualen Graphen: Der Beweis geht von der Tatsache aus, dass jeder ebene, einfache Graph eine Ecke vom Grad kleiner oder gleich 5 enthält. Nehmen wir wieder die Landkarte, so heisst das, dass es ein Land gibt mit höchstens 5 Nachbarländern. Alle Länder ausser dem betrachteten Land mit den fünf Grenzen seien bereits gefärbt. Der Beweis geht nun so, dass man einer gegebenen Landkarte mit N Ländern ein weiteres Land hinzufügt (nicht notwendigerweise mit 5 Nachbarn). Hat man alle möglichen Landkarten mit N Ländern bereits gefärbt, so kann man auch die Landkarte mit N+1 Ländern färben, indem man eine gefärbte Landkarte mit N Ländern wählt, in der ein (beliebiges) Land mit 5 Nachbarn fehlt. Dieses Land setzt man nun ein und färbt die Karte so um, dass eine Farbe für das neue Land übrig bleibt. Dem Beweis des Fünf-Farben Satzes wurden bereits Artikel hier auf dem Matheplaneten gewidmet z.B. hier. Kempes Beweis funktioniert also einwandfrei, solange man nur ein Land umfärben muss.

Fehler und Gegenbeispiel

Um eine Vier-Färbung zu erhalten, dürfen die fünf Nachbarn nur drei Farben enthalten. In der folgenden Karte hat Land 1 fünf Nachbarn (die graue Farbe soll anzeigen, dass Land 1 noch nicht gefärbt ist). Man könnte in diesem einfachen Beispiel nun einfach Land 6 rot färben und 9 blau. Dies ist aber bei einer komplexeren Karte nicht unbedingt möglich.
Karte Nehmen wir also an, wir müssten die beiden blauen Länder 2 und 4 umfärben. Dies müsste im Sinne von Kempes Beweis möglich sein, denn es gibt eine rot-weiss Kette und eine rot-grün Kette. Tauscht man die Farben von Gebiet 2 und 7, so hat man zwar die eine Hälfte der Aufgabe gelöst, aber da Gebiet 7 nun blau ist, lässt sich die Vertauschung von 4 und 8 nicht mehr durchführen (Gebiet 8, welches an 7 angrenzt würde auch blau gefärbt). Die Durchführung des 1. Schrittes kann also die Voraussetzung für den zweiten Schritt zerstören.
Ersetzen zweier Farben

Die weitere Verwendung von Kempes Beweisführung

Im Jahr 1890 deckte Heawood den Fehler in Kempes Beweisführung auf. Kempe erkannte seinen Fehler sofort. Heawood war nicht glücklich darüber dass er dieses negative Ergebnis gefunden hatte und bezeichnete seine Arbeit als destruktiv. Dieser persönlichen Einschätzung muss man aus heutiger Sicht aber widersprechen, denn Heawood hat immerhin gezeigt, dass eine 5-Färbung immer möglich ist. Heawood war es auch, der eine Formel für die chromatische Zahl für Flächen mit einem vom Null verschiedenen Geschlecht angab. So benötigt man beispielsweise bis zu 7 Farben um einen Torus zu färben. Nach vielen Versuchen das Vier-Farben-Problem auf andere Weise anzugehen, wurde Kempes Methode wieder aufgegriffen. Heinrich Heesch von der Universität Hannover legte ein Programm vor (im Sinne einer Vorgehensweise), welches dann auch tatsächlich zur Lösung führte. Neben ersten Computer-Teil-Beweisen in den 1960er Jahren wurden auch Teilgraphen (sog. Konfigurationen) mit Kempes Methode auf Vier-Färbbarkeit überprüft. Dies waren dann natürlich nicht einzelne Ecken vom Grad 5, sondern grössere Teilgraphen.

Vereinfachter Beweis für den 5-Farben Satz

Was den Beweis für die 5-Färbbarkeit angeht, habe ich mich gefragt, ob es nicht noch einfacher geht. Kempe hat im zweiten Beweisschritt gezeigt, dass man die äusseren Länder umfärben kann und wieder eine gültige Färbung erhält. Einfacher wäre es bei einem bestehenden planaren Graphen Ecken zusammenlegen zu können, also den Graphen zu reduzieren. Wie das geht, will ich an einer Ecke mit Grad 5 zeigen (Die Ecken stellen Länder dar, es handelt sich also um den dualen Graphen einer Landkarte):
Reduktion einer 5-Ecke Hier wurde also nicht die Färbung, sondern die Struktur des Graphen verändert. Ecke 3 und 5 wurden zusammengelegt und Ecke 0 gestrichen. Da man vier Ecken höchstens mit vier Farben färben kann, bleibt die fünfte Farbe für die mittlere Ecke 0 übrig.

Impulse

Das ungelöste Vier-Farben-Problem war für etliche Mathematiker der Anlass sich mit Graphentheorie zu befassen. Aus den vielen gewonnenen Erkenntnissen habe ich zwei Beispiele ausgewählt.

Plättbarkeit

Das Vier-Farben-Problem führt zu der Frage, was ein ebener Graph denn genau sei. Einer Zeichnung mit Kreuzungen sieht man oft nicht an, ob der Graph plättbar ist oder nicht. Die Untersuchungen zur Plättbarkeit führten zum bekannten "Satz von Kuratowski" (1930). Er besagt, dass ein Graph genau dann planar ist, wenn er gewisse Graphen nicht als Untergraphen enthält. (Genauer müsste es heissen: Enthält keine Unterteilung dieser Untergraphen, also auch nicht mit zusätzlichen Ecken. Ich wollte aber nicht zu viele Begriffe einführen.) Die nicht planaren Untergraphen heissen K_5 und K_{3,3}. \begin{tikzpicture} \coordinate (A2) at (2,0); \coordinate (B2) at (4,0); \coordinate (C2) at (4.8,1.4); \coordinate (D2) at (3,2.8); \coordinate (E2) at (1.2,1.4); \coordinate (F2) at (7,0); \coordinate (G2) at (9,0); \coordinate (H2) at (11,0); \coordinate (I2) at (7,3); \coordinate (K2) at (9,3); \coordinate (L2) at (11,3); \draw (A2)--(B2) circle(0.1); \draw (A2)--(C2) circle(0.1); \draw (A2)--(D2) circle(0.1); \draw (A2)--(E2) circle(0.1); \draw (B2)--(C2); \draw (B2)--(D2); \draw (B2)--(E2); \draw (C2)--(D2); \draw (C2)--(E2); \draw (D2)--(E2); \draw (A2) circle (0.1); \draw (F2)--(I2) circle (0.1); \draw (F2)--(K2) circle (0.1); \draw (F2)--(L2) circle (0.1); \draw (G2)--(I2); \draw (G2)--(K2); \draw (G2)--(L2); \draw (H2)--(I2); \draw (H2)--(K2); \draw (H2)--(L2); \draw (F2) circle (0.1); \draw (G2) circle (0.1); \draw (H2) circle (0.1); \end{tikzpicture} K_5 und K_{3,3} Oft sind diese Untergraphen "versteckt" und nicht gut zu erkennen. In der nächsten Graphik sind einige zusätzliche Ecken und Kanten zu einem K_{3,3} eingezeichnet. Diese ändern aber nichts daran, dass der Graph nicht planar ist. \begin{tikzpicture} \coordinate (A2) at (2,0); \coordinate (B2) at (4,0); \coordinate (C2) at (4.8,1.4); \coordinate (D2) at (3,2.8); \coordinate (E2) at (1.2,1.4); \coordinate (F2) at (7,0); \coordinate (G2) at (9,0); \coordinate (H2) at (11,0); \coordinate (I2) at (7,3); \coordinate (K2) at (9,3); \coordinate (L2) at (11,3); \draw (F2)--(I2) circle (0.1); \draw (F2)--(K2) circle (0.1); \draw (F2)--(L2) circle (0.1); \draw (G2)--(I2); \draw (G2)--(K2); \draw (G2)--(L2); \draw (H2)--(I2); \draw (H2)--(K2); \draw (H2)--(L2); \draw (F2) circle (0.1); \draw (G2) circle (0.1); \draw (H2) circle (0.1); \filldraw[blue] (7.8,0.6) circle (0.1); \filldraw[blue] (10.2,1.8) circle (0.1); \filldraw[blue] (10.2,0.6) circle (0.1); \draw[blue] (7.8,0.6)--(10.2,1.8); \draw[blue] (7.8,0.6)--(I2); \draw[blue] (10.2,0.6)--(10.2,1.8); \end{tikzpicture} Enthält K_{3,3} Man darf natürlich keine Ecken auf Kreuzungen, d.h. auf mehr als eine Kante legen und somit diese entfernen. Beim Beweis des Fünf-Farben-Satzes durch Zusammenlegen von Ecken könnte man versuchen nochmals zwei Ecken zusammenzulegen, um den Vierfarbensatz zu beweisen. Dabei erhält man aber die von Kuratowski beschriebenen nicht planaren Graphen. Es handelt sich also um ein topologisches Argument, wieso eine Ecke vom Grad 5 nicht reduziert werden kann.

Hamiltonkreise

Es wurden nach Kempe viele weitere Versuche unternommen die Vierfarben-Vermutung zu beweisen. Einen sehr schönen, aber leider nicht in jedem Fall zutreffenden "Beweis" für die Vier-Farben-Vermutung wird mit Hilfe von Hamilton-Kreisen konstruiert (Tait 1883). Die Bezeichnung "Hamiltonscher Graph" geht auf ein Spiel Hamiltons (1856) zurück, dem "Icosian Game". Im Spiel geht es darum auf einem Dodekaeder die Ecken mit einer geschlossenen Linie so zu verbinden, dass jede Ecke einmal besucht wird. "Icosian Game" Wir betrachten den Gerüstgraphen einer Landkarte, also den Graphen, dessen Kanten aus den Landesgrenzen bestehen. Ein Kreis, der alle Ecken genau einmal enthält ist ein Hamilton-Kreis. Durch einen Hamilton-Kreis wird der Graph in zwei disjunkte Kempe Ketten aufgeteilt. Die Färbung ist damit trivial. Im Bild sind die beiden Kempe-Ketten gestrichelt eingezeichnet.
Hamilton-Kreis
Anders, als in Taits Vermutung, hat nicht jeder ebene Graph (Genauer: jeder 3-reguläre polyedrische Graph) einen Hamilton-Kreis. Nach längeren Diskussionen brachte Tutte 1946 ein Gegenbeispiel: Tutte Graph. Damit wurde wieder ein neues Kapitel in der Graphentheorie aufgeschlagen, die Vier-Farben-Vermutung blieb aber nach wie vor ungelöst.

Birkhoff und Heesch; Die Vorbereitung zur Lösung

Die Birkhoff-Zahl

Kommen wir zurück zu Kempes Lösungsansatz. Das Programm, also den Lösungsweg für das Vier-Farben-Problem war im ursprünglichen Beweisversuch bereits gegeben. Der Beweis besteht aus zwei Teilen: 1. Suche eine Menge von unvermeidbaren Konfigurationen, welche in jedem ebenen Graphen enthalten sind. 2. Alle diese Konfigurationen müssen reduzierbar sein. Kempe fand die kleinste Menge: Je eine Ecke vom Grad 3, 4 oder 5. Was den zweiten Punkt betrifft so sind die Ecken vom Grad 3 und 4 reduzierbar, jedoch nicht die Ecke vom Grad 5. Nun galt es eine eine unvermeidbare Menge von Konfigurationen zu finden mit mehr als einer Ecke, welche alle reduzierbar sind. Birkhoff erstellte 1913 eine Liste von reduzierbaren Konfigurationen. Eine davon ist der Birkhoff-Diamant mit 10 Ecken: \begin{tikzpicture}[scale=0.8, >=latex] \coordinate (A) at (0,2); \coordinate (B) at (2,0); \coordinate (C) at (2,2); \coordinate (D) at (2,4); \coordinate (E) at (3,1); \coordinate (F) at (3,3); \coordinate (G) at (4,0); \coordinate (H) at (4,2); \coordinate (I) at (4,4); \coordinate (K) at (6,2); \draw[thick] (A)--(B)--(G)--(K)--(I)--(D)--cycle; \draw[thick] (C)--(F)--(H)--(E)--cycle; \draw[thick] (E)--(F); \draw[dashed] (A)--(C); \draw[dashed] (B)--(C); \draw[dashed] (D)--(C); \draw[dashed] (D)--(F); \draw[dashed] (I)--(F); \draw[dashed] (G)--(H); \draw[dashed] (K)--(H); \draw[dashed] (I)--(H); \draw[dashed] (B)--(E); \draw[dashed] (G)--(E); \draw (A) node[below] {$1$}; \draw (B) node[below] {$2$}; \draw (C) node[left] {$7$}; \draw (D) node[above] {$6$}; \draw (E) node[below] {$8$}; \draw (F) node[above] {$10$}; \draw (G) node[below] {$3$}; \draw (H) node[right] {$9$}; \draw (I) node[above] {$5$}; \draw (K) node[below] {$4$}; \begin{scope}[xshift=7.5cm, yshift=2cm] \draw [thick] (0,0)--(2,1.5)--(4,0)--(2,-1.5)--(0,0)--(6,0) circle(0.1]); \draw (0,0) node[below] {$1$}; \draw (2,-1.5) node[below] {$2$}; \draw (4,0) node[below] {$3$}; \draw (6,0) node[below] {$4$}; \draw (4,0) node[above] {$5$}; \draw (2,1.5) node[above] {$6$}; \end{scope} \end{tikzpicture} Birkhoff-Diamant original und reduziert
Die äusseren Ecken werden als Ring bezeichnet. Der Birkhoff-Diamant hat somit eine Ringgrösse von 6. Später erkannte man, dass die Ringgrösse mindestens 13 betragen musste. Eine Untersuchung auf Reduzierbarkeit ohne Computerhilfe ist somit ein sehr optimistisches Unterfangen. Die Birkhoff-Zahl ist die Zahl der Ecken, welche ein irreduzierbarer Graph mindestens haben muss. Bis 1950 lag diese Schranke bei b>=36. Doch dies war kein allzu ermutigendes Ergebnis. Man wusste somit nur, dass man alle Graphen mit b-1 Ecken Vier-färben kann. Einen gewissen Wert hat dieses Ergebnis aber trotzdem. Nehmen wir an in allen Graphen mit einer Eckenzahl E<=1 gibt es eine reduzierbare Konfiguration, dann wäre der Vierfarbensatz bewiesen. Man hatte somit zumindest eine untere Grenze für die Grösse der zu untersuchenden Konfigurationen.

Heinrich Heesch

Es war Heesch von der Universität Hannover, welcher die Suche nach einer unvermeidbaren Menge wieder aufnahm. Heesch leistete vor dem Krieg wichtige Beiträge zur Gruppentheorie und löste das reguläre Parkettierungsproblem der Ebene. Er schätzte dass eine unvermeidbare Menge reduzierbarer Konfigurationen aus einigen tausend Elementen bestehen würde. Um eine derartige Menge an Daten zu bearbeiten dachte er bereits an die Unterstützung von Computern. Das mag nun nach Brute-Force klingen. Doch das ist nicht der Fall. Es mussten sehr viel Vorarbeit geleistet werden, bis der Computer den buchhalterischen Anteil des Beweises übernehmen konnte. Vorläufig musste sich Heesch aber noch mit Hand- und Kopfarbeit begnügen. Er stellte sich zum Beispiel die Frage, ob man einer Konfiguration die Reduzierbarkeit "ansehen" konnte. Es würde die Suche natürlich stark vereinfachen, wenn man aussichtslose Kandidaten erst gar nicht untersuchen muss. Heesch untersuchte bekannte Konfigurationen und fand selbst auch neue, welche sich nicht reduzieren liessen. In einer unvermeidbaren Menge dürfen diese natürlich nicht vorkommen. Heesch fand Kriterien für nicht oder nur schwierig zu reduzierende Konfigurationen. Er nannte die kritischen Stellen "Obstruktionen". Von diesen gibt es 3 Arten. Die folgende Abbildung zeigt eine davon: \begin{tikzpicture}[scale=0.8, >=latex] \coordinate (A) at (3,0); \coordinate (B) at (5,0); \coordinate (C) at (7,1); \coordinate (D) at (8,3); \coordinate (E) at (8,5); \coordinate (F) at (7,7); \coordinate (G) at (5,8); \coordinate (H) at (3,8); \coordinate (I) at (1,7); \coordinate (K) at (0,5); \coordinate (L) at (0,3); \coordinate (M) at (1,1); \coordinate (X) at (4,2); \draw[thick] (A)--(B)--(C)--(D)--(E)--(F)--(G)--(H)--(I)--(K)--(L)--(M)--cycle; \draw[dashed] (X)--(M); \draw[dashed] (X)--(A); \draw[dashed] (X)--(B); \draw[dashed] (X)--(C); \draw (X) circle(0.1) node[above] {$X$}; \end{tikzpicture} Obstruktion
Die Ecke X im Inneren der Konfiguration hat mehr als 3 Kanten zu den Ecken des äusseren Kreises. Es ist offensichtlich, dass eine Färbung der vier Ecken mit vier verschiedenen Farben nicht möglich ist, da die Ecke X dann nicht mehr gefärbt werden kann. Heesch hatte festgestellt, dass eine von drei Obstruktionen in jeder nicht reduzierbaren Konfiguration vorkam, welche er untersucht hatte. Neben der Reduktion war die systematische Suche nach unvermeidbaren Mengen das zweite zentrales Thema. Auch hier fand Heesch eine entscheidende Verbesserung. Für einen irreduzibaren, maximalen, ebenen Graphen gilt bekanntlich (wie bereits weiter oben im Artikel aufgeführt): \sum_{v\in E} (6-d(v))=12 Dabei ist: v eine Ecke aus der Menge E aller Ecken im Graph d(v) ist der Grad einer Ecke, also die Anzahl der Kanten, welche von ihr weggehen. 6-d(v) nannte Heesch auch die Ladung der Ecke. Eine Ecke vom Grad 5 hat somit die Ladung 1 und damit als einzige Ecke eine positive Ladung. Eine 6-Ecke hat die Ladung 0, eine 7-Ecke -1 usw. Nach obiger Formel muss insbesondere die gesamte Ladung des Graphen grösser als Null sein. Es muss somit Konfigurationen geben mit positiver Gesamtladung. Eine 5-Ecke wird beispielsweise durch eine 7-Ecke in ihrer Ladung neutralisiert. Um eine systematische Suche nach unvermeidbaren Konfigurationen zu ermöglichen entwickelte Heesch sogenannte Entladungsalgorithmen. Sucht man beispielsweise nach einer unvermeidbaren Menge aus 2 benachbarten Ecken, so findet man zwei Konfigurationen mit einer Ladung grösser als 0, von denen eine immer vorkommen muss:
Unvermeidbare Menge
Man erkennt natürlich, dass die anderen Ecken auch keinen Grad grösser als 6 aufweisen sollten. Dann ist man aber bereits bei Konfigurationen mit 6 Ecken angelangt. Wie bereits gesagt hat Heesch den Computer genutzt, um Konfigurationen auf Reduzierbarkeit zu prüfen. Der einfachste Ansatz dafür besteht darin die äusseren Ecken einer Konfiguration auf alle möglichen Arten zu färben und zu testen, ob sich dann auch die inneren Ecken färben lassen. Obwohl Heesch einige Kriterien und optimierte Algorithmen fand, waren die Rechner damals einfach zu schwach, um alle Konfigurationen zu prüfen. Zudem standen die wenigen Computer, die es in den 60er Jahren an den Hochschulen gab, nicht jederzeit zur Verfügung. Dies waren Computer der zweiten Generation. Nach den Rechnern mit Röhren waren in diesen Geräten bereits diskrete Transistoren verbaut. Heinrich Heesch hat den Beweis des 4-Farben-Satzes weiter begleitet. Den Ruhm für seine Arbeit konnte er aber nicht einfahren. Wie es dazu kam ist im nächsten Kapitel beschrieben.

Der Beweis

Appel, Haken und IBM 370

Zwischen 1967 und 1971 reiste Heesch einige Male in die USA, wo leistungsfähigere Computer zur Verfügung standen. In Illinois war Wolfgang Haken 1965 zum Professor berufen worden. Die beiden, zusammen mit Yoshio Shimamoto, einem Nuklear Physiker und Informatiker, überprüften auf einem IBM System 360 mit 64kB Arbeitsspeicher einzelne Fälle und Algorithmen an kleinen Beispielen. Der Computer diente allerdings hauptsächlich der Universitätsverwaltung und ich nehme an, dass Heesch und Haken ihn nur sporadisch nutzen konnten. Heesch wurde dabei von der Deutschen Forschungsgesellschaft unterstützt, die dann aber die Gelder für das Projekt strich, welches sich nun in der entscheidenden Phase befand. Im Nachhinein betrachtet war dieser Entscheid falsch und unfair gegenüber Heinrich Heesch. In der damaligen Zeit stiessen Computer aber noch nicht auf breite Akkzeptanz und was wir heute "Experimentelle Mathematik" nennen, war zu jener Zeit noch unvorstellbar. Dazu möchte ich noch eines der vielen berühmten Zitate zur Fehleinschätzung des Computers anfügen:
"Ich habe das ganze Land bereist und mit allen Experten gesprochen, und ich sage Ihnen: Datenverarbeitung ist ein Modefimmel, der nicht einmal das Jahr überstehen wird." (ein Lektor für Wirtschaftsbücher beim Verlag Prentice Hall, 1957)

Dieses und weitere Zitate findet man zum Beispiel hier.

Heesch war 1972 also wieder zurück in Deutschland. Yoshio Shimamoto arbeitete weiter am Vier-Farbenproblem und veröffentlichte auch einen Beweis, welcher sich aber als fehlerhaft herausstellte. Haken fand in Kenneth Appel und John A. Koch neue Partner, um das Projekt weiter zu führen. Um die Grössenordnung des Problems abzuschätzen kann man sich überlegen, wie viele grundsätzlich verschiedene Färbungen ein Ring, also der äussere Kreis einer Konfiguration, haben kann. In der folgenden Tabelle steht unter der Ringgrössen die Anzahl der möglichen Färbungen.

n 10 11 12 13 14 15
j_n 2461 7381 22144 66430 199291 597871

Im Beweis wurden vor allem Konfigurationen mit Ringgrösse 14 verwendet, also müssten ohne Vereinfachungen für jede der knapp 2000 Konfiguration bis zu 200000 Färbungen untersucht werden. Wenn alle Färbung eines Ringes auf das innere der Konfiguration fortgesetzt werden können, dann ist die Konfiguration trivialerweise reduzierbar. Im Normalfall ist das aber nicht der Fall. Dann kann man aber immer noch oft zum Erfolg kommen, indem man einen Kempe-Austausch durchführt. Eine dritte Möglichkeit besteht darin Teile der Konfiguration direkt zu reduzieren, also Ecken zu entfernen und somit auch die Auswahl der Färbungen zu reduzieren.

Im Jahr 1975 waren die grundlegenden Vorbereitungen abgeschlossen. Mit den Rechnern IBM 370-158 und IBM 370-168 (IBM370) standen ein Jahr später auch leistungsfähigere Computer zur Verfügung. Aus den heuristischen Überlegungen erwartete man, dass mit hoher Wahrscheinlichkeit Konfigurationen mit Ringgrösse 13 oder 14 genügten. Damit waren die Vorraussetzungen geschaffen, um das Projekt mit guten Erfolgsaussichten zu Ende zu bringen. Appel, Haken und Koch machten sich nun daran ihre Suchalgorithmen zu optimieren und laufend den neuen Ergebnissen anzupassen. Mit den Entladungsalgorithmen wurden unvermeidbare Konfigurationen gefunden. Falls deren Ringgrösse über 14 lag, wurden sie ausgeschlossen. Falls die Konfiguration keine Obstruktionen enthielt, also "wahrscheinlich reduzierbar" war, wurde die Reduzierbarkeit getestet. Für die Überprüfung der Reduktion setzte man dem Computer Zeitlimiten (je nach Computer 30-90Minuten). Rund 10000 Teilkonfigurationen wurden von Hand analysiert und vom Januar bis zum Juni 1976 etwa 2000 Konfigurationen mit der Maschine auf Reduzierbarkeit getestet. Schliesslich fand man eine unvermeidbare Menge von 1936 reduzierbaren Konfigurationen.

Im Juni 1976 war der Beweis vollbracht.

Fortsetzung

Appel und Haken konnten in der folgenden Zeit die Anzahl der unvermeidbaren Konfigurationen noch auf 1405 vermindern.
Der Beweis wurde aber nicht von allen Seiten freudig aufgenommen.
Auf der einen Seite fehlt die Eleganz, bzw. das grosse Aha-Erlebnis. Obwohl Heesch und Haken wichtige Beiträge zu Topologie und Gruppentheorie geleistet hatten, war im Beweis wenig davon zu finden. Es ist ein Beweis durch "Abzählen". Die einzelnen Abzählmethoden sind zwar teilweise trickreich oder ausgefeilt, aber es fehlt die theoretische Klammer um das Ganze. Ein Beweis, wie beispielsweise der Versuch mit den Hamiltonkreisen, wäre in dieser Hinsicht sicher befriedigender gewesen.
Ein weiterer Einwand wiegt meiner Ansicht nach schwerer: Ich nehme an, dass niemand den Beweis vollständig überprüft hat. Salopp gesagt: Der Beweis ist einfach zu lang, um fehlerlos zu sein. Wer hat schon Interesse oder die Zeit ein derartiges Monumentalwerk zu überprüfen. Zu jener Zeit war man noch eher misstrauisch bei den Beweisteilen, die der Computer übernahm. Es stellte sich aber heraus, dass die Handarbeit viel fehleranfälliger war. Was der Computer übernahm, waren die Teile, welche man durch einfache Algorithmen mit kleinen Teilschritten durchführen konnte. Dies kann eine Maschine ausserordentlich zuverlässig erledigen. Die Teile jedoch, welche von Hand durchgeführt wurden benötigten viel mehr Fallunterscheidungen und Zusatzüberlegungen. Man konnte zwar davon ausgehen, dass man alle Fehler beseitigen könnte ohne den Beweis zu gefährden, aber eine 100% Sicherheit dafür gab es natürlich nicht.
In der Zwischenzeit gibt es mehrere unabhängige Überprüfungen und Verbesserungen des Beweises. Das Argument der Überprüfbarkeit sticht also nicht mehr. So konnte Neil Robertson 1995 mit einem Ansatz von Heesch die Anzahl der unvermeidbaren Konfigurationen auf 633 senken. Das Team arbeoitet immer noch an Vereinfachungen: hier.
Damit sind wir in der Mathematik an einer Stelle angelangt an der man in den anderen Naturwissenschaften schon länger ist. Die direkte Überprüfung sehr kleiner oder sehr grosser Strukturen allein mit unseren menschlichen Sinnen ist oft nicht mehr möglich.
Ist ein Beweis "von Hand" also nicht möglich? Diese Frage bleibt vorerst noch offen. Man kann sich aber einige Überlegungen dazu machen:
- Bei einem Beweis durch die Untersuchung von unvermeidbaren Konfigurationen muss man immer einige 100 Konfigurationen untersuchen.
- "Beweise", welche nur an kleineren Beispielen demonstriert werden sind im allgemeinen falsch oder unvollständig.
- Ein "kurzer" Beweis muss weg von den konkreten Färbungen, also Abzählungen vermeiden.

Die Beweismaschine

Der Computerbeweis war so etwas wie der Sputnik-Schock für die Bleistift und Papier-Mathematiker. Doch wo stehen wir heute? Seit 1976 sind einige Jahre vergangen. Sprach man damals ehrfürchtig von "Höchstleistungscomputern" oder "Elektronengehirnen", so dass kaum noch eine Steigerung möglich erschien, so ist heute doch schon der Computer im Kinderzimmer 1000 mal leistungsfähiger. Um nochmals zu Sputnik zurückzukehren: Damals nahm man an, dass man im Jahr 2000 Kolonien auf dem Mond und dem Mars errichten würde. Ebenso wenig, wie es diese Kolonien heute gibt, wurden die Mathematiker durch Maschinen ersetzt, auch wenn die Computer heute viel leistungsfähiger sind, als man sich damals erträumt hatte. Allerdings wurden die Computer immer mehr zu einem unentbehrlichen Hilfsmittel. Am französischen Institut INRIA (vielleicht einigen bekannt, als Herausgeber des CAS scilab) wurde die Software Coq entwickelt. (Coq oder Gockel auf Deutsch sollte nicht mit dem gleichnamigen Matheplanet-Mitglied verwechselt werden). Mit Hilfe dieser Sprache konnte Gonthier und Werner im Jahr 2005 den Vier-Farben-Satz überprüfen. Bei Appel und Hakens Beweis wurde kritisiert, dass der Compiler fehlerhaft sein könnte. Diese Bedenken muss man bei Coq nicht mehr haben. Dieser Compiler ist auf Unfehlbarkeit hin zertifiziert, also so etwas wie der Papst unter den Programmiersprachen. Wer es selbst überprüfen will kann die Software gratis herunter laden: download. Das mit der Unfehlbarkeit bezieht sich anscheinend nicht auf jedes feature, denn auf der Webpage steht:".. many bug fixes and improvements..". Wie dem auch sei, mit Coq ist der Beweis der 4-Farben Vermutung verifiziert worden. Obwohl von einem übersichtlichen Beweis gesprochen wird, habe ich meine Zweifel, dass man ihn mit Bleistift und Papier nachvollziehen kann. Das eigentliche Betätigungsfeld solcher Software soll zukünftig in der Überprüfung von Software liegen. Übliche Zertifizierungen für Software im sicherheitsrelevanten Bereichen beruhen auf Faustregeln und Redundanz. Die geforderten Tests sprengen das Budget mancher Entwicklung. Es wäre somit sehr hilfreich Software automatisiert prüfen zu können, ohne etwas zu vergessen. Aber auch in der Mathematik möchte man weitere Beweise überprüfen. Aktuell arbeitet Gonthier an den Klassifikationstheoremen endlicher Gruppen. Dabei handelt es sich um Beweise im Umfang von ca. 15000 Seiten. Wie weit der Computer selbständig arbeitet, kann ich allerdings nicht sagen.

Links und Literatur

Eine ausführliche historische und mathematische Herleitung des Problems findet sich in diesem Buch: M.Aigner "Graphentheorie, Eine Entwicklung aus dem 4-Farben Problem" Teubner 1984 ISBN 978-3-519-02068-4 Das Buch ist zwar vergriffen, kann aber (Digitaldruck sei Dank) nachbestellt werden. Ein eingescanntes Buch der Bibliothek der Uni-München kann als pdf geladen werden: Rudolf Fritsch Eine kurze Zusammenfassung findet sich bei Wolfram: Mathworld Vielleicht kann man mit dem 4-Farben-Satz auch Higgs erklären: hier
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: automatisch eingefügt und unbearbeitet :
Das 4-Farben Problem [von Ueli]  
http://www.matheplanet.com/matheplanet/nuke/html/uploads/9/4004_island_landkarte_regionen.png EinleitungOft ist es sehr viel leichter ein mathematisches Problem zu stellen, als es zu lösen. Dies gilt beispielsweise für die Goldbach Vermutung und auch für das 4-Farben Problem. Aber ist das Färben vo
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 5927
 
Aufrufstatistik des Artikels
Insgesamt 1312 externe Seitenaufrufe zwischen 2014.06 und 2021.11 [Anzeigen]
DomainAnzahlProz
https://google.com181.4%1.4 %
https://google.at20.2%0.2 %
https://duckduckgo.com201.5%1.5 %
https://www.startpage.com90.7%0.7 %
https://google.de77358.9%58.9 %
https://google.ch10.1%0.1 %
https://matheplanet.com10.1%0.1 %
http://google.de24018.3%18.3 %
https://google.lu493.7%3.7 %
https://www.bing.com352.7%2.7 %
https://google.pt251.9%1.9 %
http://google.it231.8%1.8 %
http://google.pl181.4%1.4 %
http://google.nl161.2%1.2 %
http://images.google.de100.8%0.8 %
https://www.ecosia.org110.8%0.8 %
http://google.fr110.8%0.8 %
http://google.com40.3%0.3 %
http://suche.t-online.de50.4%0.4 %
http://int.search.myway.com40.3%0.3 %
http://google.ch20.2%0.2 %
http://r.duckduckgo.com20.2%0.2 %
http://www.bing.com171.3%1.3 %
http://192.168.10.1:191010.1%0.1 %
https://metager.de10.1%0.1 %
http://yandex.ru40.3%0.3 %
https://bing.com10.1%0.1 %
http://192.168.11.253:191010.1%0.1 %
http://www.etools.ch10.1%0.1 %
http://cn.bing.com10.1%0.1 %
https://startpage.com10.1%0.1 %
https://nortonsafe.search.ask.com10.1%0.1 %
http://google.ca10.1%0.1 %
http://suche.web.de10.1%0.1 %
http://int.search.tb.ask.com10.1%0.1 %
https://eu.startpage.com10.1%0.1 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 23 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2021.11.07-2021.11.26 (16x)https://google.com/
2021.11.26 12:24https://google.at/
2021.11.23-2021.11.24 (3x)https://duckduckgo.com/
2021.11.12-2021.11.24 (2x)https://google.com
2021.11.23 17:17https://www.startpage.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 1215 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2021 (509x)https://google.de/
2020-2021 (259x)https://google.de/url?sa=t
2014-2018 (186x)http://google.de/url?sa=t&rct=j&q=
202103-03 (49x)https://google.lu
2020-2021 (32x)https://www.bing.com/
202010-10 (25x)https://google.pt
201503-03 (23x)http://google.it/
201501-01 (22x)http://google.de/url?sa=t&source=web&cd=11&ved=0CDgQFjAK
201505-05 (18x)http://google.pl/url?sa=i&rct=j&q=
2020-2021 (16x)https://duckduckgo.com/
201411-11 (16x)http://google.nl/search?q=vierfarbenproblem bei einem land mit fuenf nachbarl...
201502-02 (14x)http://google.de/url?sa=t&rct=j&q=vier-farben-satz
201412-12 (12x)http://google.de/url?sa=t&rct=j&q=vier-farben-satz würfel
2016-2017 (10x)http://images.google.de/url?sa=t&rct=j&q=
2020-2021 (10x)https://www.ecosia.org/
201511-11 (8x)http://google.fr/url?sa=t&rct=j&q=
2020-2021 (6x)https://www.startpage.com/

[Top of page]

"Stern Mathematik: Das 4-Farben Problem" | 3 Comments
The authors of the comments are responsible for the content.

Re: Das 4-Farben Problem
von: Gockel am: Do. 05. Juni 2014 22:54:49
\(\begingroup\)Hi Ueli. \quoteon Aktuell arbeitet Gonthier an den Klassifikationstheoremen endlicher Gruppen. Dabei handelt es sich um Beweise im Umfang von ca. 15000 Seiten. Teilweise wurden diese Beweise auch mit Computerhilfe erstellt und sind damit kaum von Hand nachvollziehbar. \quoteoff Das stimmt so nicht. Dass der Beweis schwer nachvollziehbar ist, liegt an der dahinterstehenden Mathematik und dem schieren Umfang des Gesamtprojekts, aber eigentlich nicht an den computerisierten Anteilen. Es ist nicht so, dass der Beweis des Klassifikationssatzes plötzlich total einfach (oder auch nur mittelschwer) würde, wenn man die Computeranteile durch ein cleveres Argument oder eine händische Konstruktion ersetzen könnte (was in einigen Fällen in der Tat passiert ist). Er bliebe weiterhin unüberschaubar groß und verwickelt. Da kann nur eine komplette Neufassung des Beweises Abhilfe schaffen, wie sie einige Arbeitsgruppen (z.B. die Gruppe um Prof. Stroth in Halle) ja auch versuchen. Dazu kommt, dass die Computerbeweise an einigen Stellen wirklich nur triviale Rechnungen durchführen, die man einfach nicht von Hand machen will. Die Computerbeweise im Klassifikationsprojekt sind verglichen mit anderen Computerbeweisen ziemlich einfach nachzuvollziehen und inzwischen auch in vielen Fällen schon durch händische Beweise ersetzt worden. Dabei ging es sehr oft um die konkrete Konstruktion einer zuvor vorhergesagten sporadischen Gruppe mit bestimmten Eigenschaften. Dabei war eine Schwierigkeit etwa, zu beweisen, dass eine z.B. durch einen Satz von Erzeugern gegebene Matrixgruppe über einem endlichen Körper tatsächlich die geforderten Eigenschaften hat, also die richtige Ordnung besitzt, die richtige Charaktertafel besitzt, eine Involution mit dem richtigen Zentralisator besitzt usw. Diese Berechnungen sind nicht grundlegend schwer. Wenn man nicht auf Speicherplatz und Rechenzeit achten müsste, wären sie sogar ziemlich trivial. Der nichttriviale Anteil liegt darin, effiziente Algorithmen für diese Aufgaben zu finden. Solche Algorithmen gibt es aber und ihr Verständnis ist nicht grundlegend schwer. Es ist halt ein Mindestmaß von der Theorie notwendig, für die man diese Algorithmen hinterher auch einsetzen will, aber das ist ja nicht so überraschend. Diese Theorie wäre genauso für einen handgeschriebenen Beweis notwendig (wenn nicht noch mehr). Ein anderes bekanntes Teilproblem war die Berechnung der Charaktertafel der Monstergruppe, deren Existenz zu diesem Zeitpunkt nur vermutet wurde. Man konnte also nicht mit expliziten Gruppenelementen rechnen, weil man die Gruppe dazu noch nicht zur Verfügung hatte. Die Tafel ist außerdem sehr groß (aber nicht unmöglich groß. Ausgedruckt nimmt sie eine zweistellige Anzahl von Seiten in Anspruch, wenn ich mich erinnere) das macht Computerhilfe wünschenswert. Außerdem will man die Rechnungen nicht von Hand machen, weil sie fehleranfällig sind und ein Vorzeichen an der falschen Stelle bei diesen Sachen wirklich sehr, sehr stört. Ein immer wiederkehrender Schritt ist z.B. einen Vektor eines $\mathbb{C}^n$ nach einer (partiell vorhandenen) ONB zu zerlegen. Das ist absolut trivial, aber man macht es trotzdem mit einem Computer, weil es von Hand zu fehleranfällig wird. Genauso mit anderen Standardkonstruktionen. Dies einen Computerbeweis zu nennen, ist eigentlich schon fast gelogen. Die eigentliche Arbeit steckt hier nicht in den Computerrechnungen, sondern in den dazugehörigen Beweisen, dass diese und jene Konstruktionen wirklich neue Charaktere erzeugen. Außerdem kann man, wenn man wirklich will, für einige dieser Aufgaben auch Algorithmen designen, die nicht nur die notwendige Berechnungen durchführen, sondern auch Zertifikate für die Richtigkeit des Ergebnisses liefern, sodass man, wenn man dem Rechner partout nicht glauben will, nur noch das Zertifikat von Hand überprüfen muss, um zu wissen, dass das Ergebnis stimmt. So weit kann man aber meines Wissens noch nicht bei allen sporadischen Gruppen gehen. Speziell Monster und Babymonster machen selbst der besten Hardware große Probleme, wenn man Standardalgorithmen verwenden will. Diese Gruppen kann man wirklich nur mit spezialisierten Tools attackieren. mfg Gockel.\(\endgroup\)
 

Re: Das 4-Farben Problem
von: Ueli am: Di. 10. Juni 2014 22:20:02
\(\begingroup\)Hallo Gockel, danke für deine Ergänzungen. Ich habe die Textzeile entsprechend angepasst. Ich gehe mal davon aus, dass die Computer am INRIA mehr machen, als nur abzählen. Auf der anderen Seite werden sie wohl auch nicht sehr selbständig ans Werk gehen. Gruss Ueli \(\endgroup\)
 

Re: Das 4-Farben Problem
von: MontyPythagoras am: Sa. 21. Juni 2014 11:19:54
\(\begingroup\)Hallo Ueli, ein sehr interessanter Artikel. Was wie ein Aufsatz über ein "einfaches" geometrisches Problem anfängt, endet in einer beinahe philosophisch anmutenden Diskussion über den Nutzen von Computerbeweisen. Betrachtet man das Ganze aus der "Vogelperspektive", dann fällt einem auf, finde ich zumindest, dass die Menschheit vor einem großen Wandel zu stehen scheint, so ähnlich wie schon einmal vor wenigen Tausend Jahren. Bis dahin hatten die Menschen nur einfache Werkzeuge, alles was sie taten, wurde durch ihre eigene Muskelkraft angetrieben, oder bestenfalls durch domestizierte Zossen. Ein Mensch leistet auf Dauer kaum mehr als 150W, Topsportler kommen auf 450W Ausdauerleistung. Mehr schafft ein Herz einfach nicht. Betrachtet man heute die technischen Errungenschaften, so bestand ihr Nutzen häufig darin, die (körperliche) Leistungsfähigkeit eines Menschen bei weitem zu übertreffen. Wir haben heute Maschinen im weitesten Sinne, deren Leistungsfähigkeit im Megawatt- oder bei Kraftwerken sogar im Gigawattbereich liegt. Das sind Multiplikatoren, die die Vorstellungskraft eines Menschen vor nur etwa 1000 Jahren gesprengt hätten. Trotzdem sind sie für uns heute selbstverständlich und kein Mensch, auch nicht der weltgrößte Bodybuilder auf Steroiden, würde ernsthaft glauben, dass irgendetwas davon wieder durch Muskelkraft zu ersetzen wäre. Andererseits betrachten wir unser Gehirn als etwas besonderes, wo es doch eigentlich auch nur ein "Muskel" ist, wenn auch nicht im medizinischen Sinne, so doch im metaphorischen. Es ist noch nicht lange her, dass Menschen behauptet haben, ein Computer würde niemals (!) einen Menschen im Schach schlagen können. Das ist an sich schon ein Witz, denn 99% der schachspielenden Menschheit wird schon jetzt von kostenlosen Schachprogrammen auf Handys geschlagen. Der Durchbruch, vor dem wir stehen, ist, dass die Computer unser Gehirn als Werkzeug ablösen. So wie ein Kranführer zwar auch noch die Muskelkraft seiner Hände benötigt, um den Kran zu bedienen, so wird in Zukunft auch noch das menschliche Gehirn benötigt, um die Grundfunktionen, die "Bedienung" zu übernehmen, während die Computer die eigentliche "Denkarbeit" übernehmen. Vor 2000 Jahren passten mathematische Beweise auf eine Din A4-Seite (oder ein durchschnittliches Papyrusblatt), im letzten Jahrhundert waren es schon zig oder hunderte von Seiten. Mathematische Beweise werden immer komplexer und werden ein Level erreichen, den das menschliche Gehirn überhaupt nicht mehr fassen und überblicken kann, oder nur mit gigantischen Mühen in winzigen Einzelschritten. So wie die Ägypter mit Hunderten von Menschen in tagelanger Arbeit einen einzelnen Felsquader auf die Pyramide gehievt haben, was heute ein Kran in Minuten mühelos wuppen würde. Klingt ein bisschen nach Terminator und Skynet, aber es muss ja nicht immer in der Apokalypse enden. Aber der Schritt ist als nächster nur logisch. Ciao, Thomas \(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]