Graphen sind ein sehr häufig benutztes Modell bei der Beschreibung vielfältiger struk tureller Zusammenhänge, so z. B. zur Informationsübertragung 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 Einführung 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 Lehrbücher, insbeson dere in englischer Sprache. Da das Entwicklungstempo in dem ausgewählten Gebiet jedoch sehr hoch ist, erscheint es sinnvoll, von Zeit zu Zeit die Darstellung klassischer Gebiete durch die Darstellung ausgewählter Spezialgebiete zu ergänzen. Dies geschieht in dem vorliegenden Lehrbuch. Die ersten Kapitel sind klassischen Gebieten gewidmet: Euler- und Hamiltonkreise Durchsuchen von Graphen Minimalgerüste, greedy-Algorithmus und Matroide Kürzeste Wege Maximalfluß in Netzwerken Unabhängige Knoten- und Kantenmengen (Färbungen, "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, nämlich Graphen und Hypergraphen mit Baumstruktur (die eine Verallgemeinerung von Bäumen darstellen) sowie algorithmischer Nutzen dieser Strukturen 6 Im Unterschied zu bereits vorhandenen Lehrbüchern werden mehr die Struktureigen schaften von Graphen, die oftmals die Grundlage der Effizienz von Algorithmen bilden, und weniger die begleitenden Datenstrukturen der Algorithmen betont.

Klappentext

Graphen sind ein sehr häufig benutztes Modell bei der Beschreibung vielfältiger struk tureller Zusammenhänge, so z. B. zur Informationsübertragung 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 Einführung 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 Lehrbücher, insbeson dere in englischer Sprache. Da das Entwicklungstempo in dem ausgewählten Gebiet jedoch sehr hoch ist, erscheint es sinnvoll, von Zeit zu Zeit die Darstellung klassischer Gebiete durch die Darstellung ausgewählter Spezialgebiete zu ergänzen. Dies geschieht in dem vorliegenden Lehrbuch. Die ersten Kapitel sind klassischen Gebieten gewidmet: . Euler- und Hamiltonkreise . Durchsuchen von Graphen . Minimalgerüste, greedy-Algorithmus und Matroide . Kürzeste Wege . Maximalfluß in Netzwerken . Unabhängige Knoten- und Kantenmengen (Färbungen, "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, nämlich . Graphen und Hypergraphen mit Baumstruktur (die eine Verallgemeinerung von Bäumen darstellen) sowie . algorithmischer Nutzen dieser Strukturen 6 Im Unterschied zu bereits vorhandenen Lehrbüchern werden mehr die Struktureigen schaften von Graphen, die oftmals die Grundlage der Effizienz von Algorithmen bilden, und weniger die begleitenden Datenstrukturen der Algorithmen betont.

Inhalt
1 Graphen und algorithmische Graphenprobleme.- 1.1 Einführung, Grundbegriffe und Bezeichnungen.- 1.2 Bäume.- 1.3 Darstellung von Graphen im Computer.- 1.4 Polynomialzeit und NP-Vollständigkeit.- 1.5 Weitere Übungen.- 1.6 Lösungshinweise zu den Selbsttestaufgaben von Kapitel 1.- 1.7 Literaturhinweise.- 2 Eulerkreise und Hamiltonkreise.- 2.1 Ein einfaches Kriterium für die Existenz von Eulerkreisen.- 2.2 Ein Linearzeitalgorithmus zur Konstruktion von Eulerkreisen und -wegen.- 2.3 Hamiltonkreise und -wege.- 2.4 Weitere Übungen.- 2.5 Lösungshinweise zu den Selbsttestaufgaben von Kapitel 2.- 2.6 Literaturhinweise.- 3 Durchsuchen von Graphen Knotenreihenfolgen von Graphen.- 3.1 Tiefensuche (DFS) auf ungerichteten Graphen.- 3.2 Zweifach zusammenhängende Komponenten.- 3.3 DFS für gerichtete Graphen stark zusammenhängende Komponenten.- 3.4 Breitensuche (BFS).- 3.5 Topologisches Sortieren.- 3.6 Weitere Übungen.- 3.7 Lösungshinweise zu den Selbsttestaufgaben von Kapitel 3.- 3.8 Literaturhinweise.- 4 Minimalgerüste, greedy-Algorithmus und Matroide.- 4.1 Minimalgerüste.- 4.2 Greedy-Algorithmus und Matroide.- 4.3 Weitere Matroideigenschaften.- 4.4 Das Steinerbaumproblem.- 4.5 Weitere Übungen.- 4.6 Lösungshinweise zu den Selbsttestaufgaben von Kapitel 4.- 4.7 Literaturhinweise.- 5 Kürzeste Wege.- 5.1 Kürzeste Wege in dags von einem Knoten aus.- 5.2 Kürzeste Wege in gerichteten Graphen von einem Knoten aus.- 5.3 Kürzeste Wege zwischen je zwei Knoten.- 5.4 Semiringe und kürzeste Wege.- 5.5 Weitere Übungen.- 5.6 Lösungshinweise zu den Selbsttestaufgaben von Kapitel 5.- 5.7 Literaturhinweise.- 6 Das Maximalflußproblem.- 6.1 Flüsse und Schnitte.- 6.2 Der Algorithmus von Ford/Fulkerson.- 6.3 Der Algorithmus von Dinitz.- 6.4 Varianten des Maximalflußproblems.- 6.5 Weitere Übungen.- 6.6 Lösungshinweise zu den Selbsttestaufgaben von Kapitel 6.- 6.7 Literaturhinweise.- 7 Unabhängige Knoten- und Kantenmengen.- 7.1 Zuordnungen und ihre Bestimmung in paaren Graphen.- 7.2 Knoten- und Kantenüberdeckungen.- 7.3 Zuordnungen in beliebigen Graphen.- 7.4 Verallgemeinerungen des Zuordnungsproblems.- 7.5 Knotenfärbungen.- 7.6 Kantenfärbungen.- 7.7 Weitere Übungen.- 7.8 Lösungshinweise zu den Selbsttestaufgaben von Kapitel 7.- 7.9 Literaturhinweise.- 8 Graphen und Hypergraphen mit Baumstruktur.- 8.1 Chordale Graphen.- 8.2 Hypergraphen.- 8.3 Hyperbäume und duale Hyperbäume.- 8.4 Abpflückordnungen.- 8.5 Hyperbaum-Charakterisierungen und paare Inzidenzgraphen.- 8.6 Linearzeiterkennung von chordalen und dual chordalen Graphen.- 8.7 Weitere Übungen.- 8.8 Lösungshinweise zu den Selbsttestaufgaben von Kapitel 8.- 8.9 Literaturhinweise.- 9 Der algorithmische Nutzen von Baumstrukturen weitere Graphenklassen.- 9.1 Algorithmische Grundprobleme auf chordalen und dual chordalen Graphen.- 9.2 Partielle k-Bäume.- 9.3 Stark chordale Graphen.- 9.4 Intervallgraphen.- 9.5 Spezielle paare Graphen mit Chordalitätseigenschaften.- 9.6 Weitere Übungen.- 9.7 Lösungshinweise zu den Selbsttestaufgaben von Kapitel 9.- 9.8 Literaturhinweise.- 10 Ausgewählte Musterlösungen zu den Übungsaufgaben.