Graphentheorie: Eine Entwicklung aus dem 4-Farben Problem

by Martin Aigner (With)

Overview

In den letzten Jahren wurde ich immer häufiger von Studenten ge­ fragt, warum sich ein mathematisches Gebiet gerade in dieser (meist in der Vorlesung vorgestellten) Weise entwickelt hat und nicht an­ ders, was die hauptsächlichen Triebfedern waren, und wie es weiter­ geht. Insbesondere interessierte, neben anderen Faktoren wie An­ wendbarkeit oder Querverbindungen zu anderen Gebieten, die Rolle, welche die großen klassischen Probleme bei der Entwicklung einer Theorie spielten. Die kürzlich erfolgte ungewöhnliche Lösung des 4-Farben Problems war mir ein willkommener Anlaß, den genauen Einfluß zu studieren, den dieses universell bekannte Problem vornehmlich auf die Graphen­ theorie hatte. Vielleicht schärfer als anderswo scheiden sich arn 4-Farben Problem die Geister. Die einen sagen, die Mathematik, die das 4-Farben Problem hervorgebracht hat, ist eine Marginalie und die Lösung mit ihrem enormen Computer Einsatz ist vorn ästheti­ schen Standpunkt aus geradezu abschreckend. Die anderen wieder~ meinen, daß das 4-Farben Problem fast im Alleingang eine ganze Dis­ ziplin hat entstehen lassen, eben die Graphentheorie, wie es in diesem Umfang höchst selten vorkommt, und daß die Lösung mit ihren vielfältigen Aspekten inner- und außermathematischer Art weit in die Zukunft weist. Die Arbeit an diesem Buch hat mich überzeugt, daß die zweite Auffassung eher zutrifft - und es ist meine Hoff­ nung, daß mir in der Darstellung hinreichende Argumente dafür ge­ lungen sind.

Product Details

ISBN-13:	9783519020684
Publisher:	Vieweg+Teubner Verlag
Publication date:	06/20/2012
Series:	Teubner Studienbücher Mathematik
Edition description:	1984
Pages:	269
Product dimensions:	0.00(w) x 0.00(h) x 0.02(d)
Language:	German

Table of Contents

I: Introduktion.- 1. Ursprung und „Lösung“.- 4-Farben Problem, Graph, Landkarte, Färbung, Euler Formel, die falsche „Lösung“ von Kempe, Taits 3-Farbensatz, Übungen.- 2. Irrtum und Hoffnung.- Kempes Fehler, 5-Farbensatz, geschlossene Flächen, Euler-Poincaré Formel, Heawoodscher Farbensatz, Dualität von Graphen und Landkarten, Übungen.- 3. Neuanfang.- Arithmetisierung des Problems durch Heawood, die geometrischen Ideen von Veblen, Eulersche Graphen, Birkhoff und das Abzählen von Färbungen, Faktorisierung von Graphen, Satz von Petersen, Hamiltonsche Kreise, polyedrische Graphen, Übungen.- II: Thema.- 4. Plättbarkeit.- Zusammenhang von Graphen, Satz von Menger, die Charakterisierungen plättbarer Graphen durch Kuratowski, Whitney und MacLane, Dualität, Geschlecht von Graphen, Kreuzungszahl, Übungen.- 5. Färbung.- Chromatische Zahl und chromatischer Index, die Sätze von Brooks und Vizing, kritische Graphen, Hadwigers Vermutung, chromatisches Polynom, Triangulierungen, Übungen.- 6. Faktorisierung.- Matching in bipartiten Graphen, die Sätze von König und Hall, Transversalen von Mengensystemen, doppelshastische Matrizen, Lateinische Quadrate, der Tuttesche Satz Ober die Existenz von 1-Faktoren, Übungen.- 7. Hamiltonsche Kreise.- Sätze von Whitney und Tutte über Hamiltonsche ebene Graphen, notwendige Bedingungen, Hamiltonscher Abschluß und der Satz von Chvátal, Extremalprobleme in Graphen, die Sätze von Turán und Ramsey, Übungen.- 8. Matroide.- Axiomatische Beschreibungen, Dualität, Polygonmatroid und Bondmatroid von Graphen, Satz von Edmonds, Zyklen und Cozyklen, Kettengruppen, Minoren, irreduzible Gruppen, die geometrischen Ideen von Tutte, Übungen.- III: Finale.- 9. Zurück zum Anfang.- Zwei Ideen: Reduzierbarkeit und Unvermeidbarkeit, die Sätze von Birkhoff, D-Reduzierbarkeit, Obstruktionen, unvermeidbare Mengen und die Methode der Entladung, Übungen.- 10. Lösung und Problem.- Geographisch gute Konfigurationen, wahrscheinlichkeitstheoretische Aspekte, Reduzibilitätsvermutung, Residuen, Chromodendra, Plausibilitätsüberlegungen zur Unvermeidbarkeit, die endgültigen Programme von Appel und Haken und die Lösung, Kritik und Ausblick, Übungen.- Literatur.- Symbolverzeichnis.