Algorithmische Graphentheorie

Inhaltsverzeichnis

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

Pressestimmen

"Die Darstellung zeichnet sich durch Klarheit und Anschaulichkeit aus. [...] Prägnante Beispiele und die
Anwendung der Theorie auf wichtige Probleme der Informatik geben dem Buch einen hohen didaktischen Wert."
Prof. Dr. E. Rödel, Humboldt-Universität zu Berlin

Technik

Dieses eBook wird im PDF-Format ohne Kopierschutz geliefert. Sie können dieses eBook auf vielen gängigen Endgeräten lesen.

Für welche Geräte?
Sie können das eBook auf allen Lesegeräten, in Apps und in Lesesoftware öffnen, die PDF unterstützen:

• tolino Reader
  Öffnen Sie das eBook nach der automatischen Synchronisation auf dem Reader oder übertragen Sie es manuell auf Ihr tolino Gerät mit der kostenlosen Software Adobe Digital Editions.

• Andere eBook Reader
  Laden Sie das eBook direkt auf dem Reader im Hugendubel.de-Shop herunter oder übertragen Sie es mit der kostenlosen Software Sony READER FOR PC/Mac oder Adobe Digital Editions.

• Für Tablets und Smartphones: Unsere Gratis tolino Lese-App
       

• PC und Mac
  Lesen Sie das eBook direkt nach dem Herunterladen Herunterladen über "Jetzt lesen" im Browser oder mit der kostenlosen Lesesoftware Adobe Digital Editions.

Bitte beachten Sie: Dieses eBook ist nicht auf Kindle-Geräten lesbar.

Ihr erstes eBook?
Hier erhalten Sie alle Informationen rund um die digitalen Bücher für Neueinsteiger.