Anwendungen der Graphentheorie

Vorderdeckel......Page 1
Titel Seite......Page 3
Copyright Seite......Page 4
VORWORT......Page 5
Inhalt......Page 7
0. Einleitung......Page 9
1.1. Grundbegriffe......Page 13
1.2. Eigenschaften von Strömen und Spannungen......Page 30
1.3.1. Problemstellung......Page 37
1.3.2. Der Satz von Ford und Fulkerson......Page 39
1.3.3. Verallgemeinerter Satz von Ford und Fulkerson......Page 44
1.3.4. Das Multiterminal-Problem......Page 53
1.4.1. Der Existenzsatz für eine Spannung......Page 58
1.4.2. Die Probleme des kürzesten und des längsten Weges als Potentialprobleme......Page 59
1.4.3. Algorithmus zur Bestimmung einer kürzesten Bahn......Page 61
1.5. Die Idee der Netzplantechnik......Page 65
1.6. Literatur......Page 71
2.1. Problemstellung......Page 72
2.2. Die Lösung nach Busacker und Gowen......Page 73
2.3. Die Lösung nach Klein......Page 75
2.4. Minimalitätsbeweis......Page 80
2.5. Schlußbemerkungen......Page 82
2.6. Literatur......Page 83
3.2. Die Standardmethode......Page 84
3.3. Der verbesserte Matrix-Algorithmus......Page 89
3.4. Der Kaskadealgorithmus......Page 91
3.5. Literatur......Page 99
4.2. Ein konvexes Transportproblem......Page 100
4.3. Ein Multistromproblem......Page 110
4.4. Literatur......Page 123
5.1. Problemstellung......Page 124
5.2. Netze ohne Steinerpunkte......Page 128
5.3. Netze mit Steinerpunkten......Page 134
5.4. Einfluß der Kostenfunktion auf die Optimalnetzstruktur......Page 142
5.5. Literatur......Page 145
6.1.1. Problemstellung......Page 146
6.1.2. Ein Lösungsalgorithmus für das Zuordnungsproblem......Page 147
6.2.1. Problemstellung......Page 154
6.2.2. Ein branch-and-bound-Lösungsalgorithmus für das Rundreiseproblem......Page 155
6.2.3. Ein heuristisches Verfahren zur Lösung des Rundreiseproblems......Page 161
6.3. Schlußbemerkungen......Page 164
6.4. Literatur......Page 165
7.1. Problemstellung......Page 167
7.2. Algorithmus zur Erzeugung eines zyklenfreien Fragebogens......Page 171
7.3. Optimale Fragebogen......Page 173
7.4. Ein Beispiel aus der Codierung......Page 178
7.5. Literatur......Page 180
8.1. Problemstellung......Page 181
8.2. Der Algorithmus von Mason zur Lösung linearer Gleichungssysteme......Page 184
8.3. Literatur......Page 189
9.1. Problemstellung......Page 191
9.2. Der Algorithmus von Lempel und Cederbaum......Page 192
9.3. Die Idee von Younger......Page 195
9.4. Literatur......Page 208
10.2. Sätze von Kuratowski, MacLane und Whitney......Page 209
10.3. Der Planaritätsalgorithmus von Dambitis......Page 213
10.4. Planaritätsuntersuchungen mittels Zerlegung von Graphen......Page 224
10.5. Der Einbettungsalgorithmus von Demoucron, Malgrange und Pertuiset......Page 229
10.6. Der Planaritätsalgorithmus von Tutte......Page 231
10.7. Literatur......Page 234
Namen- und Sachverzeichnis......Page 237