Wartende Änderungsvorschläge zum gleichen (*) oder nahestehenden (-) Objekten
* 10207 Anonymous 2017-06-01 17:27:05 object_text In der jetzigen Version befinden sich mehrere Fehler. So wird nicht jede Fläche von mindestens 3 Kanten begrenzt (die äußere nämlich!), nicht jede Kante grenzt an zwei verschiedene Flächen (nämlich Kanten die inzident zu einem Knoten vom Grad 1 sind) und dementsprechend sind auch die Formeln offensichtlich falsch: "Es gibt in einem ebenen Graphen mit e Ecken also höchstens 3e-6 Kanten" -> Man betrachte nur einen Graph mit 2 Ecken! Diese Fehler wurden durch Anpassung der Formulierungen und Gleichungen korrigiert, der Beweis an sich ändert sich dadurch ja nicht. Den Satz "Auf 2 Flächen kommen also mindestens 3 Kanten." habe ich aufgrund der Überschaubarkeit so stehen lassen, auch wenn man hier die äußere Fläche eigentlich auch nochmal erwähnen müsste. [Vergleichen]
Bearbeiten von: Abschnitt [Änderungshistorie]
  Zeilenumbrüche automatisch mache ich selbst mit HTML    

Ich möchte eine Mail an , nachdem mein Vorschlag bearbeitet ist.
  Nachricht zur Änderung:

Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
[Link zurück zum Artikelabschnitt]

Vorschau:
Der Fünffarbensatz



Da das Problem in seiner Formulierung mit den Landkarten begrifflich schwer zu handhaben ist, modelliert man die Karte als Graph: Die Länder sind die Ecken, und zwei Ecken sind genau dann durch eine Kante verbunden, wenn die beiden entsprechenden Länder eine gemeinsame Grenze haben.
Ein Beispiel:
Eine Landkarte mit rot darübergelegtem Graphen:

Bild

Graphen, die so aus Landkarten entstehen, sind aber nicht irgendwelche x-beliebigen Graphen, sondern recht spezielle.

Die wichtigste Eigenschaft, die solche Graphen haben: Man kann sie in einer Ebene zeichnen, ohne dass sich ihre Kanten schneiden. Soche Graphen nennt man ebene Graphen.

Die Behauptung, die wir jetzt beweisen wollen, lautet also:

Die Knoten eines jeden ebenen Graphen lassen sich so mit 5 Farben färben, dass je zwei durch eine Kante verbundene Knoten verschiedene Farben haben.

Oder kürzer ausgedrückt:

Jeder ebene Graph ist 5-färbbar.

Vor dem eigentlichen Beweis brauchen wir aber noch eine Eigenschaft ebener Graphen.

Bezeichnet man die Anzahl der Ecken eines ebenen Graphen mit e, die der Kanten mit k und die Anzahl der Flächen, in die die Ebene durch den Graphen eingeteilt wird (dabei zählt das Außengebiet mit), mit f, so gilt:

e+f-k = 2

Diese Formel nennt man die Eulersche Polyederformel (siehe in diesem Artikel). Man kann sie leicht per Induktion beweisen.

In einem ebenen Graphen wird eine Fläche durch mindestens 3 Kanten begrenzt, andererseits liegt eine Kante an zwei verschiedenen Flächen. Auf 2 Flächen kommen also mindestens 3 Kanten. Es ist also

fed-Code einblenden
fed-Code einblenden

Mit der Eulerformel kann man daraus eine Abschätzung für die Anzahl der Kanten in einem ebenem Graphen gewinnen:

fed-Code einblenden
fed-Code einblenden
fed-Code einblenden

Es gibt in einem ebenen Graphen mit e Ecken also höchstens 3e-6 Kanten.

Als letzten Begriff benötigen wir den Durchschnittsgrad d eines Graphen. Das ist einfach die durchschnittliche Anzahl der an eine Ecke grenzende Kanten.
Hat man z.B. in einem Graphen 4 Ecken, an die je 2 Kanten grenzen, und 2 weitere Ecken, an die je 3 Kanten grenzen, so ist der Durchschnittsgrad dieser 6 Ecken
fed-Code einblenden

Da jede Kante an genau zwei Ecken angrenzt und somit zweimal in den Durchschnitt miteinbezogen wird, gilt
fed-Code einblenden

Für ebene Graphen gilt insbesondere

fed-Code einblenden

Der Durchschnittsgrad eines ebenen Graphen ist daher immer kleiner als 6, es gibt also immer Ecken, an denen 5 oder weniger Kanten liegen. Das ist die Eigenschaft ebener Graphen, auf denen der Beweis des Fünffarbensatzes aufbaut.

