Graphen- und Netzwerkoptimierung

Inhaltsangabe1 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.2 Negationen.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