Graphen'Algorithmen'Programme

Graphentheorie ist eine junge mathematische Disziplin, 1936 erschien das erste Lehrbuch yom ungarischen Mathematiker DENES KONIG. Mit der stiirmischen Ent wicklung der Operationsforschung erlebte auch die Graphentheorie eine ungeahnte Bliite, so daB die Zahl der Biicher zur Graphentheorie heute schon Legion ist. Das Gros der Autoren setzt jedoch beim Leser einen relativ hohen mathematischen Aus bildungsgrad sowie ein hohes Abstraktionsvermogen voraus. Wir verlangen yom Leser im allgemeinen nicht mehr mathematische Kenntnisse, als in den allgemein bildenden Schulen vermittelt werden (sieht man einmal von den Begriffen Vektor und Matrix ab) und auch nicht mehr als element are Kenntnisse iiber Programmierung (Ergibtanweisung, Laufanweisung, bedingter Sprung u. a. ). Was wir jedoch yom Leser erwarten, ist die Bereitschaft, sich Zeile fUr Zeile durch einen Algorithmus hindurchzuarbeiten. Dabei kann der Leser stiindig testen, ob er den behandelten Algorithmus verstanden hat, wenn er niimlich das sich anschlieBende Beispiel selb stiindig zu Ende fiihren kann. Kleine Aufgaben sind ebenfalls in die einzelnen Ab schnitte eingestreut. Das vorliegende Lehrbuch wendet sich an Studierende von Fach- und Hochschulen technischer, naturwissenschaftlicher und okonomischer Fachrichtungen, ferner an in der Praxis Tiitige, die sich mit Modellierung, Strukturanalyse und Optimierung diskreter Systeme befassen. Aber auch der Leser, welcher bloB SpaB an der Losung kombinatorischer Probleme hat, wird nicht umsonst zu diesem Buch greifen. 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.