Stern Mathematik: Der Fünffarbensatz
Released by matroid on Mo. 23. Februar 2004 15:03:48 [Statistics]
Written by Fabi - 8898 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)

Viele von euch haben bestimmt schon mal vom Vierfarbensatz gehört:

Jede Landkarte lässt sich mit 4 Farben färben, so dass benachbarte Länder verschiedene Farben haben.

Der Beweis dieses Satzes ist äußerst schwer und wurde erst 1977, 125 Jahre, nachdem die Vermutung aufgestellt worden war, bewiesen, und auch dieser Beweis war umstritten – er baute zum Großteil auf den Rechungen eines Computers auf, die man per Hand nicht nachvollziehen konnte.

Umso erstaunlicher ist es, dass man den Satz in einer leichten Abschwächung ohne besondere Kenntnisse beweisen kann:

Jede Landkarte lässt sich mit 5 Farben färben, so dass benachbarte Länder verschiedene Farben haben.




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
\(\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:
: Graphentheorie :: Interessierte Studenten :: Reine Mathematik :: Mathematik :
Der Fünffarbensatz [von Fabi]  
Viele von euch haben bestimmt schon mal vom Vierfarbensatz gehört: Jede Landkarte lässt sich mit 4 Farben färben, so dass benachbarte Länder verschiedene Farben haben. Der Beweis dafür ist serh schwer. Für 5 Farben geht es aber einfacher, wie Fabi hier gezeigt hat.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 8898
 
Aufrufstatistik des Artikels
Insgesamt 363 externe Seitenaufrufe zwischen 2012.01 und 2021.06 [Anzeigen]
DomainAnzahlProz
https://google.com113%3 %
https://google.de6116.8%16.8 %
http://google.de26673.3%73.3 %
https://www.bing.com92.5%2.5 %
https://de.m.wikipedia.org41.1%1.1 %
http://www.bing.com51.4%1.4 %
https://int.search.myway.com10.3%0.3 %
http://suche.aol.de10.3%0.3 %
http://matheraum.de10.3%0.3 %
http://google.at10.3%0.3 %
http://suche.t-online.de10.3%0.3 %
https://www.ecosia.org10.3%0.3 %
https://www.startpage.com10.3%0.3 %
http://www.golemis.eu.org00%0 %

Häufige Aufrufer in früheren Monaten
Insgesamt 333 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2017 (85x)http://google.de/url?sa=t&rct=j&q=
2020-2021 (46x)https://google.de/
2012-2013 (22x)http://google.de/url?sa=t&rct=j&q=fünffarbensatz beweis
201204-04 (17x)http://google.de/url?sa=t&rct=j&q=mathe 5 satz
201301-01 (16x)http://google.de/url?sa=t&rct=j&q=fünf farben satz beweis induktion
201208-08 (15x)http://google.de/url?sa=t&rct=j&q=fünffarbensatz nach induktion nach n
201405-05 (15x)http://google.de/url?sa=t&rct=j&q=fünffarbensatz
201206-06 (14x)http://google.de/url?sa=t&rct=j&q=fünffarbensatz induktion
202102-05 (14x)https://google.de
201207-07 (10x)http://google.de/url?sa=t&rct=j&q=fünf-farben-satz
201203-03 (10x)http://google.de/url?sa=t&rct=j&q=matroids matheplanet fünffarbensatz
201209-09 (9x)http://google.de/url?sa=t&rct=j&q=vier farben problem körper
201201-01 (8x)http://google.de/url?sa=t&rct=j&q=was gehört alles zum vier farben satz
201202-02 (8x)http://google.de/url?sa=t&rct=j&q=fünffarbensatz einfacher beweis
201306-06 (8x)http://google.de/url?sa=t&rct=j&q=matroids+matheplanet+fünffabrensatz
201304-04 (7x)http://google.de/url?sa=t&rct=j&q=fünf farben satz
2020-2021 (6x)https://www.bing.com/
201503-03 (6x)http://google.de/url?sa=t&source=web&cd=2&ved=0CB8QFjAB
202009-10 (5x)https://google.com/
2020-2021 (4x)https://de.m.wikipedia.org/
201210-10 (4x)http://google.de/url?sa=t&rct=j&q=beweis fünffarbensatz
201303-03 (4x)http://google.de/url?sa=t&rct=j&q=fünffarbensatz beweis euler

[Top of page]

"Stern Mathematik: Der Fünffarbensatz" | 13 Comments
The authors of the comments are responsible for the content.

Re: Der Fünffarbensatz
von: Ende am: Mo. 23. Februar 2004 17:20:37
\(\begingroup\)
Hallo Fabi!

Schoene Idee fuer einen Artikel hast Du da gehabt. Du hast den Artikel auch schoen fluessig gelesen. Ich konnte ihn praktisch wie Prosa lesen. Kompliment.

Gruss, E. ;)\(\endgroup\)
 

