Graphen und Netzwerktheorie (eBook)

Prof. Dr.-Ing. André Krischke hält Vorlesungen zu Logistik und Prozessmanagement an der HS München, Dipl.-Math. techn. Helge Röpcke, ebenfalls HS München, hält Vorlesungen zu Diskreten Strukturen (Graphenoptimierung und kombinatorische Optimierung).

Vorwort 7
Inhaltsverzeichnis 9
I Grundlagen der Graphentheorie 15
1 Grundbegriffe der Graphentheorie 17
1.1 Grundbegriffe für Graphen 18
1.1.1 Definition eines Graphen 18
1.1.2 Grad eines Knotens 20
1.1.3 Wege und Kreise 23
1.2 Typen von Graphen 25
1.2.1 Vollständige Graphen 25
1.2.2 Bipartite Graphen 28
1.2.3 Gerichtete Graphen und Multigraphen 30
1.2.4 Bewertete Graphen 31
1.2.5 Bäume und Wälder 35
1.2.6 Gozinto-Graphen 38
2 Das Kürzeste-Wege-Problem in unbewerteten Graphen 41
2.1 Aufspannende Bäume 41
2.2 Breitensuche 43
2.3 Tiefensuche 46
2.4 Anwendungen in der Praxis 49
3 Das Kürzeste-Wege-Problem in bewerteten Graphen 54
3.1 Der Kürzeste-Wege-Baum und die kombinatorische Explosion 54
3.2 Der Algorithmus von Dijkstra 58
II Ausgewählte Probleme der Graphentheorie 66
4 Das Problem minimal aufspannender Bäume 68
4.1 Minimal aufspannender Baum 68
4.2 Algorithmus von Kruskal 70
4.3 Algorithmus von Prim 73
5 Matching-Probleme 76
5.1 Definition von Matchings 76
5.2 Matchings für bipartite Graphen 78
5.3 Maximal-Matching-Algorithmen 80
5.3.1 Greedy-Matching-Algorithmus 81
5.3.2 Verbessernde Wege 82
6 Das Problem des chinesischen Postboten 85
6.1 Euler-Kreise und Euler-Wege 85
6.2 Postbotenproblem 92
7 Das Problem des Handlungsreisenden 97
7.1 Hamilton-Kreise und Hamilton-Wege 97
7.1.1 Existenz von hamiltonschen Graphen 99
7.1.2 Problem des Handlungsreisenden 100
7.2 Heuristiken 102
7.3 Anwendungen in der Praxis 106
8 Färbungsprobleme 112
8.1 Planarität und Satz von Euler 112
8.2 Knotenfärbung 117
8.3 Kantenfärbung 122
8.4 Dualität zwischen Knoten- und Kantenfärbung 124
III Netzwerktheorien und -modelle 126
9 Netzwerktheorie – Bedeutung und neuere Erkenntnisse 128
9.1 Große Netzwerke in der Praxis 128
9.1.1 Interorganisations-Netzwerke 129
9.1.2 Beziehungs-, Freundschafts- und soziale Netzwerke 130
9.1.3 Informations-, Daten- und Wissensnetzwerke 131
9.1.4 Technologische Netzwerke 134
9.1.5 Biologische Netzwerke 136
9.2 Ausgewählte Erkenntnisse der Netzwerkforschung 137
9.2.1 Forschung im Bereich sozialer Netzwerke 138
9.2.2 Cluster als Kennzeichen sozialer Netzwerke 139
9.2.3 Kurze Wege als Kennzeichen sozialer Netzwerke 141
9.2.4 Skalen-Invarianz als Kennzeichen großer Netzwerke 142
9.2.5 Universalität als Kennzeichen großer Netzwerke 145
9.3 Weiterführende Literatur 147
10 Eigenschaften von Netzwerken 148
10.1 Charakterisierung von Netzwerken auf Knoten-Ebene 148
10.1.1 Unterscheidung von Hubs und Authorities 148
10.1.2 Lokaler Cluster-Koeffizient 149
10.1.3 Zentralitätsmaße eines Knotens 150
10.2 Charakterisierung von Netzwerken auf Teilgraphen-Ebene 152
10.2.1 Verfahren zum Auffinden zusammenhängender Komponenten 154
10.2.2 Algorithmen zum Auffinden von Communities 155
10.2.3 Klassifizierende Verfahren zum Auffinden von Communities 156
10.3 Charakterisierung von Netzwerken mit statistischen Größen 158
10.3.1 Mittlerer Knotengrad und durchschnittliche Netzwerkdichte 159
10.3.2 Häufigkeitsverteilung der Kontengrade 160
10.3.3 Der Durchmesser und die mittlere Pfadlänge des Netzwerks 162
10.3.4 Der globale Cluster-Koeffizient eines Netzwerks 163
10.4 Weiterführende Literatur 163
11 Entstehung von Netzwerken – Netzwerkmodelle 164
11.1 Erzeugung von Netzwerken mit Gleich- oder Binomialverteilung 165
11.1.1 Erzeugung von Gittergraphen mit deterministischen Regeln 165
11.1.2 Erzeugung eines Erdös-Renyi-Zufallsgraphen 167
11.1.3 Erzeugung des Watts-Strogatz-Modells – zwischen Kreis- und Zufallsgraph 172
11.2 Erzeugung von Netzwerken mit skalenfreier Verteilung 176
11.2.1 Erzeugung eines skalenfreien Netzwerks durch das Wachstumsmodell 176
11.2.2 Erzeugung eines skalenfreien Netzwerks mit dem Barabasi-Albert-Modell des „Preferential Attachment“ 177
11.2.3 Erweiterungen des Barabasi-Albert-Modells 180
11.3 Weiterführende Literatur 183
12 Dynamische Prozesse auf großen Netzwerken 184
12.1 Robustheit von Netzwerken 184
12.1.1 Relevanz und Erscheinungsformen 184
12.1.2 Wesentliche Modelle und Lösungsverfahren 187
12.1.3 Zusammenfassung wesentlicher Erkenntnisse 189
12.2 Epidemische Ausbreitung in Netzwerken 189
12.2.1 Relevanz und Erscheinungsformen 190
12.2.2 Wesentliche Modelle und Lösungsverfahren 192
12.2.3 Homogene Modelle zur Beschreibung der Ausbreitung 193
12.2.4 Netzwerkmodelle zur Beschreibung der Ausbreitung 195
12.2.5 Impfung in heterogenen Netzwerken 196
12.2.6 Zusammenfassung wesentlicher Erkenntnisse 199
12.3 Suche in Netzwerken 199
12.3.1 Relevanz und Erscheinungsformen 200
12.3.2 Wesentliche Modelle und Lösungsverfahren 200
12.3.3 Zusammenfassung wesentlicher Erkenntnisse 203
12.4 Transportprozesse in Netzwerken 203
12.4.1 Datenverkehr und Datenstau in Netzwerken 204
12.4.2 Kaskaden in Transportnetzwerken 207
12.4.3 Zusammenfassung wesentlicher Erkenntnisse 211
12.5 Kollektives Verhalten in Netzwerken 211
12.5.1 Meinungsbildung in Netzwerken – Das Voting-Modell 212
12.5.2 Informationskaskaden in Netzwerken 213
12.5.3 Spieltheorie in Netzwerken 215
12.5.4 Zusammenfassung wesentlicher Erkenntnisse 217
12.6 Dynamische Prozesse in Netzwerken – Forschungsbedarf 217
12.7 Weiterführende Literatur 218
13 Softwarebasierte Analyse und Modellierung großer Netzwerke 219
13.1 Die Modellbildung als Forschungsprozess 219
13.1.1 Formulierung der Forschungsfrage 220
13.1.2 Formulierung der Forschungshypothesen 220
13.1.3 Festlegung der Modellstruktur 221
13.1.4 Implementierung und Verifikation des Modells 222
13.1.5 Analyse und Validierung des Modells 223
13.1.6 Ergebnisdarstellung zur Entscheidungsunterstützung 223
13.2 Softwarebasierte Analyse und Visualisierung 224
13.2.1 Vorgehen bei der Datenbeschaffung und Datenimport 225
13.2.2 Softwarebasierte Erzeugung von Netzwerken 227
13.2.3 Grundlagen der Visualisierung und des Graphzeichnens 228
13.2.4 Softwarebasierte Analyse großer Netzwerke 230
13.3 Softwarebasierte Simulation dynamischer Prozesse in Netzwerken 233
13.3.1 Vergleich verschiedener Simulationsmodelle 233
13.3.2 Agentenbasierte Simulationsmodelle auf regulären Netzwerken 235
13.3.3 Simulation des Wachstums von Netzwerken 237
13.3.4 Simulation dynamischer Prozesse in Netzwerken 238
13.3.5 Simulation dynamischer Prozesse auf dynamischen Netzwerken 240
13.3.6 Generierung von Simulationsdaten und Durchsuchen des Lösungsraums 241
13.4 Schlussbetrachtung zur softwarebasierten Modellierung 242
13.5 Weiterführende Literatur 243
Literaturverzeichnis 244
Bildnachweise 249
Sachwortverzeichnis 250