Inhalt

• Inhalt
• 1 Einführung
  • 1.1 Modellierungsmöglichkeiten von Graphen
  • 1.2 Grundtypen bei der Zielfindung
  • 1.3 Lösungsstrategien
• 2 Implementation von Graphen
• 3 Zusammenhangskomponenten
  • 3.1 Artikulationspunkt
  • 3.2 2-fach zusammenhängend
• 4 Union/Find
• 5 Minimum Spanning Tree
  • 5.1 Algorithmus von Kruskal
  • 5.2 Algorithmus von Prim
• 6 Kürzeste Wege Probleme
  • 6.1 Algorithmus von Dijkstra
  • 6.2 Strenge Zusammenhangskomponenten
  • 6.3 Transitiver Abschluß
  • 6.4 All pairs shortest path
  • 6.5 Pert
• 7 Location-Probleme
  • 7.1 Zentrum
• 8 Maximale Flüsse Probleme
  • 8.1 Fluß
  • 8.2 Erweiternder Weg
  • 8.3 Algorithmus von Ford-Fulkerson
  • 8.4 Cut
• 9 Kostenminimale Flüsse
  • 9.1 Erweiternder Kreis
• 10 Matching
  • 10.1 Maximum/maximales Matching
  • 10.2 Bipartiter Graph
  • 10.3 Erweiternder Weg
  • 10.4 (Erweiternder) alternierender Baum
  • 10.5 2-Prozessor Scheduling
  • 10.6 Vertexcover
  • 10.7 Independent Set
  • 10.8 Perfektes Matching
  • 10.9 Heiratsproblem
• 11 Traveling Salesman
• 12 Begriff der NP-Vollständigkeit
• 13 Näherungslösung für das Vertexcover Problem
• 14 Chinese Postman