Mathematik: 5-Farben-Satz
Released by matroid on Do. 20. Januar 2005 07:10:57 [Statistics]
Written by Kobe - 4528 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\) Dass jeder ebene Graph 5-färbbar ist, hat Fabi bereits hier bewiesen. Aber ich werde diesen Satz auf eine andere Art und Weise beweisen. Kombinatorischer und mit Listenfärbung

Zum Anfang möchte ich nochmal das Problem erläutern: Eine praktische Frage lautet, ob man jede Landkarte mit nur 5 verschiedenen Farben färben kann, ohne dass 2 aneinander grenzende Länder die gleiche Farbe haben. Für 5 Länder ist das trivial, aber bei schon 6 Ländern kann man nicht einfach drauf los "malen". Und wie sieht es bei 10 Ländern aus? Bei 20? Bei x Ländern?
Um das Problem mathematisch erfassen zu können, konstruieren wir aus der Landkarte einen Graphen - genauer gesagt, einen dualen Graphen. Ein dualer Graph G* eines Graphen G wird wie folgt konstruiert: In jede Fläche von G wird (mittig) eine Ecke gesetzt, welche dann zu G* gehört. Nun bekommen genau jene Ecken eine gemeinsame Kante in G*, die in G in 2 benachbarten Flächen liegen. Würfel und der dazu duale Graph, ein Oktaeder: Bild Oktaeder und der dazu duale Graph, ein Würfel: Bild Der duale Graph (G*) einer Landkarte (G) ist 2-dimensional. Er bekommt pro Land eine Ecke und zusätzlich eine Ecke in der äußeren Region, die nicht abgegrenzt ist. Nun bekommt er Kanten zwischen Ecken, deren Länder auf der Landkarte aneinandergrenzen (die äußere Region nicht vergessen! Sie grenzt üblicherweise an viele Länder) Bild Der duale Graph hat also keine Multikanten oder -ecken und die Kanten schneiden einander nicht, sondern treffen sich höchstens in gemeinsamen Endecken.
Ein Theorem (Proofs from THE BOOK; Aigner, Martin und Ziegler, Günter M.) zeigt, dass jeder ebene Graph fast-triangulierbar ist: Alle inneren Regionen sind Dreiecke. Unseren Graphen können wir ganz einfach durch Hinzunahme von 4 Kanten fast-triangulieren. Das macht die ganze Angelegenheit (das Prüfen auf Färbbarkeit) noch schwieriger, da 2 Ecken, die zuvor nicht verbunden waren, jetzt vielleicht benachbart sind. Also für 2 Ecken, die wir zuvor noch mit der gleichen Farbe färben konnten, brauchen wir nun evtl. 2 verschiedene Farben. Bild
Beweis Graph G=(E,K) ist 5-listenfärbbar \ Voraussetzungen: 1) G ist zusammenhängend 2) G ist fast-trianguliert 3) B sei der Kreis, der die Grenze des Graphen bildet 4) sei x,y\el\B mit xy\el\K (also benachbart) und x(\alpha\) und y(\beta\) (also x \alpha\-gefärbt, y \beta\-gefärbt) sei c(v) die Farbpalette von Ecke v, \forall\ v \el\E 5) \|c(v)\| >= 3 \forall\ v\el\B\\{x,y} 6) \|c(v)\| >= 5 \forall\ v\el\ G\\B Induktion: IA: \|E\| <= 3 => 3 Farben reichen aus, damit der Graph 5\-listenfärbbar ist, da die Grenze B 3 Farben zur Verfügung hat und das Innere 5 Farben zur Verfügung hat IH: G ist 5\-listenfärbbar für \|E\| \ => \exists\ u,v \el\ B , uv\el\K => \exists\ G_1 , B_1 und G_2 , B_2 und B=B_1 \union\ B_2 => G_1 hat < n bzw. weniger Ecken als G, ist fast-trianguliert und da B 3\-listenfärbbar ist, ist auch B_1 weiterhin 3\-listenfärbbar => mit IH ist G_1 5\-listenfärbbar => u(\gamma\) , v(\delta\) mit \gamma\,\delta\ beliebig aber \gamma\ != \delta\ => auch mit (durch G_1) vorgefärbten u,v ist G_2 ebenfalls mit IH 5\-listenfärbbar, da G_2 eine Grenze B_2 hat, die 3\-listenfärbbar ist und das Innere von G_2 fast-trianguliert ist Fall 2) B hat keine Sehne Bild \ sei v_0 \el\ B, v_0 x\el\K (also v_0 Nachbar von x), v_0 != y seien v_i (i\el\{1,...,t}) und w Nachbarn von v_0 Betrachten wir G'=G\\v_0 G' hat die Grenze B'= ( B\\v_0 ) \union\{v_1 ,..., v_t } => da \|c(v_0)\|>=3 , existieren beliebige \gamma\,\delta\ != \alpha\ => wir ersetzen alle c(v_i) von G (\|c(v_i)\|>=5, weil sie im Inneren liegen) durch c(v_i)\\{\gamma\,\delta\} in G', alle anderen Farbpaletten bleiben unangetastet => wir färben G' dementsprechend => B' ist 3\-listenfärbbar, G' hat eine Grenze die 3\-listenfärbbar ist, da jetzt \|c(v_i)\|>=3 und laut IH ist das Innere von G' 5\-listenfärbbar => G' ist 5\-listenfärbbar jetzt können wir v_0 wieder dazu nehmen mit allen dazugehörigen Kanten => da x \alpha\-gefärbt und alle v_i 3\-listenfärbbar ohne \gamma\ und \delta\ sind, können wir v_0 \gamma\- oder \delta\-färben. Wir müssen bloß auf w achten, falls es \gamma\- oder \delta\-gefärbt ist, müssen wir v_0 dementsprechend mit der anderen Farbe färben. Jetzt haben wir gezeigt, dass jeder ebene Graph 5-listenfärbbar ist. Wobei wir sogar neue Bedingungen dazu genommen haben, indem wir ihn fast-trianguliert haben. Da Listenfärbung stärker als normale Färbbarkeit ist, wissen wir, dass diese Graphen auch 5-färbbar sind. q.e.d. Vielleicht sind solche Graphen sogar 4-färbbar, das bleibt in diesem Beweis offen ...
\(\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 :: Kombinatorik :: Graphentheorie :: Reine Mathematik :
5-Farben-Satz [von Kobe]  
Dass jeder ebene Graph 5-färbbar ist, hat Fabi bereits hier bewiesen. Aber ich werde diesen Satz auf eine andere Art und Weise beweisen. Kombinatorischer und mit Listenfärbung
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 4528
 
Aufrufstatistik des Artikels
Insgesamt 501 externe Seitenaufrufe zwischen 2012.01 und 2022.09 [Anzeigen]
DomainAnzahlProz
http://google.de39378.4%78.4 %
https://google.de387.6%7.6 %
https://google.com204%4 %
http://google.si91.8%1.8 %
https://www.bing.com81.6%1.6 %
http://www.bing.com112.2%2.2 %
https://www.ecosia.org30.6%0.6 %
https://duckduckgo.com30.6%0.6 %
http://images.google.de20.4%0.4 %
https://www.startpage.com20.4%0.4 %
http://search.conduit.com20.4%0.4 %
http://search.snapdo.com10.2%0.2 %
http://google.com10.2%0.2 %
http://search.sweetim.com10.2%0.2 %
http://173.194.69.9410.2%0.2 %
http://start.mysearchdial.com10.2%0.2 %
http://google.ch10.2%0.2 %
http://suche.gmx.net10.2%0.2 %
http://matheraum.de10.2%0.2 %
http://suche.aol.de10.2%0.2 %
http://google.at10.2%0.2 %

Häufige Aufrufer in früheren Monaten
Insgesamt 468 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2017 (114x)http://google.de/url?sa=t&rct=j&q=
2012-2013 (35x)http://google.de/url?sa=t&rct=j&q=5 farben satz
201205-05 (32x)http://google.de/url?sa=t&rct=j&q=Farbe MAthematik
201206-06 (27x)http://google.de/url?sa=t&rct=j&q=wieso kann man jede landkarte mit fünf f...
201212-12 (26x)http://google.de/url?sa=t&rct=j&q=5 farben problem
2020-2021 (25x)https://google.de/
201204-04 (22x)http://google.de/url?sa=t&rct=j&q=beweis des fünf-farben-satzes für ebe...
2020-2022 (20x)https://google.com/
201306-06 (15x)http://google.de/url?sa=t&rct=j&q=welcher graph ist zwei listenfärbbar
2020-2021 (13x)https://google.de
201203-03 (13x)http://google.de/url?sa=t&rct=j&q=satz in farbe
201201-01 (12x)http://google.de/url?sa=t&rct=j&q=triangulierung matheplanet
201304-04 (12x)http://google.de/url?sa=t&rct=j&q=mathematik der farbe
201303-03 (11x)http://google.de/url?sa=t&rct=j&q=beweisa 5-listenfärbbarkeit
201208-08 (11x)http://google.de/url?sa=t&rct=j&q=beweis 5 farben satz
201209-09 (10x)http://google.de/url?sa=t&rct=j&q=mathe 5 satz
201211-11 (10x)http://google.de/url?sa=t&rct=j&q=mathematik 5 satz
201504-04 (9x)http://google.si/url?sa=i&rct=j&q=
201202-02 (9x)http://google.de/url?sa=t&rct=j&q=5 listen farben satz
201503-03 (8x)http://google.de/url?sa=t&source=web&cd=1&ved=0CBwQFjAA
2020-2022 (8x)https://www.bing.com/
201210-10 (8x)http://google.de/url?sa=t&rct=j&q=funf farbensatz
201302-02 (5x)http://google.de/search?site=&source=hp&q=oktaeder in würfel
201308-08 (5x)http://google.de/url?sa=t&rct=j&q=ebener graph ist 5-listenfärbbar
201307-07 (4x)http://google.de/url?sa=t&rct=j&q=5 farbensatz
201411-11 (4x)http://www.bing.com/search?q=5 farbensatz&pc=cosp&ptag=A4EB2A0A4240A4D26B2F&f...

[Top of page]

"Mathematik: 5-Farben-Satz" | 1 Comment
The authors of the comments are responsible for the content.

Re: 5-Farben-Satz
von: Ex_Mitglied_40174 am: Mi. 23. April 2008 18:55:26
\(\begingroup\)Interessant, interessant, zum Glück habe ich mein Abi bereits in der Tasche!!!!! Ciao und viel Glück\(\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-2023 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]