Das Buch erscheint in der Reihe "Quantitative Methoden" und gibt einen Überblick über ein wichtiges
Teilgebiet der diskreten Mathematik, nämlich die Graphen- und Netzwerktheorie, die in den
Wirtschaftswissenschaften eine wesentliche Rolle spielt. Die beschriebenen Verfahren kommen in der Praxis auf vielfältige Weise vor, beispielsweise in jeder Art von Netzwerken, wenn es darum geht, kürzeste Wege zu berechnen, also Kosten zu sparen.
Das Buch gibt hier einen Überblick über die gängigen Verfahren und bietet zahlreiche Beispiele aus der betriebswirtschaftlichen Praxis. Es wird auch gezeigt, welche der Verfahren mit entsprechender Simulationssoftware gelöst werden können. So sind die Studierenden später in der Lage, eine Praxissituation einschätzen zu können und ein geeignetes Instrument zur Lösung zu finden.
/ AUS DEM INHALT: / / /
I Grundlagen der Graphentheorie 13
1 Grundbegriffe der Graphentheorie 15
1.1 Grundbegriffe für Graphen 16
1.1.1 Definition eines Graphen 16
1.1.2 Grad eines Knotens 18
1.1.3 Wege und Kreise 21
1.2 Typen von Graphen 23
1.2.1 Vollständige Graphen 23
1.2.2 Bipartite Graphen 26
1.2.3 Gerichtete Graphen und Multigraphen 28
1.2.4 Bewertete Graphen 29
1.2.5 Bäume und Wälder 33
1.2.6 Gozinto-Graphen 36
2 Das Kürzeste-Wege-Problem in unbewerteten Graphen 39
2.1 Aufspannende Bäume 39
2.2 Breitensuche 41
2.3 Tiefensuche 44
2.4 Anwendungen in der Praxis 47
3 Das Kürzeste-Wege-Problem in bewerteten Graphen 52
3.1 Der Kürzeste-Wege-Baum und die kombinatorische Explosion 52
3.2 Der Algorithmus von Dijkstra 56
II Ausgewählte Probleme der Graphentheorie 64
4 Das Problem minimal aufspannender Bäume 66
4.1 Minimal aufspannender Baum 66
4.2 Algorithmus von Kruskal 68
4.3 Algorithmus von Prim 71
5 Matching-Probleme 74
5.1 Definition von Matchings 74
5.2 Matchings für bipartite Graphen 76
5.3 Maximal-Matching-Algorithmen 78
5.3.1 Greedy-Matching-Algorithmus 79
5.3.2 Verbessernde Wege 80
6 Das Problem des chinesischen Postboten 83
6.1 Euler-Kreise und Euler-Wege 83
6.2 Postbotenproblem 90
7 Das Problem des Handlungsreisenden 95
7.1 Hamilton-Kreise und Hamilton-Wege 95
7.1.1 Existenz von hamiltonschen Graphen 97
7.1.2 Problem des Handlungsreisenden 98
7.2 Heuristiken 100
7.3 Anwendungen in der Praxis 104
8 Färbungsprobleme 110
8.1 Planarität und Satz von Euler 110
8.2 Knotenfärbung 115
8.3 Kantenfärbung 120
8.4 Dualität zwischen Knoten- und Kantenfärbung 122
III Netzwerktheorien und-modelte 124
9 Netzwerktheorie - Bedeutung und neuere Erkenntnisse 126
9.1 Große Netzwerke in der Praxis 126
9.1.1 Interorganisations-Netzwerke 127
9.1.2 Beziehungs-, Freundschafts- und soziale Netzwerke 128
9.1.3 Informations-, Daten- und Wissensnetzwerke 129
9.1.4 Technologische Netzwerke 132
9.1.5 Biologische Netzwerke 134
9.2 Ausgewählte Erkenntnisse der Netzwerkforschung 135
9.2.1 Forschung im Bereich sozialer Netzwerke 136
9.2.2 Cluster als Kennzeichen sozialer Netzwerke 137
9.2.3 Kurze Wege als Kennzeichen sozialer Netzwerke 139
9.2.4 Skalen-Invarianz als Kennzeichen großer Netzwerke 140
9.2.5 Universalität als Kennzeichen großer Netzwerke 143
9.3 Weiterführende Literatur 145
10 Eigenschaften von Netzwerken 146
10.1 Charakterisierung von Netzwerken auf Knoten-Ebene 146
10.1.1 Unterscheidung von Hubs und Authorities 146
10.1.2 Lokaler Cluster-Koeffizient 147
10.1.3 Zentralitätsmaße eines Knotens 148
10.2 Charakterisierung von Netzwerken auf Teilgraphen-Ebene 150
10.2.1 Verfahren zum Auffinden zusammenhängender Komponenten 152
10.2.2 Algorithmen zum Auffinden von Communities 153
10.2.3 Klassifizierende Verfahren zum Auffinden von Communities 154
10.3 Charakterisierung von Netzwerken mit statistischen Größen 156
10.3.1 Mittlerer Knotengrad und durchschnittliche Netzwerkdichte 157
10.3.2 Häufigkeitsverteilung der Kontengrade 158
10.3.3 Der Durchmesser und die mittlere Pfadlänge des Netzwerks 160
10.3.4 Der globale Cluster-Koeffizient eines Netzwerks 161
10.4 Weiterführende Literatur 161
11 Entstehung von Netzwerken - Netzwerkmodelle 162
11.1 Erzeugung von Netzwerken mit Gleich- oder Binomialverteilung 163
11.1.1 Erzeugung von Gittergraphen mit deterministischen Regeln 163
11.1.2 Erzeugung eines Erdös-Renyi-Zufallsgraphen 165
11.1.3 Erzeugung des Watts-Strogatz-Modells - zwischen Kreis- und Zufallsgraph 170
11.2 Erzeugung von Netzwerken mit skalenfreier Verteilung 174
11.2.1 Erzeugung eines skalenfreien Netzwerks durch das Wachstumsmodell.. 174
11.2.2 Erzeugung eines skalenfreien Netzwerks mit dem Barabasi-Albert-Modell des "Preferential Attachment" 175
11.2.3 Erweiterungen des Barabasi-Albert-Modells 178
11.3 Weiterfuhrende Literatur 181
12 Dynamische Prozesse auf großen Netzwerken 182
12.1 Robustheit von Netzwerken 182
12.1.1 Relevanz und Erscheinungsformen 182
12.1.2 Wesentliche Modelle und Lösungsverfahren 185
12.1.3 Zusammenfassung wesentlicher Erkenntnisse 187
12.2 Epidemische Ausbreitung in Netzwerken 187
12.2.1 Relevanz und Erscheinungsformen 188
12.2.2 Wesentliche Modelle und Lösungsverfahren 190
12.2.3 Homogene Modelle zur Beschreibung der Ausbreitimg 191
12.2.4 Netzwerkmodelle zur Beschreibung der Ausbreitung 193
12.2.5 Impfung in heterogenen Netzwerken 194
12.2.6 Zusammenfassung wesentlicher Erkenntnisse 197
12.3 Suche in Netzwerken 197
12.3.1 Relevanz und Erscheinungsformen 198
12.3.2 Wesentliche Modelle und Lösungsverfahren 198
12.3.3 Zusammenfassung wesenüicher Erkenntnisse 201
12.4 Transportprozesse in Netzwerken 201
12.4.1 Datenverkehr und Datenstau in Netzwerken 202
12.4.2 Kaskaden in Transportnetzwerken 205
12.4.3 Zusammenfassung wesentlicher Erkenntnisse 209
12.5 Kollektives Verhalten in Netzwerken 209
12.5.1 Meinungsbildung in Netzwerken - Das Voting-Modell 210
12.5.2 Informationskaskaden in Netzwerken 211
12.5.3 Spieltheorie in Netzwerken 213
12.5.4 Zusammenfassung wesenüicher Erkenntnisse 215
12.6 Dynamische Prozesse in Netzwerken - Forschungsbedarf 215
12.7 Weiterführende Literatur! 216
13 Softwarebasierte Analyse und Modellierung großer Netzwerke .217
13.1 Die Modellbildung als Forschungsprozess 217
13.1.1 Formulierung der Forschungsfrage 218
13.1.2 Formulierung der Forschungshypothesen 218
13.1.3 Festlegung der Modellstruktur 219
13.1.4 Implementierung und Verifikation des Modells 220
13.1.5 Analyse und Validierung des Modells 221
13.1.6 Ergebnisdarstellung zur Entscheidungsunterstützung 221
13.2 Softwarebasierte Analyse und Visualisierung 222
13.2.1 Vorgehen bei der Datenbeschaffung und Datenimport 223
13.2.2 Softwarebasierte Erzeugung von Netzwerken 225
13.2.3 Grundlagen der Visualisierung und des Graphzeichnens 226
13.2.4 Softwarebasierte Analyse großer Netzwerke 228
13.3 Softwarebasierte Simulation dynamischer Prozesse in Netzwerken 231
13.3.1 Vergleich verschiedener Simulationsmodelle 231
13.3.2 Agentenbasierte Simulationsmodelle auf regulären Netzwerken 233
13.3.3 Simulation des Wachstums von Netzwerken 235
13.3.4 Simulation dynamischer Prozesse in Netzwerken 236
13.3.5 Simulation dynamischer Prozesse auf dynamischen Netzwerken 238
13.3.6 Generierung von Simulationsdaten und Durchsuchen des Lösungsraums 239
13.4 Schlussbetrachtung zur softwarebasierten Modellierung 240
13.5 Weiterführende Literatur 241
Literaturverzeichnis 242
Bildnachweise 247
Sachwortverzeichnis 248