Graphen und Algorithmen
| Corporate Author: | |
|---|---|
| Format: | eBook |
| Language: | German |
| Published: |
Wiesbaden
Vieweg+Teubner Verlag
1994, 1994
|
| Edition: | 1st ed. 1994 |
| Series: | Leitfäden und Monographien der Informatik
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- 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
- 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
- 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