Anwendungen der Graphentheorie

Inhaltsverzeichnis0. Einleitung.1. Ströme und Spannungen auf Netzwerken.1.1. Grundbegriffe.1.2. Eigenschaften von Strömen und Spannungen.1.3. Das Problem des Maximalstromes.1.4. Das Problem der Maximalspannung.1.5. Die Idee der Netzplantechnik.1.6. Literatur.2. Das lineare Transportproblem.2.1. Problemstellung.2.2. Die Lösung nach Busacker und Gowen.2.3. Die Lösung nach Klein.2.4. Minimalitätsbeweis.2.5. Schlußbemerkungen.2.6. Literatur.3. Der Kaskadealgorithmus.3.1. Problemstellung.3.2. Die Standardmethode.3.3. Der verbesserte Matrix-Algorithmus.3.4. Der Kaskade algorithmus.3.5. Literatur.4. Nichtlineare Transportprobleme.4.1. Problemstellung.4.2. Ein konvexes Transportproblem.4.3. Ein Multistromproblem.4.4. Literatur.5. Kommunikations- und Versorgungsnetze.5.1. Problemstellung.5.2. Netze ohne Steinerpunkte.5.3. Netze mit Steinerpunkten.5.4. Einfluß der Kostenfunktion auf die Optimalnetzstruktur.5.5. Literatur.6. Das Zuordnungs- und das Rundreiseproblem.6.1. Das Zuordnungsproblem.6.2. Das Rundreiseproblem.6.3. Sehluübemerkungen.6.4. Literatur.7. Codierungs- und Entseheidungsgraphen.7.1. Problemstellung.7.2. Algorithmus zur Erzeugung eines zyklenfreien Fragebogens.7.3. Optimale Fragebogen.7.4. Ein Beispiel aus der Codierung.7.5. Literatur.8. Signalflußgraphen.8.1. Problemstellung.8.2. Der Algorithmus von Mason zur Lösung linearer Gleichungssysteme.8.3. Literatur.9. Minimale Mengen von Rückkehrbögen.9.1. Problemstellung.9.2. Der Algorithmus von Lempel und Cedebbaum.9.3. Die Idee von Younger.9.4. Literatur.10. Einbettung planarer Graphen in die Ebene.10.1. Problemstellung.10.2. Sätze von Kuratowski, MacLane und Whitney.10.3. Der Planaritätsalgorithmus von Dambitis.10.4. Planaritätsuntersuchungen mittels Zerlegung von Graphen.10.5. Der Einbettungsalgorithmus von Demoucron, Malgrange und Pertuiset.10.6. Der Planaritätsalgorithmus von Tutte.10.7. Literatur.Namen- und Sachverzeichnis.