English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGraphen und NetzwerkeKarten färben
Wir haben die Graphentheorie bereits bei verschiedenen Landkarten angewendet. Wenn wir herauszoomen, verschwinden einzelne Straßen und Brücken und wir sehen stattdessen den Umriss ganzer Länder.
Beim Einfärben einer Karte - oder jeder anderen Zeichnung, die aus verschiedenen Regionen besteht - dürfen benachbarte Länder nicht die gleiche Farbe haben. Außerdem sollten wir so wenig verschiedene Farben wie möglich verwenden.
Einige einfache "Karten", wie ein Schachbrett, brauchen nur zwei Farben (schwarz und weiß), aber die meisten komplexeren Karten brauchen mehrere.
Wenn man die Karte der US-Bundesstaaten einfärbt, dann sind natürlich 50 Farben ausreichend, aber es sind weit weniger notwendig. Versuche die Karten unten mit so wenig Farben wie möglich einzufärben:
Vereinigte Staaten
Südamerika
Deutschland
England
Alle diese Karten können mit nur vier verschiedenen Farben eingefärbt werden, aber es ist nicht schwer, sich vorzustellen, dass andere, sehr komplizierte Karten viel mehr Farben benötigen. Tatsächlich brauchen manche Karten mindestens vier Farben, wenn sie vier Länder enthalten, die alle miteinander verbunden sind.
Wie zuvor können wir eine Karte mit Ländern und Grenzen in einen planaren Graphen umwandeln: jedes Land entspricht
Jetzt wollen wir die Knoten eines Graphen einfärben, und zwei Knoten müssen eine andere Farbe haben, wenn sie durch eine Kante verbunden sind.
1852 musste der Botanikstudent
In den folgenden 100 Jahren veröffentlichten viele Mathematiker „Beweise“ für den Vier-Farben-Satz, nur um später Fehler zu finden. Einige dieser ungültigen Beweise waren so überzeugend, dass es mehr als 10 Jahre dauerte, um die Fehler zu entdecken.
Mathematiker konnten lange Zeit weder beweisen, dass vier Farben ausreichen, noch eine Karte finden, die mehr als vier Farben benötigte.
In Bezug auf das Vier-Farben-Problem wurden bis 1976 nur geringe Fortschritte erzielt, als
Der Vier-Farben-Satz ist der erste bekannte mathematische Satz, der mit Hilfe eines Computers bewiesen wurde, etwas, das inzwischen viel gebräuchlicher und weniger umstritten ist. Schnellere Computer und ein effizienterer Algorithmus tragen dazu bei, dass man heute den Vier-Farben-Satz auf einem Laptop in nur wenigen Stunden beweisen kann.
Stempel der mathematischen Fakultät der Universität von
Illinois Urbana-Champaign, wo Haken und Appel gearbeitet haben.
"Four colors suffice" bedeutet "Vier Farben reichen aus"
Der Vier-Farben-Satz funktioniert nur für Karten auf einer flachen Ebene oder einer Kugel, wobei alle Länder aus einem einzigen Gebiet bestehen.
Mathematiker haben sich aber auch Karten von Imperien angesehen, auf denen Länder aus mehreren nicht zusammenhängenden Gebieten bestehen können, und Karten auf unterschiedlich geformten Planeten, wie zum Beispiel einem Torus (Donutform). In diesen Fällen braucht man mehr als vier Farben, und die Beweise werden noch schwieriger.
Diese Karte auf einem Torus benötigt sieben Farben.