X
  GO
Ihre Mediensuche
Suche
Zweigstelle
Medienart


9 von 52
Graphen- und Netzwerkoptimierung
VerfasserIn: Büsing, Christina
Verfasserangabe: Christina Büsing
Jahr: 2010
Verlag: Heidelberg, Spektrum, Akad. Verl.
Mediengruppe: Buch
verfügbar (wo?)verfügbar (wo?)
Exemplare
 ZweigstelleStandorteStatusFristVorbestellungen
 Vorbestellen Zweigstelle: 07., Urban-Loritz-Pl. 2a Standorte: NN.MG Büsi / College 6a - Naturwissenschaften Status: Verfügbar Frist: Vorbestellungen: 0
Inhalt
„Alle Wege führen nach Rom!" Aber welcher ist der beste – wie findet mein Navi den Weg überhaupt? Und was ist mit einer Rundreise durch Europas Hauptstädte? Diese Fragen bilden nur einen kleinen Teilaspekt der Themen dieses Buches. Anhand vieler Praxissituationen werden die Begriffe der Graphentheorie und Netzwerkoptimierung eingeführt und die aufgeworfenen Probleme anschließend mit Hilfe von Algorithmen gelöst. Das Buch richtet sich an Studierende der Mathematik und Informatik in den ersten Semestern sowie an interessierte Praktiker. Es enthält eine Vielzahl an Anwendungsbeispielen sowie wichtige in der Praxis relevanten Algorithmen mit dem Beweis ihrer Optimalität. Spezielle mathematische Vorkenntnisse sind nicht erforderlich: Sämtliche Begriffe und Methoden werden auf verständliche Weise eingeführt. Das so erworbene Wissen kann anhand zahlreicher Übungsaufgaben und deren Lösungen vertieft und überprüft werden.
 
 
 
 
 
 
/ AUS DEM INHALT: / / /
 
 
1 Erste Orientierung in der Graphentheorie 1
 
1.1 Erster Schultag 1
 
1.2 Zusammenhang und Schnitte 10
 
1.3 Bäume 14
 
1.4 Aufgaben 17
 
 
 
2 Tiefen- und Breitensuche 21
 
2.1 Spannende Bäume 21
 
2.2 Wie findet man spannende Bäume? 24
 
2.3 Anwendungen von BFS und DFS 29
 
2.4 Aufgaben 33
 
 
 
3 Das Minimal-Spannende-Baum-Problem 39
 
3.1 Das Problem und zwei Algorithmen 39
 
3.2 Zwei Optimalitätskriterien 43
 
3.3 Aufgaben 51
 
 
 
4 Euler-Touren und -Wege 57
 
4.1 Das Königsberger Brückenproblem 57
 
4.2 Die Algorithmen von Hierholzer und Fleury 61
 
4.3 Euler-Wege oder das Haus vom Nikolaus 65
 
4.4 Aufgaben 68
 
 
 
5 Noch zwei Rundreise-Probleme 71
 
5.1 Hamilton und das Icosian-Spiel 71
 
5.2 Das Travelling-Salesman-Problem 78
 
5.3 Komplexitätstheorie 84
 
5.4 Aufgaben 86
 
 
 
6 Planarität 91
 
6.1 Gas-Wasser-Strom und Planarität 91
 
6.2 Outerplanare Graphen 95
 
6.3 Die Euler-Formel 98
 
6.4 Die Graphen ^3,3, K5 und Kuratowski 104
 
6.5 Aufgaben 108
 
 
 
7 Knotenfärbung 111
 
7.1 Die chromatische Zahl 111
 
7.2 Das Vier-Farben-Problem 115
 
7.3 Aufgaben 121
 
 
 
8 Gerichtete Graphen und Turniergraphen 125
 
8.1 Gerichtete Graphen - Digraphen 125
 
8.2 Starker Zusammenhang 128
 
8.3 Gerichtete Euler-Graphen 132
 
8.4 Hamilton-Wege in Turniergraphen 134
 
8.5 Könige in Turniergraphen 136
 
8.6 Aufgaben 141
 
9 Kürzeste Wege 145
 
 
 
9.1 Der Kürzeste-Wege-Baum 145
 
9.2 Ein Optimalitätskriterium und der Dijkstra-Algorithmus 149
 
9.3 Negative Kosten 155
 
9.4 Aufgaben 158
 
 
 
10 Maximale Flüsse 163
 
10.1 Flüsse und der Dekompositionssatz von Ford-Fulkerson 163
 
10.2 Das maximale Fluss-Problem 169
 
10.3 Der Max-Fluss-Min-Schnitt-Satz 176
 
10.4 Aufgaben 181
 
 
 
11 Kostenminimale Flüsse 187
 
11.1 Problemstellung 187
 
11.2 Ein Optimalitätskriterium 190
 
11.3 Zwei Algorithmen 193
 
11.4 Aufgaben 199
 
 
 
12 Maximale Matchings 203
 
12.1 Definition und ein Optimalitätskriterium 203
 
12.2 Matchings in bipartiten Graphen 207
 
12.3 Aufgaben 218
 
 
 
13 Lösungshinweise 223
 
 
 
A Satz, Beweis, Definition 247
 
A.l Folgerungen und Äquivalenzen 248
 
A.2 Negationen 249
 
A.3 Beweis durch Widerspruch 250
 
A.4 Vollständige Induktion 251
 
A.5 Ringschluss 253
 
 
 
B Zeichen und Symbole 257
 
B.l Aus der Mengentheorie 257
 
B.2 Aus der Arithmetik 258
 
B.3 Zwei Quantoren 259
 
 
 
Literaturverzeichnis 261
 
Index 263
 
Details
VerfasserIn: Büsing, Christina
VerfasserInnenangabe: Christina Büsing
Jahr: 2010
Verlag: Heidelberg, Spektrum, Akad. Verl.
Systematik: NN.MG
ISBN: 978-3-8274-2422-8
2. ISBN: 3-8274-2422-4
Beschreibung: XII, 265 S. : zahlr. graph. Darst.
Mediengruppe: Buch