Volker Turau
Algorithmische
Graphentheorie

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 von
	topsort(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 nicht

		b := 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 Orginalausgabe
Seite	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