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