nach oben

2015 | Buch

Kapitel lesen Erstes Kapitel lesen

Graphentheorie

Eine Einführung aus dem 4-Farben Problem

verfasst von: Martin Aigner

Verlag: Springer Fachmedien Wiesbaden

Buchreihe : Springer Studium Mathematik - Bachelor

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Es kommt nicht oft vor, dass ein einzelnes Problem ein ganzes mathematisches Gebiet hervorruft. Das allseits bekannte 4-Farben Problem war solch ein singuläres Ereignis: Aus den Lösungsversuchen entwickelte sich die Graphentheorie, die heute zu den unverzichtbaren Grundlagen der Diskreten Mathematik und Informatik und weiterer angewandter Wissenschaften gehört. Das Buch versucht zweierlei: Es will erstens alle wichtigen Begriffe, Ideen und Sätze für eine Einführung in die Graphentheorie im Bachelorstudium bereitstellen, und zweitens ein tieferes Verständnis für dieses wunderbare Gebiet vermitteln, durch einen Rückblick, wie alles mit dem 4-Farben Problem begann, und einen Ausblick auf die erstaunliche Lösung und den damit aufgeworfenen Fragen.

Inhaltsverzeichnis

Frontmatter

I Introduktion

Frontmatter

1. Problem und „Lösung“

Zusammenfassung

Am 23. Oktober 1852 schrieb Augustus de Morgan, Professor am University College in London, an seinen Kollegen Sir William Hamilton:

Ein Student fragte mich heute, ob es stimmt, dass die Länder jeder Landkarte stets mit höchstens 4 Farben gefärbt werden können, unter der Maßgabe, dass angrenzende Länder verschiedene Farben erhalten.

De Morgan führte sogleich ein Beispiel an, in dem 4 Farben notwendig sind (Figur 1.1) und fügte hinzu:

Ich habe das Gefühl, dass im Fall von 4 Ländern, von denen je zwei stets eine gemeinsame Grenze haben, immer eines von den drei anderen eingeschlossen wird, so dass es nicht mit einem fünften verbunden sein kann. Wenn das stimmt, so sollten 4 Farben tatsächlich immer genügen. Aber es ist nicht einfach und ich bin nicht sicher über die möglichen Verwicklungen.

Martin Aigner

2. Irrtum und Hoffnung

Zusammenfassung

In einer 1890 erschienenen Arbeit analysierte Heawood Kempes Beweisführung der 4-Farben Vermutung und legte einen fatalen Defekt bloß. Blättern wir zum letzten übriggebliebenen Fall zurück: Ein Land F ist von 5 Ländern A,B, . . . , E umgeben, die mit den Farben rot, blau, grün, weiß und blau gefärbt sind. Wir nehmen an, dass eine rot-grün Kette von A nach C existiert und eine rot-weiß Kette von A nach D. Dadurch konnten wir in der blau-weiß Komponente, die B enthält, die Farben vertauschen, und ebenso in der blau-grün Komponente, die E enthält. Während es richtig ist, dass jede einzelne dieser Vertauschungen wieder eine zulässige Färbung ergibt (wobei allerdings nach wie vor alle 4 Farben um F herum auftreten), so kann es nach Vornahme beider Vertauschungen passieren, dass zwei blaue Länder nun aneinanderstoßen (die vorher weiß bzw. grün gefärbt waren), was unzulässig ist. Der Ausschnitt einer Landkarte in Figur 2.1 demonstriert diese Tatsache.

Martin Aigner

3. Beginn der Graphentheorie

Zusammenfassung

Wenngleich um 1900 die 4-Farben Vermutung wohl nach wie vor als kombinatorische oder topologische Merkwürdigkeit angesehen wurde, die vielleicht mit einer neuen Idee auf einen Schlag gelöst werden könnte, so waren auch bereits erste Ansätze zu erkennen, das Problem in einen theoretischen Rahmen einzugliedern. Im Wesentlichen wurden fünf Richtungen eingeschlagen, die wir nun diskutieren wollen.

Martin Aigner

II Thema

Frontmatter

4. Plättbarkeit

Zusammenfassung

Von diesem Kapitel an betrachten wir stets Graphen statt Landkarten. Wir haben in Kapitel 2 gesehen (Satz 2.8), dass die 4-Farben Vermutung äquivalent zur Vermutung ist: Jeder plättbare Graph ist 4-färbbar. Als vordringlichste Aufgabe ergibt sich daraus eine Charakterisierung plättbarer Graphen.

Martin Aigner

5. Färbung

Zusammenfassung

