Graphen--Algorithmen--Programme

ISBN-13: 9783709188576 / Niemiecki / Miękka / 2012 / 192 str.

Hansjoachim Walther; Gunter Nagler

Spis treści

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.