Die Welt der Graphen verstehen
Autorentext
Manfred Nitzsche war Studiendirektor und Fachleiter mit den Fächern Mathematik und Physik an einem Gymnasium in Berlin.
Klappentext
Die Graphentheorie gehört wie die gesamte diskrete Mathematik zu den Gebieten der Mathematik, die sich heute am stärksten entwickeln, zum Teil angestoßen durch Erfordernisse der Praxis, aber auch aus rein mathematischem Interesse. Dieses Buch soll dazu beitragen, dass die Verfahren und Ergebnisse der Graphentheorie unter Nicht-Fachleuten stärker beachtet werden. Es ist deshalb so geschrieben, dass es im Wesentlichen mathematisch exakt, aber auch ohne mathematische Vorkenntnisse verständlich und vor allem leicht lesbar ist. In Beispielen wird die Denkweise der modernen Mathematik nachvollziehbar und es werden auch Probleme dargestellt, die heute noch ungelöst sind.
Inhalt
1 Erste Graphen.- Das Haus vom Nikolaus.- Was ist ein Graph?.- Auch das ist bei Graphen möglich!.- Der Grad einer Ecke.- Verschiedene Graphen gleiche Graphen?.- Zusätzliche Informationen.- Aufgaben.- Lösungshinweise.- 2 Über alle Brücken: Eulersche Graphen.- Das Königsberger Brückenproblem.- Kantenzüge.- Eulersche Graphen.- Welche Graphen sind eulersch?.- Praxis: Eulersche Touren finden.- Zwei Folgerungen.- Besuch einer Ausstellung.- Domino.- Vollständige Vielecke.- Zusätzliche Informationen.- Aufgaben.- Lösungshinweise.- 3 Durch alle Städte: Hamiltonsche Graphen.- Reisepläne.- Hamiltonsche Graphen.- Hamiltonsch und eulersch.- Hamiltonsche Kreise finden.- Hamiltonsche Graphen neu zeichnen.- ...dann ist der Graph nicht hamiltonsch.- Kreise und Wege.- Wie viele hamiltonsche Kreise gibt es?.- Reguläre Graphen.- Für Schachspieler.- Hamiltons Spiel.- Sitzordnungen.- Eine billige Rundreise.- Ein vielleicht unlösbares Problem.- Gesucht: Bäcker mit Kenntnissen in Graphentheorie.- Zusätzliche Informationen.- Aufgaben.- Lösungshinweise.- 4 Mehr über Grade von Ecken.- Tennis-Turniere.- Das handshaking lemma.- Ecken mit ungeradem Grad.- Schwierige Briefträgertouren.- Jeder gegen jeden.- Aufgaben.- Lösungshinweise.- 5 Bäume.- Was ist ein Baum?.- Wege in Bäumen.- Wie viele Kanten hat ein Baum?.- Äste absägen.- Aufspannende Bäume.- Labyrinthe, Irrgärten und Höhlen.- Straßenbahnen, Fischteiche und Bindfäden.- Eckengrade in Bäumen.- Die billigsten Straßen.- Der kürzeste Weg.- Die kürzeste Tour des Briefträgers.- Zusätzliche Informationen.- Aufgaben.- Lösungshinweise.- 6 Bipartite Graphen.- Ein Frühstücksgraph.- Bipartite Kreise.- Können Bäume bipartit sein?.- Bipartite Graphen erkennen.- Bipartite Graphen für Schachspieler.-Fachwerkhäuser.- Heiratsvermittlung mit Graphen.- Der Heiratssatz.- Eine Folgerung aus dem Heiratssatz.- Noch einmal: Der Frühstücksgraph.- Zusätzliche Informationen.- Aufgaben.- Lösungshinweise.- 7 Graphen mit Richtungen: Digraphen.- Was ist ein Digraph?.- Alles hat eine Richtung.- Wer hat gewonnen?.- Isomorphie bei Digraphen.- Lauter Einbahnstraßen.- Nur noch Einbahnstraßen?.- Eulersche Digraphen.- Hamiltonsche Digraphen.- Turniergraphen.- Wer ist der beste Spieler?.- Ranking kann fragwürdig sein.- Jeder Spieler hat gewonnen!.- Ein klarer Fall: Es gibt ein eindeutiges Ranking.- Könige und Vizekönige.- Hier ist jeder ein König!.- Wolf, Ziege und Kohlkopf.- Das Spiel Nim.- Umfüllaufgaben.- Graphen füir Zahlen.- Zusätzliche Informationen.- Aufgaben.- Lösungshinweise.- 8 Körper und Flächen.- Räumliche Graphen.- Andere Wege vom Körper zum Graphen.- Ebene und plättbare Graphen.- Sind alle Graphen plättbar?.- Elektrotechniker bevorzugen plättbare Graphen.- Ebene Graphen haben Flächen.- Die eulersche Formel.- Zwei neue Beweise.- Weitere Eigenschaften von Körpern aus der Sicht der Graphentheorie.- Die platonischen Körper.- Platonische Graphen.- Es gibt nicht mehr als 5 platonische Graphen.- Es gibt nur 5 platonische Körper.- Platonische Körper auf Kugeln.- Parkett-Fußboden.- Zusätzliche Informationen.- Aufgaben.- Lösungshinweise.- 9 Farben.- Farbige Landkarten.- Aus Landkarten werden Graphen.- Man kann auch Körper anmalen.- Wir färben alle Graphen.- Ampelschaltungen.- Ein moderner Zoo.- Das Problem mit den Museumswärtern.- Die chromatische Zahl kann nicht größer sein als.- Wie viele Farbmuster gibt es?.- Chromatische Polynome für beliebige Graphen.- Bekanntschaftsgraphen.- Befreundet bekannt unbekannt.- Kantenfärbung mit strengenRegeln.- Der chromatische Index eines vollständigen Vielecks.- Für den chromatischen Index kommen nur zwei Werte in Frage.- Lateinische Quadrate.- Zusätzliche Informationen.- Aufgaben.- Lösungshinweise.- Was ist was?.- Literatur.- Stichwortverzeichnis.