Algorithmische Graphentheorie, 4th Edition

Algorithmische Graphentheorie, 4th Edition

by Volker Turau, Christoph Weyer
Released September 2015
Publisher(s): De Gruyter
ISBN: 9783110420005

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

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 die grundlegenden Algorithmen zur Lösung graphentheoretischer Problemstellungen anhand praktischer Beispiele aus der Informatik 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. Elf Kapitel decken die wichtigsten Teilgebiete der Algorithmischen Graphentheorie ab. Die vorliegende vierte, erweiterte und überarbeitete Auflage des Buches zeichnet sich unter anderem durch ein neues umfangreiches Kapitel über Entwurfsmethoden der Algorithmischen Graphentheorie aus.

Das Buch enthält 280 Übungsaufgaben in verschiedenen Schwierigkeitsgraden, für das Bachelor- und das Masterstudium. Die ausführlichen Lösungen können kostenlos bezogen werden.

Table of contents

  1. Cover
  2. Titel
  3. Impressum
  4. Inhalt
  5. 1 Einleitung
    1. 1.1 Verletzlichkeit von Kommunikationsnetzen
    2. 1.2 Wegplanung für Roboter
    3. 1.3 Optimale Umrüstzeiten für Fertigungszellen
    4. 1.4 Objektorientierte Programmiersprachen
    5. 1.5 Suchmaschinen
    6. 1.6 Analyse sozialer Netze
    7. 1.7 Literatur
    8. 1.8 Aufgaben
  6. 2 Einführung
    1. 2.1 Grundlegende Definitionen
    2. 2.2 Spezielle Graphen
    3. 2.3 Graphalgorithmen
    4. 2.4 Datenstrukturen für Graphen
      1. 2.4.1 Adjazenzmatrix
      2. 2.4.2 Adjazenzliste
      3. 2.4.3 Kantenliste
      4. 2.4.4 Bewertete Graphen
      5. 2.4.5 Implizite Darstellung
    5. 2.5 Der transitive Abschluss eines Graphen
    6. 2.6 Vergleichskriterien für Algorithmen
    7. 2.7 Implementierung von Graphalgorithmen
    8. 2.8 Testen von Graph-Algorithmen
    9. 2.9 Literatur
    10. 2.10 Aufgaben
  7. 3 Bäume
    1. 3.1 Einführung
    2. 3.2 Anwendungen
      1. 3.2.1 Hierarchische Dateisysteme
      2. 3.2.2 Ableitungsbäume
      3. 3.2.3 Suchbäume
      4. 3.2.4 Datenkompression
    3. 3.3 Datenstrukturen für Bäume
      1. 3.3.1 Darstellung mit Feldern
      2. 3.3.2 Darstellung mit Adjazenzlisten
    4. 3.4 Sortieren mit Bäumen
    5. 3.5 Vorrang-Warteschlangen
    6. 3.6 Minimal aufspannende Bäume
      1. 3.6.1 Der Algorithmus von Kruskal
      2. 3.6.2 Der Algorithmus von Prim
    7. 3.7 Literatur
    8. 3.8 Aufgaben
  8. 4 Suchverfahren in Graphen
    1. 4.1 Einleitung
    2. 4.2 Tiefensuche
    3. 4.3 Anwendung der Tiefensuche auf gerichtete Graphen
    4. 4.4 Kreisfreie Graphen und topologische Sortierung
      1. 4.4.1 Rekursion in Programmiersprachen
      2. 4.4.2 Topologische Sortierung
    5. 4.5 Starke Zusammenhangskomponenten
    6. 4.6 Transitiver Abschluss und transitive Reduktion
    7. 4.7 Anwendung der Tiefensuche auf ungerichtete Graphen
      1. 4.7.1 Bestimmung der Zusammenhangskomponenten
      2. 4.7.2 Durchsatz und Querschnitt
      3. 4.7.3 Anwendung in der Bildverarbeitung
      4. 4.7.4 Blöcke eines ungerichteten Graphen
    8. 4.8 Breitensuche
    9. 4.9 Lexikographische Breitensuche
    10. 4.10 Beschränkte Tiefensuche
    11. 4.11 Eulersche Graphen
    12. 4.12 Literatur
    13. 4.13 Aufgaben
  9. 5 Entwurfsmethoden für die algorithmische Graphentheorie
    1. 5.1 Problemarten
    2. 5.2 Greedy-Technik
    3. 5.3 Backtracking
    4. 5.4 Branch & Bound
    5. 5.5 Teile & Herrsche
    6. 5.6 Dynamische Programmierung
    7. 5.7 Lineare Programmierung
    8. 5.8 Literatur
    9. 5.9 Aufgaben
  10. 6 Färbung von Graphen
    1. 6.1 Einführung
    2. 6.2 Anwendungen von Färbungen
      1. 6.2.1 Maschinenbelegungen
      2. 6.2.2 Registerzuordnung in Compilern
      3. 6.2.3 Public-Key Kryptosysteme
      4. 6.2.4 Sudoku
    3. 6.3 Exakte Bestimmung der chromatischen Zahl
      1. 6.3.1 Backtracking-Verfahren
      2. 6.3.2 Teile & Herrsche
      3. 6.3.3 Dynamische Programmierung
      4. 6.3.4 Lineare Programmierung
    4. 6.4 Heuristiken zur Bestimmung von Färbungen
    5. 6.5 Das Vier-Farben-Problem
    6. 6.6 Kantenfärbungen
    7. 6.7 Literatur
    8. 6.8 Aufgaben
  11. 7 Perfekte Graphen
    1. 7.1 Einführung
    2. 7.2 Kreisfreie Orientierungen
    3. 7.3 Transitiv orientierbare Graphen
      1. 7.3.1 Charakterisierung von transitiv orientierbaren Graphen
      2. 7.3.2 Färbungen von transitiv orientierbaren Graphen
    4. 7.4 Permutationsgraphen
      1. 7.4.1 Charakterisierung von Permutationsgraphen
      2. 7.4.2 Färbungen von Permutationsgraphen
    5. 7.5 Chordale Graphen
      1. 7.5.1 Charakterisierung von chordalen Graphen
      2. 7.5.2 Färbungen von chordalen Graphen
    6. 7.6 Intervallgraphen
      1. 7.6.1 Gewichtete unabhängige Mengen in Intervallgraphen
    7. 7.7 Literatur
    8. 7.8 Aufgaben
  12. 8 Flüsse in Netzwerken
    1. 8.1 Einleitung
    2. 8.2 Schnitte und Erweiterungswege
    3. 8.3 Der Satz von Ford-Fulkerson
    4. 8.4 Bestimmung von Erweiterungswegen
    5. 8.5 Der Algorithmus von Dinic
    6. 8.6 0-1-Netzwerke
    7. 8.7 Kostenminimale Flüsse
    8. 8.8 Literatur
    9. 8.9 Aufgaben
  13. 9 Anwendungen von Netzwerkalgorithmen
    1. 9.1 Maximale Zuordnungen
    2. 9.2 Netzwerke mit oberen und unteren Kapazitäten
    3. 9.3 Eckenzusammenhang in ungerichteten Graphen
    4. 9.4 Kantenzusammenhang in ungerichteten Graphen
    5. 9.5 Minimale Schnitte
    6. 9.6 Eckenüberdeckungen
    7. 9.7 Literatur
    8. 9.8 Aufgaben
  14. 10 Kürzeste Wege
    1. 10.1 Einleitung
    2. 10.2 Das Optimalitätsprinzip
    3. 10.3 Der Algorithmus von Moore und Ford
    4. 10.4 Anwendungen auf spezielle Graphen
      1. 10.4.1 Graphen mit konstanter Kantenbewertung
      2. 10.4.2 Graphen ohne geschlossene Wege
      3. 10.4.3 Graphen mit nichtnegativen Kantenbewertungen
      4. 10.4.4 Graphen mit ganzzahligen nichtnegativen Kantenbewertungen
    5. 10.5 Bestimmung von Zentralitätsmaßen
    6. 10.6 Routingverfahren in Kommunikationsnetzen
    7. 10.7 Kürzeste-Wege-Probleme in der künstlichen Intelligenz
      1. 10.7.1 Der A*-Algorithmus
      2. 10.7.2 Der iterative A*-Algorithmus
      3. 10.7.3 Umkreissuche
    8. 10.8 Kürzeste Wege zwischen allen Paaren von Ecken
    9. 10.9 Der Algorithmus von Floyd
    10. 10.10 Steinerbäume
    11. 10.11 Literatur
    12. 10.12 Aufgaben
  15. 11 Approximative Algorithmen
    1. 11.1 Die Komplexitätsklassen P, NP und NPC
    2. 11.2 Einführung in approximative Algorithmen
    3. 11.3 Absolute Qualitätsgarantien
    4. 11.4 Relative Qualitätsgarantien
    5. 11.5 Approximative Algorithmen
      1. 11.5.1 Minimale Färbungen
      2. 11.5.2 Minimale Eckenüberdeckungen
      3. 11.5.3 Minimale dominierende Mengen
      4. 11.5.4 Maximale unabhängige Mengen
      5. 11.5.5 Minimale Steinerbäume
    6. 11.6 Das Problem des Handlungsreisenden
    7. 11.7 Literatur
    8. 11.8 Aufgaben
  16. Die Graphen an den Kapitelanfängen
  17. Literatur
  18. Index

Product information

  • Title: Algorithmische Graphentheorie, 4th Edition
  • Author(s): Volker Turau, Christoph Weyer
  • Release date: September 2015
  • Publisher(s): De Gruyter
  • ISBN: 9783110420005