Volker Turau
Algorithmische
Graphentheorie

Druckfehlerverzeichnis

Diese Seite enthält eine Liste mit Fehlern, Druckfehlern und Unklarheiten, welche bisher in dem Buch Algorithmische Graphentheorie (2. 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:

  • Prof. Sigrid Knust
  • Jutta Müller

Errata

Letzte Änderung: 4. Dezember 2008

(siehe auch Errata für die dritte Auflage)

Die Fehlerliste ist in 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 oder deren Lösung
Leider haben sich in einigen Übungsaufgaben kleine Fehler eingeschlichen.
Tipp- und Formatierungsfehler
Die hier angegeben Fehler sind reine Druckfehler und sind sehr leicht zu verbessern.

Fehler

Seite	Position
---------------------------------------------------------------------------
 113   Seite 113 unten und Seite 114 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.
---------------------------------------------------------------------------

Unklarheiten

Seite	Position
---------------------------------------------------------------------------
  12	8-te Zeile

	LC(W) bezeichnet die Anzahl der Verweise, welche von Seite W
        ausgehen, d.h., Verweise die im Text von W enthalten sind
---------------------------------------------------------------------------
  36	2-te Zeile

	Nicht die Eingabe wird verdoppelt, sondern ihre Länge
---------------------------------------------------------------------------
  96    9-te Zeile von unten:
        Anstatt
	'Nach Aufruf von tiefensuche(i) werden alle von i aus erreichbaren ... '
	sollte es heißen:
	'Nach dem Aufruf der Tiefensuche für eine Ecke i werden alle
	von i aus erreichbaren ...'
---------------------------------------------------------------------------

Fehler in Funktionen oder Prozeduren

Seite	Prozedur oder Funktion

---------------------------------------------------------------------------
  98	6-te Zeile:
        Anstatt	TSNummer[i] = true sollte es Besucht[i] = true heißen
---------------------------------------------------------------------------
 102	Letzte if-Anweisung in Prozedur sZhKprozedur muss wie folgt ersetzt
        werden

	if TSNummer[i] = MinNummer[i] then
           while S.enthalten(i) = true do begin
              j = S.entfernen;
              MinNummer[j] = MinNummer[i];
           end
---------------------------------------------------------------------------
 148	17-te Zeile in Prozedur 5-färbung

	f[u] = f[i] oder f[u] = f[j] anstatt f[u] = f[i] oder f[u] = f[i]
---------------------------------------------------------------------------

Fehler in Übungsaufgaben oder deren Lösung

Seite	Aufgabe
---------------------------------------------------------------------------
 127	Aufgabe 17:
        In der Adjazenzliste für Ecke 1 fehlt Ecke 12
---------------------------------------------------------------------------
 347	Drittletzte Zeile der Lösung von Aufgabe 18

	der anstatt der der

---------------------------------------------------------------------------
 347	Vierte Zeile der Lösung von Aufgabe 23

	anstatt a_{ij} != 0 muss es a_{ji} != 0  heißen

---------------------------------------------------------------------------
 366    Die Nummering der Teilaufgaben der Lösung stimmt nicht mit der
        Nummering der Teilaufgaben in der Aufgabenstellung überein.

	Lösung von Teil b): Kritisch sind C_2 und C_n mit ungeradem n > 1.
        Lösung von Teil c): in Teil b)
        Lösung von Teil d): in Teil c)

---------------------------------------------------------------------------
 369    Lösung von Aufgabe 22.

        function chromatischeZahl(Graph : G) : Integer;
        var unten, oben, mitte : Integer;
        begin
            unten := 0; oben := n;
            while unten < oben do begin
                mitte := (oben + unten)/2;
                if färbung(G,mitte) then
                    oben := mitte
                else
                    unten := mitte + 1;
            end;
            chromatischeZahl = oben;
        end
---------------------------------------------------------------------------
 370	Achte Zeile der Lösung von Aufgabe 24

	anstatt 2 \sqrt{n} \le \chi(G)\chi(\overline{G}) muss es
        2 \sqrt{n} \le \chi(G) + \chi(\overline{G})  heißen

---------------------------------------------------------------------------
 402	Sechstletzte Zeile der Lösung von Aufgabe 10

	'for jeden Nachbar j von i do' anstatt 'for jeden Nachbar i von j do'

---------------------------------------------------------------------------
 402	Lösung von Aufgabe 11

	Die Variable L muss durch 'unbedeckt' ersetzt werden

---------------------------------------------------------------------------
 402	Lösung von Aufgabe 11, 16. Codezeile

	'if nachbar[j] = false begin' anstatt 'if nachbar[j] = true begin'

---------------------------------------------------------------------------
 411	Erste Zeile der Lösung von Aufgabe 33

	der anstatt der der

---------------------------------------------------------------------------
 412	Zeite Zeile der Lösung von Aufgabe 34

	der anstatt der der

---------------------------------------------------------------------------

Tipp- und Formatierungsfehler

Die folgende Liste enthält einfache Tipp- und Formatierungsfehler.
Seite	Position
---------------------------------------------------------------------------
  11	Abbildung 1.10

	Die Bezeichnungen der Web-Seiten A und B muss vertauscht werden
---------------------------------------------------------------------------
  12	7-te Zeile

	Der von anstatt Der von von
---------------------------------------------------------------------------
  43	13-te Zeile

	Eine Ecke anstatt Die Ecke
---------------------------------------------------------------------------
  62	12-te Zeile von unten

	in dem anstatt indem
---------------------------------------------------------------------------
  75	19-te Zeile

	ein Leitungsnetz anstatt das Leitungsnetz
---------------------------------------------------------------------------
  77	3-te Zeile

	ein minimal aufspannender Baum anstatt der gesuchte minimal
        aufspannende Baum
---------------------------------------------------------------------------
 102	1-te Zeile
        Anstatt TsNummer sollte es TSNummer heißen
	18-te Zeile
        Anstatt TsNummer sollte es TSNummer heißen
---------------------------------------------------------------------------
 118	10-te Zeile von unten

	Kanten eines kürzesten Weges anstatt Kanten des kürzesten Weges
---------------------------------------------------------------------------
 141	13-te Zeile

	knowledge anstatt kowledge
---------------------------------------------------------------------------
 152	7-te Zeile von unten

	sind das anstatt ist das
---------------------------------------------------------------------------
 238	Drittletzte Zeile von Aufgabe 28

	Die Abbildung findet man direkt im Anschluss an den Aufgabentext und
        nicht auf der nächsten Seite
---------------------------------------------------------------------------
 252	Letzte Zeile

	der Algorithmus ist optimal bezüglich der worst case Komplexität

---------------------------------------------------------------------------
 277	Erste Zeile

	In der bewerteten Adjazenzmatrix ist B[i,j] = \infty falls es
        keine Kante von i nach j gibt

---------------------------------------------------------------------------
 277	Vorletzte Zeile

	von G werden V[i,j] = i anstatt von G wird V[i,j] = i

---------------------------------------------------------------------------
 281	19-te Zeile

	werden die Vorgänger- und die Distanzmatrix anstatt wird die
        Vorgänger- und die Distanzmatrix

---------------------------------------------------------------------------
 294	Vorletzte Zeile

	polynomialem anstatt polynomialen

---------------------------------------------------------------------------
 295	2-te Zeile

	bedeutet anstatt bedeuted

---------------------------------------------------------------------------
 416	Referenz 26

	and anstatt und

---------------------------------------------------------------------------
 418	Referenz 66

	NP-completeness anstatt NP-completness

---------------------------------------------------------------------------