Graphen und Algorithmen

Inhaltsverzeichnis

• 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.