Graphen- und Netzwerkoptimierung

1 Erste Orientierung in der Graphentheorie.1.1 Erster Schultag.1.2 Zusammenhang und Schnitte.1.3 Bäume.1.4 Aufgaben.-2 Tiefen- und Breitensuche.2.1 Spannende Bäume.2.2 Wie findet man spannende Bäume?.2.3 Anwendungen von BFS und DFS.2.4 Aufgaben.-3 Das Minimal-Spannende-Baum-Problem.3.1 Das Problem und zwei Algorithmen.3.2 Zwei Optimalitätskriterien.3.3 Aufgaben.-4 Euler-Touren und -Wege.4.1 Das Königsberger Brückenproblem.4.2 Die Algorithmen von Hierholzer und Fleury.4.3 Euler-Wege oder das Haus vom Nikolaus.4.4 Aufgaben.-5 Noch zwei Rundreise-Probleme.5.1 Hamilton und das Icosian-Spiel.5.2 Das Travelling-Salesman-Problem.5.3 Komplexitätstheorie.5.4 Aufgaben.-6 Planarität.6.1 Gas-Wasser-Strom und Planarität.6.2 Outerplanare Graphen.6.3 Die Euler-Formel.6.4 K3,3, K5 und Kuratowski.6.5 Aufgaben.7 Knotenfärbung.7.1 Die chromatische Zahl.7.2 Das Vier-Farben-Problem.7.3 Aufgaben.-8 Gerichtete Graphen und Turniergraphen.8.1 Gerichtete Graphen - Digraphen.8.2 Starker Zusammenhang.8.3 Gerichtete Euler-Graphen.8.4 Hamilton-Wege in Turniergraphen.8.5 Könige in Turniergraphen.8.6 Aufgaben.-9 Kürzeste Wege.9.1 Der Kürzeste-Wege-Baum.9.2 Ein Optimalitätskriterium und der Dijkstra-Algorithmus.9.3 Negative Kosten.9.4 Aufgaben.-10 Maximale Flüsse.10.1 Flüsse und der Dekompositionssatz von Ford-Fulkerson.10.2 Das maximale Fluss-Problem.10.3 Der Max-Fluss-Min-Schnitt-Satz.10.4 Aufgaben.-11 Kostenminimale Flüsse.11.1 Problemstellung.11.2 Ein Optimalitätskriterium.11.3 Zwei Algorithmen.11.4 Aufgaben.-12 Maximale Matching.12.1 Definition und ein Optimalitätskriterium.12.2 Matchings in bipartiten Graphen.12.3 Aufgaben.-13 Lösungshinweise.-A Grundlegende Beweismethoden.A.1 Folgerungen und Äquivalenzen.A.2Negationen.A.3 Beweis durch Widerspruch.A.3.1 Beispiel: Satz von Euklid.A.4 Vollständige Induktion.A.5 Ringschluss.-B Zeichen und Symbole.B.1 Aus der Mengentheorie.B.2 Aus der Arithmetik.B.3 Zwei Quantoren.-Literaturverzeichnis.-Index

Christina Büsing studierte Mathematik als Stipendiatin des Cusanuswerks in Münster, Madrid und Berlin, bevor sie 2007 eine Promotion an der Technischen-Universität Berlin im Bereich der kombinatorischen Optimierung aufnahm. Dort beschäftigt sie sich im Rahmen des Graduiertenkollegs "Methods for Discrete Structures" mit dem Konzept der robusten Optimierung und deren Anwendungen auf Praxisprobleme.

Eine wirklich schöne und kompakte Einführung in die Graphentheorie und kombinatorische Optimierung, die auch für Lehramtsstudierende sehr gut zugänglich ist.Dipl.-Math. Frank Förster, TU Braunschweig