Algorithmische Graphentheorie

Kompakte Darstellung von Algorithmen in programmiersprachennaher Notation, die eine Übertragung in eine konkrete Programmiersprache wie C++ oder Pascal leicht macht.

Die meisten der 75 behandelten Algorithmen sind in der dargestellten Form im Rahmen von Lehrveranstaltungen implementiert und getestet worden. Das Buch enthält rund 250 Übungsaufgaben mit verschiedenen Schwierigkeitsgraden, vom Grundstudium bis hin zu höheren Semestern.

1;Vorwort;6 1.1;Vorwort zur 2. Auflage;6 1.2;Vorwort zur 1. Auflage;6 2;Inhaltsverzeichnis;10 3;Einleitung;16 3.1;1.1 Verletzlichkeit von Kommunikationsnetzen;17 3.2;1.2 Wegplanung für Roboter;18 3.3;1.3 Optimale Umrüstzeiten für Fertigungszellen;20 3.4;1.4 Objektorientierte Programmiersprachen;21 3.5;1.5 Suchmaschinen;25 3.6;1.6 Analyse sozialer Netze;28 3.7;1.7 Literatur;31 3.8;1.8 Aufgaben;31 4;Einführung;34 4.1;2.1 Grundlegende Definitionen;35 4.2;2.2 Spezielle Graphen;39 4.3;2.3 Graphalgorithmen;41 4.4;2.4 Datenstrukturen für Graphen;41 4.5;2.5 Der transitive Abschluß eines Graphen;46 4.6;2.6 Vergleichskriterien für Algorithmen;50 4.7;2.7 Implementierung von Graphalgorithmen;56 4.8;2.8 Greedy-Algorithmen;62 4.9;2.9 Zufällige Graphen;65 4.10;2.10 Literatur;66 4.11;2.11 Aufgaben;66 5;Bäume;72 5.1;3.1 Einführung;72 5.2;3.2 Anwendungen;75 5.3;3.3 Datenstrukturen für Bäume;85 5.4;3.4 Sortieren mit Bäumen;87 5.5;3.5 Vorrang-Warteschlangen;93 5.6;3.6 Minimal aufspannende Bäume;95 5.7;3.7 Literatur;102 5.8;3.8 Aufgaben;103 6;Suchverfahren in Graphen;108 6.1;4.1 Einleitung;109 6.2;4.2 Tiefensuche;109 6.3;4.3 Anwendung der Tiefensuche auf gerichtete Graphen;113 6.4;4.4 Kreisfreie Graphen und topologische Sortierung;115 6.5;4.5 Starke Zusammenhangskomponenten;119 6.6;4.6 Transitiver Abschluß und transitive Reduktion;122 6.7;4.7 Anwendung der Tiefensuche auf ungerichtete Graphen;127 6.8;4.8 Anwendung der Tiefensuche in der Bildverarbeitung;129 6.9;4.9 Blöcke eines ungerichteten Graphen;130 6.10;4.10 Breitensuche;136 6.11;4.11 Beschränkte Tiefensuche;141 6.12;4.12 Eulersche Graphen;144 6.13;4.13 Literatur;147 6.14;4.14 Aufgaben;148 7;Färbung von Graphen;154 7.1;5.1 Einführung;155 7.2;5.2 Anwendungen von Färbungen;161 7.3;5.3 Backtracking-Verfahren;164 7.4;5.4 Das Vier-Farben-Problem;167 7.5;5.5 Transitiv orientierbare Graphen;172 7.6;5.6 Literatur;179 7.7;5.7 Aufgaben;180 8;Flüsse in Netzwerken;188 8.1;6.1 Einleitung;188 8.2;6.2 Der Satz von Ford und Fulkerson;193 8.3;6.3 B
estimmung von Erweiterungswegen;195 8.4;6.4 Der Algorithmus von Dinic;203 8.5;6.5 0-1-Netzwerke;213 8.6;6.6 Kostenminimale Flüsse;216 8.7;6.7 Literatur;218 8.8;6.8 Aufgaben;219 9;Anwendungen von Netzwerkalgorithmen;224 9.1;7.1 Maximale Zuordnungen;225 9.2;7.2 Netzwerke mit oberen und unteren Kapazitäten;230 9.3;7.3 Eckenzusammenhang in ungerichteten Graphen;235 9.4;7.4 Kantenzusammenhang in ungerichteten Graphen;243 9.5;7.5 Minimale Schnitte;246 9.6;7.6 Literatur;254 9.7;7.7 Aufgaben;254 10;Kürzeste Wege;262 10.1;8.1 Einleitung;263 10.2;8.2 Das Optimalitätsprinzip;265 10.3;8.3 Der Algorithmus von Moore und Ford;269 10.4;8.4 Anwendungen auf spezielle Graphen;273 10.5;8.5 Bestimmung von Zentralitätsmaßen;279 10.6;8.6 Routingverfahren in Kommunikationsnetzen;283 10.7;8.7 Kürzeste-Wege-Probleme in der künstlichen Intelligenz;285 10.8;8.8 Kürzeste Wege zwischen allen Paaren von Ecken;299 10.9;8.9 Der Algorithmus von Floyd;302 10.10;8.10 Steiner Bäume;304 10.11;8.11 Literatur;308 10.12;8.12 Aufgaben;309 11;Approximative Algorithmen;316 11.1;9.1 Die Komplexitätsklassen P, NP und NPC;317 11.2;9.2 Einführung in approximative Algorithmen;321 11.3;9.3 Absolute Qualitätsgarantien;324 11.4;9.4 Relative Qualitätsgarantien;326 11.5;9.5 Approximative Färbungsalgorithmen;332 11.6;9.6 Das Problem des Handlungsreisenden;341 11.7;9.7 Literatur;350 11.8;9.8 Aufgaben;351 12;Anhang A;362 12.1;Angaben zu den Graphen an den Kapitelanfängen;362 13;Anhang B;366 13.1;Lösungen der Übungsaufgaben ;366 13.1.1;B.1 Kapitel 1;366 13.1.2;B.2 Kapitel 2;368 13.1.3;B.3 Kapitel 3;375 13.1.4;B.4 Kapitel 4;384 13.1.5;B.5 Kapitel 5;392 13.1.6;B.6 Kapitel 6;400 13.1.7;B.7 Kapitel 7;408 13.1.8;B.8 Kapitel 8;419 13.1.9;B.9 Kapitel 9;428 14;Literaturverzeichnis;446 15;Index;454