Re: Der Fünffarbensatz
von: Ende am: Mo. 23. Februar 2004 17:21:51
\(\begingroup\)
Aerks, moeglicherweise hast Du den Artikel zwar fluessig gelesen, ich meinte aber, dass Du ihn fluessig geschrieben hast.

Waere ich bloss anonym geblieben...

Gruss, A. ;)\(\endgroup\)
 

Re: Der Fünffarbensatz
von: matroid am: Mo. 23. Februar 2004 18:01:23
\(\begingroup\)
Hi Fabi,

mir gefällt es auch gut. Der 5-Farben-Satz ist wirklich schön zu beweisen.

Gruß
Matroid\(\endgroup\)
 

Re: Der Fünffarbensatz
von: Spock am: Do. 26. Februar 2004 20:35:41
\(\begingroup\)
Hallo Fabi,

je weniger Farbe(n), desto schwerer Beweise?

Dein "5 Farben Beweis" hat mich überzeugt, und Du hast das wirklich schön dargestellt.

Was mich noch interessieren würde: Du schreibst, daß der Beweis des Vierfarbensatzes aus dem Jahre 1977 umstritten "war". Ist man mittlerweile, ohne Computer, schlauer, d.h. existiert ein allgemein akzeptierter Beweis?

Gruß
Juergen\(\endgroup\)
 

Re: Der Fünffarbensatz
von: Rebecca am: Do. 26. Februar 2004 21:18:26
\(\begingroup\)
Hi Juergen,

nein, es gibt immer noch keinen "computerfreien" Beweis.

Gruß
Rebecca\(\endgroup\)
 

Re: Der Fünffarbensatz
von: Spock am: Do. 26. Februar 2004 21:42:46
\(\begingroup\)
Danke Rebecca,
gäbe es einen solchen, hättest Du ihn mit Sicherheit gefunden, :-)
Frage an Dich: Ist der "Computerbeweis" für Dich akzeptabel?

Gruß
Juergen\(\endgroup\)
 

Re: Der Fünffarbensatz
von: Rebecca am: Fr. 27. Februar 2004 10:30:11
\(\begingroup\)
Hi Jürgen,

nachdem ich Fabis Artikel gelesen hatte, habe ich natürlich recherchiert, ob es inzwischen einen "richtigen Beweis" des Vierfarbensatzes gibt. Deshalb konnte ich deine Frage auch sofort beantworten.
Ist für mich ein Computerbeweis akzeptabel? Mit Radoi Erivan beantwortet: Im Prinzip ja, aber...
Ja, wenn es sich nur um die Durchführung einer riesigen Menge von Fallunterscheidungen handelt, der Programmcode nachvollziehbar ist und ausreichend getestet wurde. Denn das ist nichts anderes als übliche Beweise, die eine Reihe von Fallunterscheidungen enthalten. Beim Computerbeweis des Vierfarbensatzes sind diese Bedingungen angabegemäß erfüllt (es waren ja auch nur 1482 Fallunterscheidungen).
Anders ist das mit dem Beweis der  Keplersche Vermutung über  dichteste Art, Kugeln aufzustapeln. Dieser Computerbeweis von Thomas Hales und Tom Ferguson. Ihre 250 Seiten lange Dokumentation war derart unübersichtlich und unvollständig, dass - nach mehrjähriger intensiver Arbeit - die Gutachter  nicht in der Lage gewesen waren, den Beweis mit allerletzter Sicherheit zu zertifizieren. (Aber Hales arbeitet weiter daran, in seinem "Formal Proof of Kepler-Projekt" will er - ebenfalls mit Computern als Internetprojekt - jeden einzelnen Schritt seines Beweises nachvollziehbar prüfen und dokumentieren. Geschätzte Projektdauer: 20 Jahre !!).