Neben Plättbarkeit ist Färbung der zweite Begriff, der in der 4-Farben Vermutung vorkommt. Wie schon im vorangegangenen Kapitel besprechen wir nun allgemein Färbungen von beliebigen Graphen – in der Hoffnung natürlich, dass wir dadurch auch Aufschluss über die Färbung plättbarer Graphen gewinnen.

Martin Aigner

6. Faktorisierung

Zusammenfassung

Rufen wir uns die Definition eines γ-Faktors eines Graphen \(G = (V,E)\) in Erinnerung. Ein γ-Faktor von G ist ein γ-regulärer Untergraph \(H = (V,E')\), d. h. jede Ecke hat in H den Grad γ. Ausgangspunkt des Interesses an Faktorisierungen war Taits Satz 1.7, der in der Terminologie der Faktorisierungen lautet: Die 4-Farben Vermutung ist genau dann richtig, wenn das Gerüst jeder kubischen brückenlosen Landkarte L in drei disjunkte 1-Faktoren zerfällt. Petersens Resultat 3.6 hat zumindest die Existenz eines 1-Faktors in jedem 3-regulären brückenlosen Graphen (eben oder nicht) nachgewiesen. Wir legen uns nun die allgemeine Frage vor: Welche Graphen besitzen einen 1-Faktor?

Martin Aigner

7. Hamiltonsche Kreise

Zusammenfassung

Wenn wir zum Ende von Kapitel 3 zurückblättern, so lesen wir, dass der Ausgangspunkt zum Studium Hamiltonscher Kreise die Vermutung 3.9 von Tait war: Jeder 3- reguläre polyedrische Graph besitzt einen Hamiltonschen Kreis. Dort wird auch erwähnt, dass Whitney im Lichte des Satzes von Steinitz 3.11 gezeigt hat, dass die Vermutung von Tait sogar die 4-Farben Vermutung implizieren würde. Und mit diesem Resultat von Whitney wollen wir beginnen.

Martin Aigner

8. Matroide

Zusammenfassung

Wie schon bei den vorangegangenen Themen beginnt auch unsere letzte Theorie in den 1930’er Jahren – und zwar mit dem Satz 4.11 von Whitney. Rufen wir uns den dort abgehandelten Gedanken in Erinnerung: G = (V, E) sei ein Graph. Wir nennen G ^∗ = (V ^∗, E ^∗ ) ein Whitney-Dual, wenn eine Bijektion \(\varphi {\rm{: }}E \to {E^*}\) existiert, so dass C ⊆ E genau dann ein Polygon in G ist, wenn \(\varphi C \subseteq \,{E^*}\) ein Bond in G^∗ ist. Der Inhalt von Whitneys Satz war: Genau die plättbaren Graphen G besitzen ein W-Dual, nämlich den dualen Graphen G ^∗ irgendeiner ebenen Realisierung. Was aber, wenn G nicht plättbar ist, können wir auch dann eine sinnvolle „duale“ Struktur erklären?

Martin Aigner

III Finale

Frontmatter

9. Zurück zum Anfang

Zusammenfassung

Wir greifen die Ideen von Kempe zur Lösung des 4-Farben Problems und vor allem ihre Präzisierung durch Birkhoff (Kapitel 3) wieder auf – und zwar in der dualen Form. Nach Heawoods 5-Farbensatz 2.1 wissen wir, dass jeder ebene Graph G chromatische Zahl χ(G) ≤ 5 hat. Ist die 4-Farben Vermutung falsch, so muss es also 5-chromatische ebene Graphen geben – und die Idee des Induktionsbeweises von Kempe war es gerade, die minimalen Graphen unter ihnen zu studieren, um schließlich aus einem Widerspruch heraus ihre Nichtexistenz und damit die 4-Farben Vermutung zu beweisen. Wir beginnen demnach mit der folgenden Definition, wobei klar ist, dass wir uns auf einfache Graphen beschränken können.

Martin Aigner

10. Lösung und „Problem“

Zusammenfassung

Wir haben anhand mehrerer Beispiele gesehen, wie die klassische Methode funktionierte. Als Erstes wurde eine Liste von reduzierbaren Konfigurationen aufgestellt (Reduzierbarkeit) und als Zweites der Nachweis versucht, dass in jeder beliebigen Triangulierung mindestens eine der schon bekannten reduzierbaren Konfigurationen auftaucht (Unvermeidbarkeit).

Martin Aigner

Backmatter

Titel: Graphentheorie
verfasst von: Martin Aigner
Verlag: Springer Fachmedien Wiesbaden
Electronic ISBN: 978-3-658-10323-1
Print ISBN: 978-3-658-10322-4
DOI: https://doi.org/10.1007/978-3-658-10323-1