Author(s): Walther H., Naegler G.
Publisher: FBV
Year: 1987
Language: German
Pages: 192
Vorderdeckel......Page 1
Mathematik für Ingenieure......Page 2
Titel Seite......Page 3
Copyright Seite......Page 4
Inhaltsverzeichnis......Page 7
0. Einleitung......Page 9
1.1. Was ist ein Graph?......Page 12
1.2. Beschreibung und Speicherung von Graphen......Page 14
1.3. Algorithmus und Programm......Page 19
1.4. Einfache Organisationsalgorithmen......Page 23
1.5. Abschätzungen des Aufwandes von Algorithmen......Page 30
2.1. Einführung......Page 36
2.2.1. Problemstellung......Page 37
2.2.2. Tremaux-Algorithmus......Page 38
2.2.3. Das Prinzip Depth-First- Search(DFS)......Page 39
2.2.4. Das Prinzip Breadth-First- Search (BFS)......Page 41
2.3.1. Beispiele......Page 42
2.3.2. Ordnungen in Wurzelbäumen......Page 43
2.4. Zusammenhang......Page 47
2.5. Starker Zusammenhang......Page 50
2.6. Kreisfreiheit......Page 53
2.7.1. Beispiele......Page 55
2.7.2. Nichtnegative Bogenlängen......Page 57
2.7.3. Beliebige reelle Bogenlängen......Page 59
2.7.4. Kaskadealgorithmus und Floyd-Algorithmus......Page 62
2.8.1. Beispiele......Page 66
2.8.3. Algorithmus zur Radius- und Zentrumsermittlung......Page 67
2.8.4. Zentrumsmengen......Page 69
2.9.1. Beispiele......Page 71
2.9.2. Längste Wege und Kreisfreiheit......Page 74
2.9.3. Graphen ohne Kreise......Page 76
2.9.4. Graphen mit Kreisen......Page 77
2.10.1. Aufgabenstellung......Page 79
2.10.3. Greedyalgorithmen......Page 80
2.10.4. Ein Algorithmus vom Aufwand $O(m n)$......Page 82
2.10.5. Ein Algorithmus vom Aufwand $O(m \cdot \log n)$......Page 84
2.11.1. Aufgabenstellung......Page 86
2.11.2. Eigenschaften von Minimalnetzen......Page 87
2.11.3. Konstruktion eines Minimalnetzes......Page 89
2.11.4. Algorithmus zur Ermittlung eines Steiner-Netzes......Page 93
2.11.5. Kostenabhängigkeit......Page 94
3.1. Beispiele und Definitionen......Page 96
3.2.1. Aufgabenstellung......Page 98
3.2.2. Mathematische Sätze......Page 99
3.2.3. Methoden zur Lösung der Gleichungssysteme......Page 102
3.2.4. Eine mathematische Perle......Page 104
3.3.1. Problemformulierung......Page 108
3.3.2. Eine Ersatzaufgabe......Page 111
3.3.3. Verbalalgorithmus zur Lösung des Maximalstromproblems MAX 2 und PASCAL-procedure......Page 112
3.4.1. Problemstellung und Beispiele......Page 115
3.4.3. Die Idee des out-of-kilter- Algorithmus......Page 120
3.4.4. Verbalalgorithmus und PASCAL-procedure TRANSPORT......Page 126
3.5.1. Aufgabenstellung......Page 129
3.5.2. Der Satz von König......Page 130
3.5.4. Ein Beispiel......Page 131
3.5.5. PASCAL-procedure ZUORDNUNG......Page 133
3.6.1. Aufgabenstellung......Page 134
3.6.2. Ein Verfahren, basierend auf dem Prinzip branch-and-bound......Page 135
3.6.4. Näherungsverfahren zur Lösung des Rundreiseproblems und PASCAL-procedures......Page 137
4.1.1. Beispiele und Probleme......Page 146
4.1.2. Verbalalgorithmus zur Ermittlung innerlich stabiler Mengen und PASCAL-procedure......Page 148
4.2.2. Definitionen und Sätze......Page 152
4.2.3. Verbalalgorithmen zur zulässigen Färbung eines Graphen......Page 154
4.2.4. PASCAL-procedure zur Minimalgradfolge und zulässiger Färbung......Page 156
4.2.5. Exakter Algorithmus zur Bestimmung der chromatischen Zahl und PASCAL-procedure......Page 157
4.2.6. Prozedur zur Ermittlung der chromatischen Zahl......Page 162
4.3.1. Beispiele und Aufgabenstellung......Page 164
4.3.2. Definitionen, Verbalalgorithmus und PASCAL- procedure......Page 166
4.4.1. Aufgabenstellung......Page 169
4.4.2. Erforderliche Sätze......Page 170
4.4.3. Verbalalgorithmus......Page 171
4.4.4. PASCAL-procedure zur Näherung an eine Maximumpaarung......Page 172
4.5.1. Problemstellung......Page 174
4.5.2.1. Der Satz von Kuratowski......Page 175
4.5.2.2. Der Satz von McLane......Page 176
4.5.2.3. Der Satz von Whitney......Page 178
4.5.3. Planaritätsalgorithmen......Page 179
4.6. Bemerkungen zur Auswertung von Rechenbeispielen......Page 183
Literatur- und Quellenver-jzeichnis......Page 188
Sach Wortverzeichnis......Page 190
