Algorithmische Graphentheorie
Kapitel 3: Bäume
Eine für Anwendungen sehr wichtige Klasse von Graphen sind Bäume. In vielen Gebieten wie z.B. beim Compilerbau oder bei Datenbanksystemen werden sie häufig zur Darstellung von hierarchischen Beziehungen verwendet. In diesem Kapitel werden Anwendungen von Bäumen und ihre effiziente Darstellung beschrieben. Es wird ein auf Bäumen basierender Sortieralgorithmus vorgestellt und eine effiziente Realisierung von Vorrang-Warteschlangen diskutiert. Ferner werden zwei Algorithmen zur Bestimmung von minimalen aufspannenden Bäumen und ein Verfahren zur Datenkompression beschrieben.
Kapitelübersicht
- Einleitung
- Einführung
- Bäume
- Einführung
- Anwendungen
- Datenstrukturen für Bäume
- Sortieren mit Bäumen
- Vorrang-Warteschlangen
- Minimal aufspannende Bäume
- Literatur
- Aufgaben
- Suchverfahren in Graphen
- Entwurfsmethoden für die algorithmische Graphentheorie
- Färbung von Graphen
- Perfekte Graphen
- Flüsse in Netzwerken
- Anwendungen von Netzwerkalgorithmen
- Kürzeste Wege
- Approximative Algorithmen