Gruß
Rebecca
\(\endgroup\)
 

Re: Der Fünffarbensatz
von: Ex_Mitglied_3308 am: Fr. 27. Februar 2004 19:33:18
\(\begingroup\)
Kann nur das Buch "Der Vierfarbensatz" von R. und G. Fritsch für weitere Informationen empfehlen.

Um 5€ auf:
http://www.stm-books.at/
\(\endgroup\)
 

Re: Der Fünffarbensatz
von: Fabi am: Sa. 28. Februar 2004 16:53:20
\(\begingroup\)
Hi!

Soviel ich weiß, gibt es keinen "computerfreien" Beweis, aber kürzere Beweise als den damals angegebenen (statt ca. 1500 Fallunterscheidungen sind es nur noch ca. 650). Wer aber mit dem ersten Beweis wegen des Computers nicht einverstanden war, den wird das auch nicht zufriedenstellen.

Gruß
Fabi\(\endgroup\)
 

Re: Der Fünffarbensatz
von: Fabi am: So. 29. Februar 2004 15:04:01
\(\begingroup\)
Hi!

Die Fünffärbung hat gegenüber der Vierfärbung vermutlich auch den Vorteil, dass man Landkarten algorithmisch vermutlich recht gut fünffärben kann.

Sei f: N -> N die FUnktion, die angibt, wie lange usnerer Algorithmus für Graphen mit n Ecken arbeitet.

Bei einem vorgegebenem Graphen mit n Ecken nimmt man eine Ecke von Grad < 6 raus und färbt den verbliebenen Graphen mit dem Algorithmus mit 5 Farben. Das geht in f(n-1) Schritten. Dann prüft man (mit den Bezeichnungen wie im Artikel), ob es einen rot-blau-Weg gibt, das sollte in der Zeit O(n) gehen. Und dann färbt man um, das geht auch in der Zeit O(n).

Insgesamt ist also f(n) = f(n-1)+2O(n), also ist f(n) = O(n²), also nicht so schlecht.

Für die Vierfärbbarkeit gibt es sowas wohl nicht - sonst hätte man je einen echten Beweis.

Weiß jemand näheres darüber?

Gruß
Fabi

\(\endgroup\)
 

Re: Der Fünffarbensatz
von: MasterSader am: So. 12. Dezember 2004 22:17:34
\(\begingroup\)
Klingt zwar blöd, ABER fehlt da nicht ne Strecke ^^. Die Verbindung der beiden rechten äußeren Länder?\(\endgroup\)
 

Re: Der Fünffarbensatz
von: Ex_Mitglied_40174 am: Mo. 01. Oktober 2012 17:14:12
\(\begingroup\)
Hallo Fabi,

ich muss für die Schule eine Facharbeit über den 5-Farbensatz schreiben und weiß ehrlich geasgt nicht genau wie ich damit 15 Seiten füllen soll. 😁  Ich habe das Buch "Kombinatorische Optimierung erleben" gekauft, in dem das Problem sehr gut behandelt wird. Andauernd aber nur aus einer Quelle zu zietieren ist jedoch schlecht. Könntest du mir eventuell Bücher oder Quellen empfehlen die ich hierfür verwenden kann? 😵  :-?

Gruß
 
Max
''\(\endgroup\)
 

Re: Der Fünffarbensatz
von: Ex_Mitglied_40174 am: Mo. 03. Dezember 2012 15:01:10
\(\begingroup\)
Super Erklärung. Ich habe den Beweis auf Wikipedia nicht 100% verstanden, da ich nicht beachtet habe, dass die Reihenfolge der Konten (1-3,2-4) eine Rolle spielt.\(\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]