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.
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.
---------------------------------------------------------------------------
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 ...'
---------------------------------------------------------------------------
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]
---------------------------------------------------------------------------
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
---------------------------------------------------------------------------
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
---------------------------------------------------------------------------
