Graphen Und Algorithmen

ISBN-13: 9783519021315 / Niemiecki / Miękka / 1994 / 264 str.

Andreas Brandstadt; Andreas Brandstadt

Opis

Graphen sind ein sehr haufig benutztes Modell bei der Beschreibung vielfaltiger struk tureller Zusammenhange, so z. B. zur Informationsubertragung in Kommunikations netzwerken, zum Transport von Waren oder zur Beschreibung hierarchischer Struktu ren. Die Behandlung dieser Modelle mit den Mitteln der algorithmischen Graphentheorie stellt ein wichtiges Teilgebiet der Mathematik und Informatik dar. Das vorliegende Lehrbuch vermittelt eine Einfuhrung in dieses sich rasch entwickelnde Forschungsgebiet, wobei lediglich einfache Grundkenntnisse in Mathematik und Infor matik vorausgesetzt werden, die i. a. im Grundstudium erworben werden. Zum Thema "Graphen und Algorithmen" gibt es bereits einige Lehrbucher, insbeson dere in englischer Sprache. Da das Entwicklungstempo in dem ausgewahlten Gebiet jedoch sehr hoch ist, erscheint es sinnvoll, von Zeit zu Zeit die Darstellung klassischer Gebiete durch die Darstellung ausgewahlter Spezialgebiete zu erganzen. Dies geschieht in dem vorliegenden Lehrbuch. Die ersten Kapitel sind klassischen Gebieten gewidmet: Euler- und Hamiltonkreise Durchsuchen von Graphen Minimalgeruste, greedy-Algorithmus und Matroide Kurzeste Wege Maximalfluss in Netzwerken Unabhangige Knoten- und Kantenmengen (Farbungen, "matchings") Die letzten beiden Kapitel beschreiben neuere Ergebnisse aus den 80er und 90er Jah ren, die in Lehrbuchform noch nicht erschienen sind und einen zentralen Aspekt der algorithmischen Graphentheorie darstellen, namlich Graphen und Hypergraphen mit Baumstruktur (die eine Verallgemeinerung von Baumen darstellen) sowie algorithmischer Nutzen dieser Strukturen 6 Im Unterschied zu bereits vorhandenen Lehrbuchern werden mehr die Struktureigen schaften von Graphen, die oftmals die Grundlage der Effizienz von Algorithmen bilden, und weniger die begleitenden Datenstrukturen der Algorithmen betont

Spis treści

Graphen und algorithmische Graphenprobleme - Eulerkreis und Hamiltonkreise - Durchsuchen von Graphen - Knotenreihenfolgen von Graphen - Minimalgerüste - greedy-Algorithmus und Matroide - Kürzeste Wege - Das Maximalflußproblem - unabhängige Knoten- und Kantenmengen - Graphen und Hypergraphen mit Baumstruktur - Der algorithmische Nutzen von Baumstrukturen, weitere Graphenklassen - Ausgewählte Musterlösungen zu den Übungsaufgaben