Grundlegende Algorithmen: Lösungshinweise

Kapitel 5

5.1
Starte an einem beliebigen Knoten und laufe entgegen der Kantenrichtung (dies ist nach Voraussetzung eindeutig). Entweder trifft man auf einen Knoten mit Eingangsgrad 0 oder man findet einen Zyklus (da der Graph endlich ist).
5.2
=>: Angenommen, |E|≠|V|-1. Betrachte unter allen solchen Graphen einen mit kleinster Knotenanzahl. Dann enthält G keinen Knoten mit Grad 1, denn dass Entfernen des Knotens samt seiner inzidenten Kante würde zu einem kleineren Graphen mit denselben Eigenschaften führen.
Ist |E|<|V|-1, dann kann G nicht zusammenhängend sein. Sei also |E|≥|V|. Nach Annahme hat jeder Knoten mindestens Grad 2. Starte an einem beliebigen Knoten und durchlaufen den Graphen. Sobald man einen Knoten zum zweiten Mal besucht, hat man einen Kreis gefunden (dies muss geschehen, da der Graph endlich ist und jeder Knoten mindestens Grad 2 hat). Dies ist ein Widerspruch zur Azyklität von G.

<=: Angenommen G sei zyklisch. Wähle unter allen solchen Graphen einen mit minimaler Knotenanzahl. Dann enthält G keinen Knoten mit Grad 1, denn dass Entfernen des Knotens samt seiner inzidenten Kante würde zu einem kleineren Graphen mit denselben Eigenschaften führen. Da die Summe der Knotengrade gleich der doppelten Kantenanzahl ist und jeder Knoten Grad mindestens 2 hat, gilt |E|≥|V|>|V|-1, was ein Widerspruch zur Voraussetzung ist.
5.3
Induktion über die Anzahl der Blätter.
5.4
Unterteile die Matrix in Blöcke der Größe k*k mit k=√log(n) Es gibt nur 2k*k=O(n) verschiedene k*k-Matrizen mit Einträgen aus {0,1}. Diese können vorab in Platz O(nlog(n)) gespeichert werden. Jeder echte Block der Adjazenzmatrix wird dann durch einen Verweis auf diese vorberechneten Blöcke repräsentiert und benötigt daher Platz n/k*n/k=O(n2/log(n))
5.5
Es müssen nur die im Text genannten Charakterisierungen der entsprachenden kanten berücksichtigt werden.
5.6
Eine Vorwärtskante würde man in einem ungerichteten Graphen zuerst andersherum als Rückwärtskante identifizieren.
Eine Querkante würde man in eineme ungerichteten Graphen zuerst andersherum als Baumkante indentifizieren.
5.7
In gerichteten Graphen entstehen Baumkanten, Querkanten und Rückwärtskanten.
Bei ungerichteten Graphen entstehen Baumkanten und Querkanten.
5.8
=>: In einen Eulerkreis wird jeder Knoten genau so oft verlassen, wie er besucht wurde. Somit muss der Knotengrad gerade sein.

