Graphentheoretische Konzepte und Algorithmen

Graphen und Netzwerke sind wichtige Modellierungs-Werkzeuge in natur-, ingenieur-, wirtschafts­ und sozialwissenschaftlichen Problembereichen. Der Entwurf und die Analyse von effizienten Me­ thoden zur Lösung von »Problemen auf Graphen« sind daher Schlüssel zur Lösung vieler prakti­ scher Probleme. Der Schwerpunkt dieses Buches liegt auf einer Einführung in graphentheoretische Konzepte und Algorithmen. Es basiert auf den Vorlesungen »Graphentheoretische Konzepte und Algorithmen« und »Netzwerk-Optimierung«, welche die Autoren in den letzten Jahren an den Universitäten Würz­ burg und Kaiserslautern gehalten haben, sowie dem Selbstudienkurs »Graphentheoretische Konzep­ te und Algorithmen« der Virtuellen Hochschule Bayern (VHB). Wir richten uns an Leser, die ma­ thematische Grundkenntnisse besitzen, insbesondere an Informatik- und Mathematik-Studentinnen und -Studenten im Bachelor- und Masterstudium. Das Buch ist aus einem gleichnamigen Skript hervorgegangen. Ingo Demgensky und Dr. Hans­ Christoph Wirth haben hier viele Anregungen und Beiträge geliefert, wofür wir uns bedanken. Wir bedanken uns außerdem bei Dr. Elisabeth Gassner, Stefan Ruzika, SIeman Saliba, Prof. Dr. Martin Skutella, Stephan Westphal und Johannes Hoffart für das sorgfältige Korrekturlesen, zahlreiche Verbesserungsvorschläge und anregende Diskussionen. Alle verbleibenden Fehler sind allein unser Versäumnis. Kaiserslautern / Würzburg, im April 2005 Sven O. Krumke, Hartmut Noltemeier Inhaltsverzeichnis 1 Einleitung 1 1.1 Routenplanung . . . . . . . . .