Graphentheorie: Eine Entwicklung Aus Dem 4-Farben Problem

ISBN-13: 9783519020684 / Niemiecki / Miękka / 1984 / 269 str.

Martin Aigner; Martin Aigner

Opis

In den letzten Jahren wurde ich immer haufiger 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 hauptsachlichen Triebfedern waren, und wie es weiter- geht. Insbesondere interessierte, neben anderen Faktoren wie An- wendbarkeit oder Querverbindungen zu anderen Gebieten, die Rolle, welche die groen klassischen Probleme bei der Entwicklung einer Theorie spielten. Die kurzlich erfolgte ungewohnliche Losung 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 scharfer 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 Losung mit ihrem enormen Computer Einsatz ist vorn astheti- 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 hochst selten vorkommt, und da die Losung mit ihren vielfaltigen Aspekten inner- und auermathematischer Art weit in die Zukunft weist. Die Arbeit an diesem Buch hat mich uberzeugt, da die zweite Auffassung eher zutrifft - und es ist meine Hoff- nung, da mir in der Darstellung hinreichende Argumente dafur ge- lungen sind.

Spis treści

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, 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.