Aktion	Zweigstelle	Standorte	Status	Frist	Vorbestellungen
Vorbestellen	Zweigstelle: 07., Urban-Loritz-Pl. 2a	Standorte: NN.MG Büsi / College 6a - Naturwissenschaften	Status: Verfügbar	Frist:	Vorbestellungen: 0

„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