Jetzt kann der Beweis endlich begonnen werden:

Für Graphen mit 1, 2, 3, 4, 5 Ecken ist die Behauptung trivial.

Sei G nun ein ebener Graph mit e > 5 Ecken, und sei die Behauptung richtig für alle Graphen mit weniger Ecken.

G enthält eine Ecke v, an der höchstens 5 Kanten anliegen und damit auch höchstens 5 Nachbarn hat.
Löscht man diese Ecke und alle anliegenden Kanten, so bleibt ein ebener Graph G’ mit e-1 Ecken übrig. Dieser ist nach Induktionsvoraussetzung fünffärbbar.

Sei G’ nun fünfgefärbt. Hat v 4 oder weniger Nachbarn, so haben die an v angrenzenden Ecken nur höchstens 4 verschiedene Farben, man kann v also einfach mit der fünften Farbe färben und hat eine Fünffärbung von G. Man kann also annehmen, dass v tatsächlich 5 Nachbarn hat und diese sogar alle verschieden gefärbt sind, sonst wäre ja wieder eine Farbe nicht unter den Nachbarn von v vertreten und man färbt v einfach in dieser Farbe.

Das ganze sieht also mit den 5 Fraben rot,grün,blau, gelb und orange so aus:

Bild


Wir wollen nun versuchen, durch geschicktes Umfärben einzelner Ecken zu erreichen, dass eine Farbe für v frei wird.

Betrachten wir mal in der Zeichnung die rote und die blaue Ecke. Könnten wir die rote Ecke r blau färben, so ließe sich v rot färben. Wann geht das?
Färben wir r blau, müssen wir natürlich auch alle an r angrenzenden blauen Ecken umfärben, sonst hätten wir ja zwei benachbarte blaue Ecken. Färben wir all diese blauen Ecken einfach mal rot.
Dann müssen wir auch wieder alle an diese umgefärbten Ecken angrenzenden roten Ecken umfärben, sagen wir mal in blau.

Setzen wir dieses Verfahren fort, so tauschen wir die Farben rot und blau auf all den Ecken, die mit r durch einen Kantenzug verbunden sind, auf dem nur rote und blaue Ecken liegen (einem rot-blau-Weg) – andere rote und blaue Ecken sind ja von r durch orange, grüne oder gelbe Ecken abgegrenzt, müssen also auch nicht umgefärbt werden.

Es ist also die Frage, ob die an v angrenzende blaue Ecke b mit einem rot-blau-Weg mit r verbunden ist. Wenn nicht, können wir r blau färben, ohne b umfärben zu müssen, und können v rot färben; wenn doch, dann müssten wir leider auch b rot färben, um nicht zwei blaugefärbte Ecken nebeneinander zu haben, und haben nichts gewonnen – immer noch grenzen alle 5 Farben an v an und wir können v nicht färben.

Die Existenz dieses rot-blau-Weges zwischen r und b liefert jetzt aber eine zusätzliche Strukturaussage über den Graphen, die wir nutzen können.

Bild

W ist der rot-blau-Weg zwischen r und b.

Nun können wir dasselbe Spielchen mit der orangen Ecke o und der grünen Ecke g machen: Gibt es keinen orange-grün-Weg zwischen den beiden, könnte man die orangene Ecke grün färben, in allen mit o durch einen orange-grün-Weg verbundenen Ecken orange und grün austauschen und dann v orange färben. Gibt es einen, haben wir leider immer noch nichts gewonnen.
Kann es aber überhaupt einen geben? Sieht man sich die Zeichnung an, so erkennt man, dass, egal wie man W einzeichnet, ein Weg von o nach g irgendwo W kreuzen muss (der Weg kann ja nicht eine der an v angrenzenden Kanten durchschneiden, weil der Graph eben ist).

Wo kann denn diese Kreuzung sein? Wegen der Ebenheit des Graphen muss diese Kreuzung eine Ecke sein, die auf W liegt. Diese Ecke liegt also auf dem rot-blau-Weg W, ist damit selbst entweder rot oder blau. Einen orange-grün-Weg von o nach g kann es damit nicht geben, weil er eine rote oder blaue Ecke enthalten müsste. Und damit können wir entsprechend umfärben, so dass man auch v gültig färben kann. Damit ist auch G fünfgefärbt. q.e.d.

Man kann also auch jede Landkarte mit 5 Farben färben.

Gruß
Fabi
 
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]