Algorithmische Graphentheorie
Deterministische und randomisierte Algorithmen
5. erweiterte und überarbeitete Auflage
Jedes System, das aus diskreten Zuständen oder Objekten und Beziehungen zwischen diesen besteht, kann als Graph modelliert werden. Diese Darstellung ermöglicht den Einsatz graphentheoretischer Algorithmen. Das vorliegende Buch stellt grundlegende Algorithmen zur Lösung graphentheoretischer Problemstellungen anhand praktischer Beispiele vor. Die Algorithmen sind in kompakter Form in einer programmiersprachennahen Notation dargestellt, die eine Übertragung in eine konkrete Implementierung leicht macht. Die praktische Relevanz der behandelten Algorithmen wird in vielen Anwendungen aus Gebieten wie Compilerbau, Künstlicher Intelligenz, Betriebssystemen, Computernetzwerken, Suchmaschinen, Analyse sozialer Netzwerke und Operations Research demonstriert.
Die Methoden der algorithmischen Graphentheorie werden immer weiter entwickelt. Somit muss ein Lehrbuch zu diesem Thema auch stets aktualisiert werden. Die fünfte Auflage wurde um ein Kapitel über randomisierte Algorithmen und deren Analyse erweitert. Randomisierte Algorithmen sind in vielen Fällen einfacher zu verstehen, einfacher zu implementieren und oft effizienter als deterministische Algorithmen. Das neue Kapitel behandelt zahlreiche Anwendungen innerhalb der algorithmischen Graphentheorie und zeigt damit das Potential dieser Methodik. Neben einem neuen Kapitel wurden einige vorhandene Themen erweitert und besser bebildert. Ferner wurden neue Aufgaben hinzugefügt und kleinere Korrekturen vorgenommen.
Das Buch enthält mittlerweile fast 300 Übungsaufgaben in verschiedenen Schwierigskeitsgraden, für das Bachelor- und das Masterstudium. Die Lösungen sind wie bisher kostenfrei über die Webseite des Verlags verfügbar.
Die Highlights der 5. Auflage
- Inhaltlich aktualisierte 5. Auflage mit farbiger Bebilderung.
- Neues Kapitel über randomisierte Algorithmen.
- Praktisch anwendbare Algorithmen für graphentheoretische Probleme.
- Ca. 300 Übungsaufgaben mit online verfügbaren Lösungen.
Wissenswertes zum Titelbild des Buches
Der dargestellte Graph wurde nach dem Mathematiker Alfred Clebsch benannt. Er entdeckte den Graphen im Jahr 1868 im Zusammenhang mit seinen Untersuchungen zur Darstellungstheorie der Drehgruppe. Der Clebsch-Graph ist ein regulärer, ungerichteter Graph mit 16 Ecken und 40 Kanten. Er hat die chromatische Zahl 4, ist ein hamiltonscher Graph und hat den Durchmesser 2. Der Clebsch-Graph entsteht beispielsweise aus einem Hypercube der Dimension fünf in dem alle fünf Paare von Ecken mit Distanz fünf kontrahiert werden. Alfred Clebsch stieß in seinen Forschungsarbeiten auf diesen Graph als er distanztransitive Graphen betrachtete. Dabei handelt es sich um Graphen, bei denen es zu je zwei Paaren von Ecken `e_1, e_2` und `f_1, f_2` mit `d(e1, e2) = d(f1, f2)` einen Automorphismus des Graphen gibt, der `e_1` auf `f_1` und `e_2` auf `f_2` abbildet. Der Clebsch-Graph ist distanztransitiv.