<=: Starte an einem beliebigen Knoten v und durchlaufe den Graphen, solange es geht. Man kann zeigen, dass man wieder an v endet, da man jeden Knoten den man besucht wieder verlassen kann (da der Knotengrad gerade ist) außer bei v. Hat man einen Eulerkreis konstruiert, so ist man fertig. Sonst gibt es noch unbesuchte Kanten. Entferne den bisher gefundenen Kreis. Im neuen Graph hat jeder Knoten weiterhin geraden Grad. Starte an einem beliebigen Knoten und finden einen neuen Kreis. Zum Schluss muss aus der Menge der gefundenen Kreise ein neuer, einziger Kreis konstruiert werden (dies ist möglich, da G nach Voraussetzung zusammenhängend ist).
5.9
Die Wurzel des Baumes ist der erste Knoten in der Preorder. Wir finden jetzt die Teillisten für die Teilbäume, die an den Kindern der Wurzel gewurzelt sind. Der zweite Knoten der Preorder-Liste ist die Wurzel des ersten Teilbaumes. In der Postorder-Liste gehören alle Knoten vor diesem Knoten zum ersten Teilbaum. Der auf diese Menge von Knoten in der Preorder-Liste folgende Knoten ist die Wurzel des zweiten Teilbaumes usw. Die Teilbäume selbst werden dann aus den Bruchstücken der Preorder- und Postorder-Liste rekursiv konstruiert.
5.10
Verwende eine rekursive Tiefensuche; Sobald eine Rückkante gefunden wird, ist der Graph kein DAG.
Die topologische Sortierung erhält man, indem man einen globalen Zähler mit n=|V| initilisiert und nach dem Abschluss der rekursiven Tiefensuche an einem Knoten dort den Wert n vergibt und anschließend n um 1 dekrementiert.
5.11
Traversiere den Graphen und füge für jede Kante (u,v) die Kante (v,u) hinzu.
5.12
Sei T(i,j,k) die Anzahl Operationen, die benötigt werden, um Dki,j zu berechnen. Dabei sei T(i,j,0)=1. Dann gilt T(i,j,k)=3k (Beweis mittel Induktion). Also ist die Gesamtlaufzeit Θ(n23n).
5.13
G=({a,b,c}, {(a,b,2), (a,c,3), (c,b,-2)})
5.14
Sobald ein Wert Dki,i negativ wird, gibt es einen Kreis negativer Länge.
5.15
Beweis mit Induktion.
5.16
Wir nehmen hier schlingenfreie Graphen an, d.h. E(i,i)=0. Es gilt E-=E-sgn*(E*), wobei sgn* alle positiven Elemente auf 1 setzt und die Elemente der Hauptdiagonale auf 0 setzt.
5.17
Analog wie bei normalen Heaps.
5.18
Schlüssel und Name eines Elementes werden im Folgenden als identisch betrachtet: Zum Schluss hatt man einen Baum der aus einer linearen liste mit n Elementen besteht, wobei 4n-2 Operationen benötigt werden.
5.19
delete(k)={decrease_key(k,min-1); delete_min();}
5.20
Betrachte einen minimalen Spannbaum T. Enthält T die Kante e nicht, so ist nichts zu zeigen. Sei also e eine Kante von T, die die beiden Teilbäume T1 und T2 verbindet. Verfolge nun den Pfad, der durch den restlichen Kreis induziert wird, beginnend vom Endkonten von e, der in T1 liegt. Dieser Pfad enthält eine Kante e', die von T1 zu T3 geht. Da e' ebenfalls eine Kante des Kreises mit maximaler Kante e ist, ist das Gewicht von e' höchstens so groß wie von e und somit ist T1 und T3 verbunden mit e' ebenfalls ein minimaler Spannbaum.
5.21
In den U.S.A. ist er optimal, in Utopia nicht (betrachte den Wechel von beispielsweise 30 Einheiten). Wie wäre es bei den Nennwerten {1,5,25,100}?
5.22
Angenommen, ein minimaler Spannbaum enthält e. Nach dem Entfernen von e aus dem Spannbaum bleiben zwei Bäume übrig. Beim Durchlaufen der restlichen Kanten des gegebenen Kreises trifft man auf mindestens eine Kante e', die zwischen den beiden Bäumen verläuft. Nach Voraussetzung muss das Gewicht von e; gleich dem von e sein.
5.23
Ein Binomial-Baum k-ter Ordnung ist rekursiv wie folgt definiert. Ein Binomial-Baum 0-ter Ordnung besteht aus nur einem Knoten. Ein Binomial-Baum k-ter Ordnung entsteht aus zwei Binomial-Bäumen (k-1)-ter Ordnung, indem man die Wurzel des einem Baumes zum Kind des anderen Baumes macht.
Ein Binomial-Baum k-ter Ordnung besitzt offenichtlich 2k Knoten und hat eine Tiefe von k. Man kann weiter zeigen, dass man sich einen Binomial-Baum k-ter Ordnung auch als eine Wurzel vorstellen kann, an dem für jedes i∈[0:k-1] ein Binomial-Baum i-ter Ordung als Kind angehängt wird.
Sei k:=log(n/2). Man erzeugt zunächst mit Union-Operationen einen Binomial-Baum k-ter Ordnung (mit n/2 Knoten). Hängt man dieses Biniomial-Baum (mittels einer Union-Operation) an einen anderen Knoten als Kind an und führt ein Find (mit Pfadkompression) auf das tiefste Blatt in diesem Baum durch, so kann man zeigen, dass im Wesentlichen wieder ein Binomial-Baum gleicher Ordnung entsteht (an deren Wurzel nur ein weiterer Knoten hängt). Diese Find-Operation verursacht Kosten in Höhe von Ω(log(n)). Da nun noch n/2-1 Knoten übrig sind, kann man dies noch &Omega(n/2) mal wiederholen und erhält einen Gesamtaufwand von Ω(nlog(n)).