Description
Book SynopsisIn 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.
Table of ContentsI: 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, doppelstochastische 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.
