Graphen—Algorithmen—Programme

Inhaltsverzeichnis

• 0. Einleitung.
• 1. Grundlagen.
• 1.1. Was ist ein Graph ?.
• 1.2. Beschreibung und Speicherung von Graphen.
• 1.3. Algorithmus und Programm.
• 1.4. Einfache Organisationsalgorithmen.
• 1.5. Abschätzungen des Aufwandes von Algorithmen.
• 2. Abstandsprobleme.
• 2.1. Einführung.
• 2.2. Erreichbarkeit.
• 2.2.1. Problemstellung.
• 2.2.2. Trémaux-Algorithmus.
• 2.2.3. Das Prinzip Depth-First-Search (DFS).
• 2.2.4. Das Prinzip Breadth-First-Search (BFS).
• 2.3. Wurzelbäume.
• 2.3.1. Beispiele.
• 2.3.2. Ordnungen in Wurzelbäumen.
• 2.4. Zusammenhang.
• 2.5. Starker Zusammenhang.
• 2.6. Kreisfreiheit.
• 2.7. Kürzeste Wege.
• 2.7.1. Beispiele.
• 2.7.2. Nichtnegative Bogenlängen.
• 2.7.3. Beliebige reelle Bogenlängen.
• 2.7.4. Kaskadealgorithmus und Floyd-Algorithmus.
• 2.8. Radius und Zentrum.
• 2.8.1. Beispiele.
• 2.8.2. Definitionen und Aufgabenstellung.
• 2.8.3. Algorithmus zur Radius- und Zentrumsermittlung.
• 2.8.4. Zentrumsmengen.
• 2.9. Längste Wege.
• 2.9.1. Beispiele.
• 2.9.2. Längste Wege und Kreisfreiheit.
• 2.9.3. Graphen ohne Kreise.
• 2.9.4. Graphen mit Kreisen.
• 2.10. Minimalgerüst.
• 2.10.1. Aufgabenstellung.
• 2.10.2. Grundidee zur Lösung des Minimalgerüstproblems.
• 2.10.3. Greedyalgorithmen.
• 2.10.4. Ein Algorithmus vom Aufwand O(mn).
• 2.10.5. Ein Algorithmus vom Aufwand O(m · log n).
• 2.11. Das Steiner-Problem.
• 2.11.1. Aufgabenstellung.
• 2.11.2. Eigenschaften von Minimalnetzen.
• 2.11.3. Konstruktion eines Minimalnetzes.
• 2.11.4. Algorithmus zur Ermittlung eines Steiner-Netzes.
• 2.11.5. Kostenabhängigkeit.
• 3. Strom- und Transportprobleme.
• 3.1. Beispiele und Definitionen.
• 3.2. Elektrische Netze.
• 3.2.1. Aufgabenstellung.
• 3.2.2. Mathematische Sätze.
• 3.2.3. Methoden zur Lösung der Gleichungssysteme.
• 3.2.4. Eine mathematische Perle.
• 3.3. Maximalstromproblem.
• 3.3.1. Problemformulierung.
• 3.3.2. Eine Ersatzaufgabe.
• 3.3.3. Verbalalgorithmus zur Lösung des Maximalstromproblems MAX 2 und PASCAL-procedure.
• 3.4. Zirkulationsproblem.
• 3.4.1. Problemstellung und Beispiele.
• 3.4.2. Das Optimalitätskriterium.
• 3.4.3. Die Idee des out-of-kilter-Algorithmus.
• 3.4.4. Verbalalgorithmus und PASCAL-procedure TRANSPORT.
• 3.5. Das Zuordnungsproblem.
• 3.5.1. Aufgabenstellung.
• 3.5.2. Der Satz von König.
• 3.5.3. Verbalalgorithmus zur Lösung des Zuordnungsproblems.
• 3.5.4. Ein Beispiel.
• 3.5.5. PASCAL-procedure ZUORDNUNG.
• 3.6. Das Rundreiseproblem.
• 3.6.1. Aufgabenstellung.
• 3.6.2. Ein Verfahren, basierend auf dem Prinzip branch-and-bound.
• 3.6.3. Verbalalgorithmus zur exakten Lösung des Rundreiseproblems.
• 3.6.4. Näherungsverfahren zur Lösung des Rundreiseproblems und PASCAL-procedures.
• 4. Parameterprobleme.
• 4.1. Innere Stabilitätszahl.
• 4.1.1. Beispiele und Probleme.
• 4.1.2. Verbalalgorithmus zur Ermittlung innerlich stabiler Mengen und PASCAL-procedure.
• 4.2. Chromatische Zahl.
• 4.2.1. Problemstellung.
• 4.2.2. Definitionen und Sätze.
• 4.2.3. Verbalalgorithmen zur zulässigen Färbung eines Graphen.
• 4.2.4. PASCAL-procedure zur Minimalgradfolge und zulässiger Färbung.
• 4.2.5. Exakter Algorithmus zur Bestimmung der chromatischen Zahl und PASCAL-procedure.
• 4.2.6. Prozedur zur Ermittlung der chromatischen Zahl.
• 4.3. Dominierende Knotenmengen.
• 4.3.1. Beispiele und Aufgabenstellung.
• 4.3.2. Definitionen, Verbalalgorithmus und PASCAL-procedure.
• 4.4. Maximumpaarung.
• 4.4.1. Aufgabenstellung.
• 4.4.2. Erforderliche Sätze.
• 4.4.3. Verbalalgorithmus.
• 4.4.4. PASCAL-procedure zur Näherung an eine Maximumpaarung.
• 4.5. Planarität von Graphen.
• 4.5.1. Problemstellung.
• 4.5.2. Planaritätssätze.
• 4.5.2.1. Der Satz von Kuratowski.
• 4.5.2.2. Der Satz von McLane.
• 4.5.2.3. Der Satz von Whitney.
• 4.5.3. Planaritätsalgorithmen.
• 4.6. Bemerkungen zur Auswertung von Rechenbeispielen.
• Literatur- und Quellenverzeichnis.
• Sachwortverzeichnis.