Graphen und Anwendungen

Eine Einführung für Studierende der Natur-, Ingenieur- und Wirtschaftswissenschaften
von Prof. Dr. Günter Nägler und Prof. Dr. Friedmar Stopp

B.G. Teubner Verlagsgesellschaft Stuttgart Leipzig 1996
ISBN 3-8154-2084-9 / 24.80 DM

Inhalt

1 Einführung
1.1 Zur Entwicklung der Graphentheorie
1.2 Einführende Beispiele
1.3 Aufgaben: Modellierung mit Graphen

2 Grundlagen
2.1 Graphen und Matrizen
2.1.1 Matrizenrechnung
2.1.2 Matrizen für Graphen
2.1.3 Tripelalgorithmus
2.1.4 Aufgaben: Graphen und Matrizen
2.2 Komplexität von Algorithmen und Problemen
2.2.1 Ordnungssymbole O und o
2.2.2 Asymptotische Gleichheit
2.2.3 Zeitkomplexität von Algorithmen
2.2.4 Komplexität von Problemen
2.2.5 Aufgaben: Komplexität

3 Graphen
3.1 Definition des Graphen
3.2 Listendarstellung des Graphen
3.3 Die Datenstruktur Graph
3.4 Grundbegriffe
3.5 Aufgaben

4 Bäume und Gerüste
4.1 Definition, Darstellung und Eigenschaften von Bäumen und Gerüsten
4.2 Bäume als Suchstrukturen
4.2.1 Binärbäume als Datenstrukturen
4.2.2 B-Bäume
4.3 Stützgerüste zur Zyklen- und Cozyklenerzeugung
4.4 Aufgaben

5 Optimierung auf Graphen mit einer Bogenbewertung
5.1 Voronoi-Diagramm und Minimalgerüst
5.2 Erreichbarkeit und Wegminierung
5.3 Matchings
5.4 Aufgaben

6 Stromprobleme
6.1 Strom und Spannung
6.2 Minimalkosten-Stromprobleme
6.2.1 Problemstellung und Anwendungen
6.2.2 Mathematische Grundlagen des Lösungsalgorithmus
6.2.3 Algorithmus zur Lösung des Problems 6.1
6.2.4 Beispiele, Aufgaben, unzulässige Lösungen
6.3 Maximalflußproblem
6.4 Minimalkosten-Stromproblem mit einem freien Parameter
6.5 Aufgaben

7 Potentialprobleme
7.1 Minimalkosten-Potentialproblem
7.2 Klassische Netzplantechnik
7.3 Erweitertes Netzplanmodell
7.4 Aufgaben

8 Testgraphen
8.1 Einführung
8.2 Anzahlformeln
8.2.1 Numerierte und unnmumerierte Graphen
8.2.2 Digraphen mit n Knoten und m Bögen
8.2.3 Zusammenhängende Digraphen
8.2.4 Digraphen mit gegebener Dichte
8.2.5 Ungerichtete Graphen und Bäume
8.2.6 Aufgaben: Einführung Testgraphen
8.3 Erzeugung von Testgraphen
8.3.1 Gleichverteilte Testgraphen
8.3.2 Fast immer endliche Verfahren
8.3.3 Sukzessiv erzeugte Adjazenzlisten
8.3.4 Prozeduren für die Erzeugung von Graphen
8.3.5 Aufgaben: Erzeugung von Graphen

Lösungen der Aufgaben

Literatur

Sachwortverzeichnis


Maintainer
stopp@imn.htwk-leipzig.de; 21. Feb 1999
zurück zur
Homepage