Graphen und Graphalgorithmen

Das Buch ist aus Vorlesungen, die der Autor an der Universität Oldenburg gehalten hat, hervorgegangen. Es wird mittels a-Wegen und f-Wegen in allgemeinen Graphen ein einheitlicher Rahmen für die Darstellung der algorithmischen Grapentheorie eingeführt. Allgemeine Graphen sind Graphen, in denen ungerichtete Kanten und gerichtete Bögen gemischt auftreten dürfen, auch mehrfach zwischen zwei gegebenen Knoten. a-Wege sind alternierende Folgen von Knoten und Kanten/Bögen, bei denen Bögen in beliebiger Richtung durchlaufen werden dürfen. Bei f-Wegen ist das nur in Bogenrichtung erlaubt. Man gewinnt damit an Klarheit und viele Dinge, die sonst lose nebeneinander stehen, fügen sich jetzt gut zusammen. In den ersten acht Kapiteln werden die elementaren Teile der algorithmischen Graphentheorie unbewerteter Graphen behandelt: Grundlagen, Wege und einfacher Zusammenhang, Tiefen- und Breitensuche, zweifacher Zusammenhang, Perioden und Partitionen. Der Zugang zum zweifachen Zusammenhang als ,, standard-a-Zerlegung" allgemeiner Graphen ist neu. Unüblich ist auch die Behandlung von Perioden und Partitionen. Die letzten drei Kapitel sind schwierigerem Stoff gewidmet. Der Satz von Menger und seine Varianten sowie die zugehörigen Algorithmen sind Inhalt von Kapitel 9. Die Zerlegung allgemeiner Graphen in Zusammenhangskomponenten höherer Ordnung wird in Kapitel 10 diskutiert. Kapitel 11 schließlich behandelt die algorithmische Gewinnung solcher Zerlegungen. Zu jedem Kapitel gibt es Übungsaufgaben und Literaturangaben.