Chr.Nelius: Graphentheorie (WS 2015/16) 57 § 16. Flächenfärbungen In der Mitte des 19. Jahrhunderts tauchte eine Vermutung auf, die erst 125 Jahre später bewiesen werden sollte und die eine der bekanntesten Vermutungen der Mathematik werden sollte. Ein Mathematik–Student vermutete, dass jede Landkarte mit höchstens vier Farben so gefärbt werden kann, dass benachbarte Länder immer unterschiedlich gefärbt sind. Diese ”Vierfarben–Vermutung” hat die Entwicklung der Graphentheorie stark beeinflusst und vorangetrieben. Wir werden sehen, dass diese Vermutung äquivalent zum Vierfarben–Satz für die Eckenfärbung ist. Wir sehen hier einen planaren Graphen, dessen Flächen mit 6,3 bzw 2 Farben so gefärbt sind, dass benachbarte Flächen immer unterschiedlich gefärbt sind. (16.1) DEF: Sei G ein ein planarer Graph mit einer ebenen Zeichnung Z(G) . a) Bei einer Flächenfärbung von G wird jeder Fläche von Z(G) genau eine Farbe zugeordnet (oder anschaulicher: jede Fläche wird mit genau einer Farbe gefärbt). b) Eine Flächenfärbung von G heißt zulässig, wenn benachbarte Flächen (das sind Flächen mit mindestens einer gemeinsamen Randkante) immer mit unterschiedlichen Farben gefärbt sind. c) Sei k ≥ 1 eine natürliche Zahl. G heißt k–flächenfärbbar , wenn es eine zulässige Flächenfärbung von G mit höchstens k verschiedenen Farben gibt. Man sagt dann auch, dass G eine k–Flächenfärbung besitzt. 58 Chr. Nelius: Graphentheorie (WS 2015/16) (16.2) BEM: a) Ein planarer Graph G besitzt genau dann eine zulässige Flächenfärbung, wenn er keine Brücke besitzt. b) Ein Graph ist genau dann 1–flächenfärbbar, wenn er der Null–Graph ist. c) Der Tetraeder–Graph hat die chromatische Zahl 4 . Er ist 4–flächenfärbbar, aber nicht 3– flächenfärbbar. d) Beispiel für einen Graphen mit chromatischer Zahl 4, der 3–flächenfärbbar ist. e) Ist ein Graph k–flächenfärbbar, so muss nicht jeder Untergraph ebenfalls k– flächenfärbbar sein. Beispiel: Der Graph G aus d) ist 3–flächenfärbbar. G enthält aber den Tetraeder–Graphen als Untergraphen, der nicht 3–flächenfärbbar ist. Wir wollen jetzt festlegen, an welchen Graphen wir Flächenfärbungen vornehmen wollen. Der Graph muss planar sein (sonst hätten wir keine Flächen) und soll zusammenhängend sein (sonst könnte man die Zusammenhangskomponenten flächenfärben), so dass Ecken vom Grade 0 ausgeschlossen sind. Der Graph darf keine Brücken enthalten, somit sind insbesondere Ecken vom Grade 1 ausgeschlossen. Ecken vom Grade 2 sind für die Berandungen unerheblich und sollen daher keine Berücksichtigung finden. Alle diese Eigenschaften findet man in 3–zusammenhängenden Graphen. Wir definieren daher: (16.3) DEF: Eine Landkarte ist ein 3–zusammenhängender planarer Graph. (16.4) BEM: a) Ist G eine Landkarte mit mindestens 2 Ecken, so gilt δ(G) ≥ 3 (nach (4.18)). b) Eine Landkarte enthält keine Brücken und besitzt daher eine zulässige Flächenfärbung. c) Ist G ein zusammenhängender planarer Graph, so gilt nach (15.14a): G Landkarte ⇐⇒ G⋆ schlicht. 59 Chr. Nelius: Graphentheorie (WS 2015/16) (16.5) SATZ: Für eine Landkarte G sind folgende Aussagen äquivalent: a) G ist 2–flächenfärbbar b) G ist ein Euler–Graph. (16.6) SATZ: Sei G ein zusammenhängender planarer Graph. Dann sind für k ∈ Aussagen äquivalent: N folgende a) G ist k–eckenfärbbar b) Der duale Graph G⋆ ist k–flächenfärbbar. Bew: a) =⇒ b) Da G keine Schlingen enthält, besitzt G⋆ keine Brücken und daher nach (16.2a) eine zulässige Flächenfärbung. In jeder Fläche F ⋆ von G⋆ liegt genau eine Ecke v von G (vgl. (15.9c) ). Da eine k–Eckenfärbung von G vorgegeben ist, kann man die Fläche F ⋆ mit der Farbe der Ecke v färben. Sind F1⋆ und F2⋆ zwei Flächen mit gemeinsamer Randkante, so müssen die darin liegenden Ecken v1 bzw. v2 von G adjazent sein, so dass v1 und v2 unterschiedlich gefärbt sind. Damit sind dann auch die Flächen F1⋆ und F2⋆ unterschiedlich gefärbt, so dass man insgesamt eine k–Flächenfärbung von G⋆ erhält. b) =⇒ a) Da G⋆ keine Brücken enthält, besitzt G keine Schlingen und daher eine zulässige Eckenfärbung. Jede Ecke v von G liegt in genau einer Fläche F ⋆ von G⋆ . Ist eine k–Flächenfärbung von G⋆ gegeben, so kann man die Ecke v mit der Farbe dieser Fläche F ⋆ färben. Sind v1 und v2 zwei adjazente Ecken von G , so haben die zugehörigen Flächen F1⋆ und F2⋆ eine gemeinsame Randkante und sind deshalb unterschiedlich gefärbt. Folglich haben auch v1 und v2 unterschiedliche Farben. Insgesamt erhält man eine k–Eckenfärbung von G . (16.7) FOLG: Ein zusammenhängender planarer Graph besitzt genau dann eine 4–Eckenfärbung, wenn sein dualer Graph eine 4–Flächenfärbung besitzt. (16.8) SATZ: Der Vierfarben–Satz für Landkarten Jede Landkarte ist 4–flächenfärbbar. Bew: Ist G eine Landkarte, so ist G⋆ planar und nach (16.4c) auch schlicht. Nach dem Vierfarben– Satz (14.14) ist G⋆ somit 4–eckenfärbbar , so dass dann G⋆⋆ nach (16.7) 4–flächenfärbbar ist. Da G zusammenhängend ist, stimmt aber G⋆⋆ nach (15.11) mit dem Graphen G überein, so dass G schließlich auch 4–flächenfärbbar ist. BEM: Der obige Beweis benutzt den Vierfarben–Satz (14.14) für die Eckenfärbung und ist daher kein eigenständiger Beweis!! ! Es folgen einige Anmerkungen zur Geschichte des Vierfarben–Problems. Chr. Nelius: Graphentheorie (WS 2015/16) 60 Zur Geschichte des Vierfarben–Problems Im Jahre 1852 teilte der Mathematik–Student Frederick Guthrie seinem Professor Augustus de Morgan in London die Vermutung seines Bruders Francis Guthrie mit, dass jede Landkarte mit vier Farben so gefärbt werden kann, dass benachbarte Länder immer eine unterschiedliche Farbe haben. Francis Guthrie (später Mathematik–Professor in Kapstadt) war auf diese Idee beim Färben einer Karte der Grafschaften von England gekommen. Obwohl diese Vermutung recht plausibel erschien, war es nicht klar, wie man sie beweisen könnte. Deshalb fragte de Morgan in einem Brief vom 23.10.1852 an seinen (uns nicht ganz unbekannten) Kollegen William Rowan Hamilton in Dublin nach. (Dieser Brief existiert heute noch.) Hamilton konnte diese Frage nicht beantworten und hatte allerdings auch kein sonderliches Interesse an ihr. 61 Chr. Nelius: Graphentheorie (WS 2015/16) De Morgan machte nun das “Vierfarbenproblem” in Mathematikerkreisen publik, und es wurde lange nach einem Beweis gesucht. Auch Arthur Cayley beschäftigte sich mit diesem Problem und legte es 1878 der London Mathematical Society vor. Schließlich veröffentlichte der englische Rechtsanwalt (und Mathematiker) Alfred Bray Kempe, der ein Schüler von Cayley gewesen war, im Jahre 1879 einen Beweis. 11 Jahre später zeigte der englische Mathematiker Percy John Heawood , dass der Beweis von Kempe fehlerhaft war. In derselben Arbeit bewies Heawood den schwächeren “Fünffarben–Satz”. Chr. Nelius: Graphentheorie (WS 2015/16) 62 Dadurch rückte das Vierfarben–Problem wieder in den Mittelpunkt des Interesses und wurde in den folgenden Jahrzehnten zu einer der bekanntesten und berühmtesten Vermutungen in der Mathematik. Viele Mathematiker versuchten sich an einem Beweis, und die Methoden, die Kempe bei seinem fehlerhaften Beweis benutzt hatte, blieben von Bedeutung und wurden weiterentwickelt. Schließlich fanden Kenneth Appel und Wolfgang Haken von der Universität in Illinois im Jahre 1976 einen Beweis, bei dem etwa 2000 Problemfälle mit Hilfe eines Computers überprüft werden mussten. Diese Beweismethode wird jedoch von einigen Mathematikern sehr kritisch betrachtet und auch nicht immer akzeptiert.
© Copyright 2024 ExpyDoc
