Druckfehlerverzeichnis
Diese Seite enthält eine Liste mit Fehlern, Druckfehlern und Unklarheiten, welche bisher in dem Buch Algorithmische Graphentheorie (1. Auflage) gefunden wurden und entsprechende Korrekturen.
An dieser Stelle möchte ich allen danken, welche mich auf
Tippfehler, Fehler oder Unklarheiten hingewiesen haben. Wenn
Sie einen Fehler finden, welcher noch nicht in dieser Liste
ist, so schicken Sie mir bitte eine e-mail an
turau at tuhh.de.
Vielen Dank!
volker turau
Mein besonderer Dank gilt den folgenden Personen:
- Wolfgang Litzenburger
- Elke Hocke
- Thomas Emden-Weinert
- Holger Dörnemann
- Philipp Flach
- Bernhard Schiefer
- Ralf Kastner
- Andreas Görz
- Felix Yu
Errata
Letzte Änderung: 26. Januar 2005
(siehe auch Errata für die zweite Auflage)
Die Fehlerliste ist in die folgenden Kategorien aufgeteilt:- Fehler
- Inhaltliche Fehler.
- Unklarheiten
- An einigen Stellen sind durch die Wahl von Formulierungen Unklarheiten aufgetreten.
- Fehler in Funktionen oder Prozeduren
- Leider haben sich in einigen Funktionen und Prozeduren kleine Fehler eingeschlichen.
- Fehler in Übungsaufgaben
- Leider haben sich in einigen Übungsaufgaben kleine Fehler eingeschlichen.
- Tipp- und Formatierungsfehler
- Die hier angegeben Fehler sind reine Druckfehler (sehr ärgerlich) und sind sehr leicht zu verbessern.
Fehler
Seite Position
---------------------------------------------------------------------------
112 Im Lemma Seite 112 oben muß der Satz
"Eine andere Ecke e ist genau dann eine trennende Ecke, falls ...
...
Vorgänger von e in B verbunden."
durch folgenden Satz ersetzt werden:
Eine andere Ecke e ist genau dann eine trennende Ecke, falls es einen
Nachfolger w von e gibt, so daß kein Nachfolger v von w durch eine
Rückwärtskante mit einem Vorgänger von e verbunden ist.
---------------------------------------------------------------------------
301 Der Beweis des Lemmas auf Seite 301 enthielt einen Fehler. Eine
geänderte und korrigierte Version ist als gezippte Postscript-Datei
verfügbar ( hier ).
---------------------------------------------------------------------------
213 Der zweite Teil des Beweis des Satzes von Menger (Seite 213 2. Absatz
ist falsch. Hier eine korrekte Version:
1. Zeige: Für jede Kante k aus (X, _quer) gilt:
k = (q, w') oder k = (w', w'')
(Die im Buch gemachte Aussage: aus e' in X folgt e'' in X ist nicht
haltbar.)
2. Setze T = { e | ist Endecke einer Kante in K_X }
Aus 1. folgt, dass alle Endecken verschieden sind (Striche beachten)
Somit ist |T| = |f|
Man beachte, dass T eineindeutig einer Menge von Ecken in G entspricht
(Striche beachten!).
3. T ist trennende Eckenmenge:
Ein Weg W von a nach b in G, induziert einen Weg W_N in N
(Man ersetzte jede Kante (x,y) aus W durch (x', x''),(x'', y') )
Nun muss W_N eine Kante aus (X, X_quer) verwenden. Nach 2. verwendet
also W eine Ecke von T.
4. Weiter wie im Buch
---------------------------------------------------------------------------
Unklarheiten
Seite Position --------------------------------------------------------------------------- 19 Zweiter Absatz, dritte Zeile Anstelle von Grad 1 oder 2 muß Grad 1, 2 oder 3 stehen --------------------------------------------------------------------------- 287 Dritter Absatz, vierte Zeile Anstelle von so beläßt man die Kante in G. steht besser so fügt man die Kante in G ein. --------------------------------------------------------------------------- 314 2. Zeile im Lemma anstelle von maximal muß minimal stehen --------------------------------------------------------------------------- 316 vorletzter Abschnitt Teil a) anstelle von maximal muß minimal stehen ---------------------------------------------------------------------------
Fehler in Funktionen oder Prozeduren
Seite Prozedur oder Funktion --------------------------------------------------------------------------- 95 topsort In der vorletzten Zeilen mußtsprozedur(i)anstelle vontopsort(i)stehen --------------------------------------------------------------------------- 188 erweitererückwärts Der Typ der Variablen W mußwarteschlange of Integer sein --------------------------------------------------------------------------- 245 verkürze In der dritten Zeile muß D[i] anstelle von D[i,j] stehen --------------------------------------------------------------------------- 263 iterativer-A* Die 18. Zeile lautet nichtb := f(j) + D[S.tiefe]; sondern b := f(j) + D[S.tiefe] + kosten(i,j);---------------------------------------------------------------------------
Fehler in Übungsaufgaben
Seite Aufgabe --------------------------------------------------------------------------- 126 14 Die Aussage gilt nur falls dii ungleich 0 ist. Ist dii=0, so bildet i eine starke Zusammenhangskomponente. --------------------------------------------------------------------------- 194 2 Im Hinweis zur Aufgabe muß in der letzten Zeile der Exponent von Lambda i+1 und nicht i sein. --------------------------------------------------------------------------- 197 9 Die Bewertung der rechten vertikalen Kante fehlt. Ihr Wert ist für die Bestimmung eines blockierenden Flusses ohne Bedeutung. Allerdings hängt der Wert W des maximalen Flusses von dieser Bewertung b ab: W = min(10,4+b). --------------------------------------------------------------------------- 236 23 Der letzte Satz muß lauten: Genau dann ist Zk(G) mindestens 2, wenn in G' jede Ecke von der Startecke aus erreichbar ist. ---------------------------------------------------------------------------
Tipp- und Formatierungsfehler
Die folgende Liste enthält einfache Tipp- und Formatierungsfehler.Seite Position --------------------------------------------------------------------------- vii Letzter Absatz turau@informatik.fh-wiesbaden.de --------------------------------------------------------------------------- vii Vorletzte Zeile Wiesbaden, im Februar 1996 --------------------------------------------------------------------------- 23 9. Zeile von unten A[N[i+1]-1] --------------------------------------------------------------------------- 41 8. Zeile N[n+1] = m + 1 --------------------------------------------------------------------------- 125 1. Zeile Sind e,f Ecken eines ungerichteten Graphen --------------------------------------------------------------------------- 125 8. Zeile Ist (e,f) eine Kante eines gerichteten Graphen --------------------------------------------------------------------------- 133 Bildunterschrift zu Abbildung 5.3 Ein bipartiter Graph --------------------------------------------------------------------------- 137 3. Zeile objektorientierten --------------------------------------------------------------------------- 210 Abbildung 7.7 Die Bezeichnungen der Ecken s und q sind vertauscht --------------------------------------------------------------------------- 216 2. Absatz, 4. Zeile von oben Es muß z >= Ze(G) anstelle von z <= Ze(G) heißen --------------------------------------------------------------------------- 231 8. Zeile von unten Es muß (log n)½ anstelle von log n heißen --------------------------------------------------------------------------- 253 Abbildung 8.8 In der 3. Zeile und Spalte 3 muß anstelle von 7 eine 11 stehen --------------------------------------------------------------------------- 258 vorletzte Zeile anstelle von f((e muß f(e stehen --------------------------------------------------------------------------- 265 letzte Zeile Abschnitt 8.4 --------------------------------------------------------------------------- 271 Abbildung 8.18 Im Text zur Abbildung muß es heißen: ... Graphen aus Abbildung 8.15 --------------------------------------------------------------------------- 277 erste Zeile anstelle von kantenbwerteten muß kantenbewerteten stehen --------------------------------------------------------------------------- 281 sechste Zeile anstelle von sin muß sind stehen --------------------------------------------------------------------------- 288 dritte Zeile probabilistische --------------------------------------------------------------------------- 292 vorletzte Zeile Anstelle von n.; d.h. muß n. D.h. stehen --------------------------------------------------------------------------- 302 dritte Zeile des Beweises P = NP --------------------------------------------------------------------------- 305 Bildunterschrift für Abbildung 9.11 Eine Anwendung von 3-clique-färbung auf den Graphen aus Abbildung 9.10 --------------------------------------------------------------------------- 311 erste Zeile Elemente --------------------------------------------------------------------------- 312 3. Zeile vor Satz. Abbildung 9.15 --------------------------------------------------------------------------- 316 vorletzte Zeile anstelle von Schritt c) kann muß Die Schritte d) und e) können stehen --------------------------------------------------------------------------- 317 Erste Zeile, anstatt Abbildung 9.14 muss Abbildung 9.15 stehen --------------------------------------------------------------------------- 319 5. Zeile, letztes Wort ist --------------------------------------------------------------------------- 319 7. Zeile, letztes Wort Ressourcen --------------------------------------------------------------------------- 319 letzte Zeile im ersten Absatz Am Ende fehlt ein Punkt --------------------------------------------------------------------------- 319 2. Absatz, zweitletzte Zeile durchgeführt --------------------------------------------------------------------------- 331 1. und 6. Zeile Diamant --------------------------------------------------------------------------- 336 Referenzen [19] und [20] Die e-mail Adresse lautet: ftp-request@theory.stanford.edu --------------------------------------------------------------------------- 339 Referenz [63] Die Seitenzahl lautet 1098 - 1101 --------------------------------------------------------------------------- Buchrückseite 2. Zeile Es fehlt: und Beziehungen ---------------------------------------------------------------------------
Erweiterungen
Erweiterungen gegenüber der OrginalausgabeSeite Position --------------------------------------------------------------------------- 204 Bestimmung einer maximalen Zuordnung in bipartiten Graphen Verbesserung der Laufzeit: O(z½m), wobei z die Anzahl der Kanten in einer maximalen Zuordnung ist. --------------------------------------------------------------------------- 258 A*-Algorithmus Ausführliche Darstellung des A*-Algorithmus --------------------------------------------------------------------------- Viele neue Übungsaufgaben ---------------------------------------------------------------------------
Letzte Änderung: 26. Januar 2005