Graphen- Und Netzwerkoptimierung

ISBN-13: 9783827424228 / Niemiecki / Miękka / 2010 / 265 str.

Christina Büsing

Opis

Alle Wege führen nach Rom!" Aber welcher ist der beste wie findet mein Navi den Weg überhaupt? Und was ist mit einer Rundreise durch Europas Hauptstädte? §§Diese Fragen bilden nur einen kleinen Teilaspekt der Themen dieses Buches. Anhand vieler Praxissituationen werden die Begriffe der Graphentheorie und Netzwerkoptimierung eingeführt und die aufgeworfenen Probleme anschließend mit Hilfe von Algorithmen gelöst. §§Das Buch richtet sich an Studierende der Mathematik und Informatik in den ersten Semestern sowie an interessierte Praktiker. Es enthält eine Vielzahl an Anwendungsbeispielen sowie wichtige in der Praxis relevanten Algorithmen mit dem Beweis ihrer Optimalität. §§Spezielle mathematische Vorkenntnisse sind nicht erforderlich: Sämtliche Begriffe und Methoden werden auf verständliche Weise eingeführt. Das so erworbene Wissen kann anhand zahlreicher Übungsaufgaben und deren Lösungen vertieft und überprüft werden.

Spis treści

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

O autorze

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.