Karlsruher Institut fur Technologie Prof. Dr. Peter SandersInstitut fur Theoretische Informatik Dennis Luxen, Dr. Johannes Singler

5. Ubungsblatt zu Algorithmen II im WS 2010/2011http://algo2.iti.kit.edu/AlgorithmenII.php

{luxen,sanders,singler}@kit.edu

Musterlosungen

Aufgabe 1 (Großter Kreis in einem konvexen Polygon)

Gegeben sei ein konvexes Polygon P ∈ R2. Das Problem ist einen großtmoglichen Kreis K ∈ R2 zufinden, der vollstandig in P enthalten ist.

Polygon P

K

a) Geben Sie ein lineares Programm zur Losung des Problems an.

b) Lasst sich das Problem auf hohere Dimensionen verallgemeinern?

Musterlosung:

a) Um das lineare Programm zur Losung unseres Problems zu bestimmen, mussen wir uns zunachstein paar Gedanken uber die geometrische Natur des Problems machen.

Sei also P ⊆ R2 das gegebene Polygon. Die Anzahl der Seiten des Polygons sei n. Nehmen wirzur Vereinfachung an, dass P keine vertikalen Seiten enthalt. Man kann sich leicht klarmachen,dass wir in diesem Falle durch eine Rotation des Achsenkreuzes (Koordinatentransformation)das Polygon so in eine Position drehen konnen, dass keine der Seiten mehr vertikal ist. Weil nendlich ist, ist dies immer moglich.

Weiterhin definieren wir die Seiten des Polygons durch n Geraden gi der Form

y = aix+ bi i = 1, . . . , n.

Da wir keine vertikalen Seiten zulassen, sei die Nummerierung der Geraden so, dass g1, . . . , gkdas Polygon von unten begrenzen, wahrend gk+1, . . . , gn das Polygon von oben begrenzen.

(s1, s2)

rg1gk

gk+1

gn

Damit nun der Kreis K mit Mittelpunkt s := (s1, s2) und Radius r komplett in P enthalten ist,mussen genau folgende Bedingungen erfullt sein:

1

• Der Punkt s hat mindestens den Abstand r von allen Geraden g1, . . . , gn,

• der Punkt s liegt oberhalb von g1, . . . , gk und

• der Punkt s liegt unterhalb von gk+1, . . . , gn.

Zur Berechnung des Abstandes des Punktes s von einer Geraden g, beziehen wir uns auf diefolgende Abbildung.

γ

γ

γ

(s1, s2)

g : y = ax+ b

d

(s1, as1 + b)

l

Die Steigung der Geraden g findet sich im Winkel γ wieder uber tan γ = a. Wegen der Ahnlichkeitder eingezeichneten Dreiecke gilt ebenfalls cos γ = d/l, und somit ist der gesuchte Abstand geraded = cos(γ)l. Mit γ = arctan(a) folgt insgesamt d = cos(arctan a)l. Die Lange der Strecke l istgerade die Differenz der y-Koordinaten des Kreismittelpunktes (s1, s2) und dem Wert as1 + b.Weiterhin ist aus der Analysis bekannt, dass gilt

cos(arctanx) =1√

x2 + 1,

wir erhalten in unserem Fall also insgesamt

d = cos(arctan a)l =s2 − as1 − b√

a2 + 1.

Fur den Fall, dass der Punkt (s1, s2) unterhalb der Geraden g liegt, gilt analog

d =as1 + b− s2√

a2 + 1.

Der Kreis K liegt also genau dann vollstandig in P wenn folgende Ungleichungen erfullt sind

s2 − ais1 − bi√a2i + 1

≥ r, i = 1, . . . , k

ais1 + bi − s2√a2i + 1

≥ r, i = k + 1, . . . , n.

Obwohl man etwas durch den Term√a2i + 1 abgeschreckt sein mag, da dieser doch vermeint-

lich die Linearitat der Bedingungen verletzt, stellt dies kein Problem dar, da die ai Teil der

Eingabe sind. Tatsachlich sind also die Terme√a2i + 1 Konstanten innerhalb unseres linearen

Programms.

Unser Ziel ist es den großten Kreis zu finden. Wir definieren uns also ein lineares Programm mitden Variablen r, s1 und s2 durch

maximiere r

2

unter den Nebenbedingungen

s2 − ais1 − bi√a2i + 1

≥ r, i = 1, . . . , k

ais1 + bi − s2√a2i + 1

≥ r, i = k + 1, . . . , n.

Eine Losung liefert uns demnach einen großtmoglichen Kreis mit Mittelpunkt (s1, s2) und Radiusr, der vollstandig in P enthalten ist.

b) Fur die Verallgemeinerung auf hohere Dimensionen lasst sich der gleiche Ansatz verwenden. Stattden Punkt-Gerade-Abstanden mussen lediglich Punkt-Hyperebenen-Abstande als Bedingungenberechnet werden. Diese sind ebenfalls als lineare Ungleichungen formulierbar.

Im Allgemeinen sei nun H eine Hyperebene fur alle x ∈ Rm mit (x− b) · a = 0, wobei a, b ∈ Rmund a 6= 0, dann ist der Abstand des Kreismittelpunktes s gegeben durch

d =|(s− b) · a|‖a‖2

.

Dabei ist der nicht-lineare Anteil ‖a‖2 durch die Eingabe bereits definiert – enthalt also insbe-sondere keine Variablen. Das Skalarprodukt im Zahler fuhrt analog zu Aufgabe (a) wieder zueiner linearen Form. Die Nebenbedingungen (Man muss hier noch darauf achten, dass der Kreis-mittelpunkt im inneren des Polytops liegt) sind also insgesamt linear, ein lineares Programmsfuhrt somit zu dem gewunschten Ergebnis.

Aufgabe 2 (Gleichverteiltes JA/NEIN )

Gegeben sei ein Algorithmus A, der mit Wahrscheinlichkeit p den Wert 1 ausgibt und mit (1− p) denWert 0.

a) Geben Sie einen Algorithmus A′ an, der A als Subroutine benutzt und gleichverteilt den Wert 0oder 1 ausgibt.

b) Analysieren Sie die erwartete Laufzeit Ihres Algorithmus in Abhangigkeit von p.

Musterlosung: Die notige Symmetrie der Wahrscheinlichkeit erhalt man durch Multiplikation:p(1− p) = (1− p)p. Diese Wahrscheinlichkeiten implizieren eine UND-Verknupfung zweier Elementa-rereignisse. Bei zweimaliger unabhangiger Ausfuhrung von Biased-Random bezeichne x den erstenRuckgabewert, y den zweiten. Dann gilt:

P ({x = 0, y = 1}) = (1− p)p und P ({x = 1, y = 0}) = p(1− p).

Ein Algorithmus, der jeweils mit Wahrscheinlichkeit 1/2 den Wert 0 oder 1 ausgibt, sieht also folgen-dermaßen aus:

Algorithmus 1 : Unbiased-Random

while x = y do1

x← Biased-Random2

y ← Biased-Random3

return x4

Die erwartete Laufzeit von Unbiased-Random in Abhangigkeit von p ist bestimmt durch die An-zahl der zu erwartenden Schleifendurchlaufe. Ein einzelner Schleifendurchlauf kann als Bernoulli-Experiment aufgefasst werden, bei dem mit Wahrscheinlichkeit 2p(1 − p) ein Erfolg (x 6= y) eintritt.

3

Die gesamte Schleife ist damit eine Aneinanderreihung unabhangiger Bernoulli-Experimente und damitdurch die Geometrische Verteilung gekennzeichnet. Das heißt, der Erwartungswert der ZufallsvariableX fur die Anzahl der Durchlaufe bis zum ersten Erfolg (inklusive) ist E(X) = 1/(2p(1−p)). Damit istdie erwartete Laufzeit von Unbiased-Random in Θ(1/(2p(1− p))), d. h. je ungleicher die Verteilungbei Biased-Random, umso langer dauert es.

Aufgabe 3 (Vergleich von Bitfolgen und Wortern)

Gegeben seien zwei Bitfolgen a1 · · · an und b1 · · · bn, die an verschiedenen geographischen Orten auf derErde gespeichert sind. Um auf Gleichheit zu testen, ließe sich die eine Bitfolge an den Ort der anderentransferieren und bitweise vergleichen. Die Kommunikationskosten sind jedoch sehr hoch und ein Bitzu ubertragen kostet Θ(1) Geldeinheiten und Ihr Budget ist sehr begrenzt. Folgender Algorithmuskonnte ihnen helfen:

1) Wahle Primzahl p gleichverteilt aus [2 : n2 log n2].

2) a =∑n

i=1 ai · 2i−1

3) b =∑n

i=1 bi · 2i−1

4) Falls a mod p ≡ b mod p, gebe ja zuruck, andernfalls nein

Zeigen Sie, dass die Kommunikationskosten in O(log n) liegen.

Musterlosung: Angenommen, die Bits a1 · · · an liegen an einem Ort A, und die Bits b1 · · · bn aneinem Ort B. Um nun zu uberprufen ob a1 · · · an = b1 · · · bn gilt, wahlt o. B. d. A. A die Primzahlp ∈ [2, n2 log n2]. Dann berechnen wir in A den Wert a mod p =: z und ubertragen das Tupel (z, p)zu B. Bei B wird nun b mod p =: z′ berechnet und uberpruft ob z = z′ gilt.Was die Anzahl ubertragener Bits betrifft, so gilt fur die Primzahl p dass p ≤ n2 log n2. Dafur sindlog(n2 log n2) Bits notwendig. Es gilt

log(n2 log n2) = 2 log(n log n2) = 2 log n+ 2 log log n2 ∈ O(log n).

Somit genugen fur p bereits O(log n) Bits. Da fur z wegen z = a mod p gilt dass z ≤ p, folgt somitdass fur z ebenfalls O(log n) Bits ausreichen.

Aufgabe 4 (Line-Shooting Problem)

(a) Ja-Instanz I = (P, 4).

l3l4

l1

l2

(b) Losung von I mit 4 Geraden.

Abbildung 1: Beispiel fur eine Instanz I = (P, k) des Line-Shooting Problems mit gegebener Punkte-menge P und k = 4. Eine zulassige Losung ist in Abbildung (b) dargestellt.

Gegeben sind n Punkte P ⊂ R2, n endlich in der Ebene mit pi := (xi, yi) fur alle pi ∈ P sowie eineZahl k ∈ N . Gefragt ist nun ob es eine Menge L von k Geraden gibt so, dass die Geraden lj ∈ L allePunkte pi ∈ P uberdecken. Dies bedeutet, dass fur jeden Punkt pi ∈ P eine Gerade lj ∈ L existiertso, dass pi ∈ lj . Eine Instanz des Line-Shooting Problems ist dann durch I := (P, k) gegeben.

4

a) Argumentieren Sie, warum bezuglich der Punktemenge P aus Abbildung 1a die Instanz I = (P, 3)eine Nein-Instanz des Problems ist.

b) Beweisen Sie, dass das Line-Shooting Problem FPT bezuglich k ist. Geben Sie dazu einen Al-gorithmus mit beschrankter Suchbaumtiefe an, der eine Instanz (P, k) exakt lost. Dabei solldie Suchbaumtiefe und der Verzweigungsgrad polynomiell in k, und der Aufwand pro Knotenpolynomiell in |P | =: n sein. Analysieren Sie die Laufzeit Ihres Algorithmus im O-Kalkul.

Hinweis: Verwalten Sie in jedem Baumknoten k Bins, die maximal zwei Punkte aufnehmenkonnen (und damit ggf. eine Gerade definieren). Ein Suchbaum der Hohe O(k) genugt.

Musterlosung:

a) Betrachten wir Abbildung 1b. Die drei Geraden l1, l3 und l4 decken jeweils 4 > 3 Punkte ab, da-mit mussen sie zwangsweise in einer Losung von I = (P, 3) enthalten sein. Ware beseispielsweisel1 nicht Teil der Losung, so brauchte man 4 Geraden, um die durch l1 uberdeckten Punkte ab-zudecken, was naturlich schon zu viel ware. Da wir nun wissen dass l1, l3 und l4 Teil der Losungsein mussen, bleibt uns keine Gerade mehr ubrig, um den rechtesten durch l2 uberdeckten Punktzu uberdecken. Das heißt, die Punktemenge P lasst sich nicht mit 3 Geraden uberdecken.

b) Die Idee fur einen exakten Such-Algorithmus mit beschrankter Suchbaumtiefe ist wie folgt. JederKnoten v in dem Suchbaum besteht aus k Bins die maximal zwei Punkte pi ∈ P aufnehmenkonnen. Wir nennen einen Bin b offen, wenn |b| < 2, ansonsten heißt b voll. Jeder volle Bindefiniert eindeutig eine Gerade l die durch dessen Punkte induziert wird. Dabei kann l durchausmehr als zwei Punkte in P uberdecken.

Der Suchbaum wird nun wie folgt konstruiert: Zunachst ordnen wir die Punktemenge P in einerbeliebigen Reihenfolge, das heißt es ist P = {p1, . . . , pn}. Dann wird die Wurzel des Baumesmit k leeren Bins initialisiert. Betrachten wir nun einen beliebigen Knoten v auf Level i desBaumes. Die zugehorigen Bins von v seien mit b1(v), . . . , bk(v) bezeichnet. Fur jeden offenen Binbj(v) erzeugen wir einen Nachfolgeknoten wj wie folgt. Die Bins von wj werden zunachst von vubernommen, das heißt es gilt bν(wj) := bν(v) fur alle 1 ≤ ν ≤ k. In den j-ten Bin von wj wirdallerdings noch der Punkt pi+1 hinzugefugt, also bj(wj) := bj(v) ∪ {pi+1}. In Worten heißt das,wir untersuchen alle Moglichkeiten den ”nachsten“ Punkt pi+1 auf die Bins zu verteilen (diessind maximal k Stuck, da es maximal k offene Bins geben kann). Damit ist der Verzweigungsgradfur jeden Knoten hochstens k – insbesondere also polynomiell in k.

Wird beim erzeugen eines Knotens im Baum ein Bin bj(v) voll, so werden alle durch die bj(v)induzierte Gerade l uberdeckten Punkte ”geloscht“ – das heißt diese werden nicht langer furdie Nachfolgeknoten in Betracht gezogen. Dafur ist die fur jeden vollen Bin uberdeckte Mengevon Punkten zu ermitteln. Dies geht in Zeit O(kn). Fur die Blatter des Baumes muss schließ-lich uberpruft werden, ob die durch die Bins induzierten Geraden alle (verbliebenen) Punkteuberdecken. Dies ist ebenfalls in O(kn) berechenbar. Die Hohe des Suchbaums ist hochstens2k, da wir k Bins der Große 2 haben, und fur jeden Nachfolgeknoten genau in einen der Binseinen Punkt hinzufugen. Da der Verzweigungsgrad des Baumes hochstens k ist, hat der Bauminsgesamt O(k2k) Knoten. Das heißt unser Algorithmus ist ein Algorithmus mit Suchbaumtiefepolynomiell in k, und die Gesamtlaufzeit betragt O(k2kkn) = O(k2k+1n).

Aufgabe 5 (Multiples Auswahlen)

Betrachten Sie den Algorithmus QuickSelect aus dem Buch von Mehlhorn und Sanders (Ab-schnitt 5.5, Pseudo-Code in Abbildung 5.9). Nehmen sich ruhig etwas Zeit, dieses Verfahren — dasim Mittel O (n) Zeit benotigt — gut zu verstehen.

a) Entwerfen Sie ein verallgemeinerte Version von QuickSelect, namlich QuickMultiSelect.Als Eingabe soll dieser neue Algorithmus eine Folge von Elementen s = 〈e1, . . . en〉 sowie eine

5

Menge von naturlichen Zahlen K = {k1, . . . , k`} akzeptieren, wobei k1, . . . , k` ≤ n gelten muss.Als Ergebnis soll nun eine Menge {(e′1, k1), . . . (e′`, k`)} mit e′1, . . . , e

′` ∈ s geliefert werden, so dass

e′i das ki-großte Element von s ist. Hinweis: Orientieren Sie sich zunachst eher an QuickSortals an QuickSelect und ubertragen Sie dann die Konzepte von QuickSelect auf QuickSort.

b) Gehen Sie nun davon aus, dass die folgenden (zugegebenermaßen stark vereinfachenden) Annah-men gelten:

• Die Lange n von s und die Kardinalitat ` von K sind jeweils Zweierpotenzen.

• Das”Pivotelement“ p liegt immer in der Mitte von s.

• In jedem Rekursionsschritt wird K”halbiert“.

Wenn Sie den Algorithmus ausreichend gut gestaltet haben, konnen Sie nun nachweisen, dass erunter den obigen Vorraussetzungen eine Laufzeit von O (n log `) hat. Fuhren Sie diesen Nachweis.

Musterlosung:

a) Das Ergebnis wird mittels rekursivem Aufrufen von QuickMultiSel rec durch die”Wrap-

per“-Function QuickMultiSelect geliefert. Letztere initialisiert den zusatzlichen”Offset“-

Parameter o von QuickMultiSel rec mit der 0.

1: function QuickMultiSelect(s : Sequence of Element, K : Set of N) : Set of (Element×N)2: assert 1 ≤ e ≤ |s| fur alle e ∈ k3: return QuickMultSel rec(s, K, 0)

Die rekursive Funktion QuickMultSel rec ahnelt sehr dem QuickSort Algorithmus ausdem Buch von Mehlhorn und Sanders (nachlesen!). Lediglich die Zeilen 8, 9 und 10 sind neuhinzugekommen. Die Zeilen 3 (Basisfall) und 11 (Rekursion) mussten aber angepasst werden.

1: function QuickMultSel rec(s : Sequence of Element, K : Set of N, o : N0) :Set of (Element × N)

2: assert o ≤ n− 13: if s = 〈〉 oder K = ∅ then return ∅4: Wahle gleichverteilt zufallig ein Element p ∈ s5: a := 〈e ∈ s : e < p〉6: b := 〈e ∈ s : e = p〉7: c := 〈e ∈ s : e > p〉8: Ka := {k ∈ K : k − o ≤ |a|}9: Kb := {k ∈ K : |a| < k − o ≤ |a|+ |b|}

10: Kc := {k ∈ K : |a|+ |b| < k − o}11: return QuickMultSel rec(a,Ka, o)∪({p}×Kb)∪QuickMultSel rec(c,Kc, o+|a|+|b|)

In den Zeilen 5, 6 und 7 wird die Sequenz s mit Hilfe des Pivotelementes p in drei Teilfolgena, b und c aufgeteilt. Dabei werden alle Elemente, die kleiner als p bzw. gleich p bzw. großerals p sind, in a bzw. b bzw. c eingefugt. In den Zeilen 8, 9 und 10 werden die Elemente von Kentsprechend den Teilfolgen a, b und c auf die Mengen Ka, Kb und Kc verteilt. Dabei gilt furein Element e ∈ a, welches in s das ki-großte Element ist, stets ki ∈ Ka. Analoges gilt auch furKb und Kc.

Fur die Elemente in a und b wird die Berechnung jeweils rekursiv fortgesetzt (Zeile 11). Fur dieElemente in b sind wir bereits fertig, da sie alle gleich p sind. Wir konnen also jeweils (p, k) furalle k ∈ Kb in die Ergebnismenge einfugen (Zeile 11).

Wozu wird nun der”Offset“-Parameter o benotigt? Bei dem zweiten der beiden rekursiven

Aufrufe in Zeile 11

QuickMultSel rec(c,Kc, o+ |a|+ |b|)

6

wird ja die Teilfolge c als Parameter ubergeben. Diese ist aber |a| + |b| Elemente kurzer alss. Dieser Wert musste aber eigentlich von allen Werten in Kc abgezogen werden, da sonst einfalsches Ergebnis zuruckgeliefert wurde. Auf der anderen Seite werden die Werte in Kc abernoch benotigt, da sie ja auch im Ergebnis vorkommen sollen. Aus diesem Grund wird Kc alsounverandert weitergereicht. Stattdessen wird aber |a| + |b| als

”Offset“ ubergeben um dann

beim Aufbau der Mengen Ka, Kb, Kc entsprechend verwendet zu werden (Zeilen 8 bis 10). Die

”Offsets“ aller vorherigen Rekursionsschritte sind dabei naturlich weiterhin notwendig. Es wird

also insgesamt o+|a|+|b| ubergeben, da samtliche”Offstes“ im Eingabeparamter o ja als Summe

enthalten sind.

b) Abgesehen von den rekursiven Aufrufen verursacht die Funktion QuickMultSel rec einenAufwand, der linear in n ist: Zum einen kann man die Teilfolgen a, b und c aufbauen indem mans von links nach rechts durchliest. Dies lasst sich ein Zeit von O (n) erledigen. Zum anderen mussauch die Menge K ebenfalls nur einmal durchgegangen werden (man verteilt dabei die Elementevon K auf Ka, Kb und Kc). Dies benotigt O (`) Zeit. Es gilt aber ` ≤ n (siehe unten).

Nun ist noch die Frage offen, wieviel Zeit das Einfugen von Elementen in Mengen (Zeilen 8bis 10) die Mengenvereinigung in Zeile 11 benotigt. All diese Operationen lassen sich aber inkonstanter Zeit ausfuhren. Z.B. implementiere man die Mengen als Doppelt verkettete Listen.

Zusatzlich zu dem Aufwand, der durch die Rekursion entsteht, haben wir also einen Zeitbedarfvon O (n). Nach Annahme (siehe Aufgabenstellung) gilt außerdem, dass n und ` in jedem Schritt

”halbiert“ werden. Der Zeitaufwand genugt also der Rekurrenzrelation

T (n, `) ≤ 2T

(n

2,`

2

)+ dn

fur eine Konstante d > 0. Um ein Gefuhl fur das Verhalten dieser Rekurrenz zu bekommen,falten wir diese ein Stuck weit aus:

T (n, `) ≤ 2T

(n

2,`

2

)+ dn

≤ 2

(2T

(n

4,`

4

)+ d

n

2

)+ dn

≤ 2

(2

(2T

(n

8,`

8

)+ d

n

4

)+ d

n

2

)+ dn

= 23 T

(n

23,`

23

)+ 22 d

n

22+ 2 d

n

2+ dn︸ ︷︷ ︸

3dn

Als Menge kann K aber keine Elemente mehrfach enthalten, und es ist ` = |K| und K ⊆{1, . . . , n}. Somit gilt ` ≤ n und wir erhalten durch vollstandiges Ausfalten

T (n, `) ≤ 2log2 ` T

(n

2log2 `,

`

2log2 `

)+ (log2 `)dn

= ` · T( n

2log2 `, 1)

︸ ︷︷ ︸O(1)

+ dn log2 `

= O (n log `) .

Aufgabe 6 (Sortierte Listen mit Rangoperation)

Sortierte Listen werden oft mittels balancierter Binarbaume implementiert, die bei n Elementen einemaximale Hohe von O (log n) garantieren. Damit kosten die Operationen insert, remove, update

und locate mit Hinweis nur O (log ∆) Zeit (es sei ∆ der Abstand vom Hinweis zur Fundstelle) undrangeSearch kostet O (log ∆ + L), wobei L die Große des Ergebnisses sein soll.

7

a) Wie ist die asymptotische Laufzeit, wenn man eine bereits sortierte Liste in einen leeren Rot-Schwarz-Baum geschickt einfugt?

Der Rang (engl. rank) eines Elements bezeichnet dessen Index in einer sortierten Folge. So genannteRank-Select-Dictionaries erlauben die effiziente Abfrage des Elements mit dem Rang k (select) undumgekehrt das Herausfinden des Rangs eines gesuchten Elements (rank). Dies kann erreicht werden,indem jeder Knoten des Rot-Schwarz-Baums speichert, wie viele Nachfahren er hat.

b) Skizzieren Sie die Algorithmen fur select und rank, sowie die Neuerungen bei insert.

c) Was bedeutet das fur die Laufzeiten der grundlegenden Operationen einer sortierten Liste, alsoinsert, remove, update, locate und rangeSearch?

Musterlosung:

a) Ab dem zweiten Element ubergibt man das vorangegangene als Hinweis. Dadurch ist immer∆ ≤ 1. Laufzeit einer Einfugeoperation ist damit O (1), also O (n) insgesamt.

b) select lauft analog zu binarer Suche ab, bei jeder Entscheidung werden die Anzahlen Nachfah-ren des rechten und des linken Kindknotens betrachtet. rank lauft gleich ab wie ein normaleslocate, nur dass es die Zahl der Nachfahren des linken Kindknotens auf einen Zahler r addiert,wenn beim Abstieg der rechte Weg genommen wird. r ergibt zum Schluss den Rang. insert mussdahingehend verandert werden, dass nach erfolgreichem Einfugen und Balancieren die Nachfah-renzahler aktualisiert werden mussen. Dazu muss der ganze Baum bis zu Wurzel nach obendurchlaufen werden.

c) Fur die nicht verandernden Operationen locate und rangeSearch andert sich nichts, sie konnenden zusatzlichen Eintrag einfach ignorieren. Fur alle Aufrufe von remove, update und insert

mussen die Nachfahrenzahler fur jeden Vorfahr im Baum geandert werden, also im schlimmstenFall O (log n) Stuck. Da sich die Halfte der Elemente in Blattern befindet, hilft hier amortisierteAnalyse in keinem Fall, die Laufzeit erhoht sich auf O (log n), unabhangig von ∆.

Aufgabe 7 (Starker Zusammenhang)

Finde sie im unten stehenden Graphen alle stark zusammenhangenden Komponenten. Benutzen Siedazu den DFS-basierten Algorithmus aus der Vorlesung, beginnen Sie bei H. In den mehrdeutigenFallen ist explizit angeschrieben, in welcher Reihenfolge die Kanten abgearbeitet werden sollen. In wel-chem Zustand befindet sich der Algorithmus, nachdem C zum zweiten Mal erreicht wurde (Markierungder Knoten, Inhalt der Stapel)?

Geben Sie ebenso den Endzustand des Graphen an.

8

Musterlosung: Zustand, nachdem C zum zweiten Mal erreicht wurde (und zwar uber eine Ruckwarts-kante):

Stapel: oReps: H, I, G, D, C; oNodes: H, I, G, D, E, C, B, A

9

Endzustand: Stapel: beide leer

Aufgabe 8 (Preflow-Push)

Bestimmen Sie den maximalen Fluss in dem unten angegebenen Netzwerk mit s = 1 und t = 6 (Kan-tenkapazitaten in Klammern). Benutzen Sie hierzu einen Preflow-Push Algorithmus aus der Vorlesung.Geben Sie samtliche Zwischenschritte an. Zeichnen Sie das aktuelle Netzwerk vor jeder (bis auf dieerste) Relabel-Operation und nachdem der Algorithmus terminiert. Siehe Kapitel 5 des Skripts.

1

2

3

4

5

6

(20)

(2)

(3)

(4)

(10)

(1)

(2)

(3)

(5)

Musterlosung: Die erste Darstellung zeigt das Netzwerk zu Beginn des Algorithmus

1

2

3

4

5

6

20(20)

3(3)

(2)

(1)

(10)

(4)

(2)

(3)

(5)

[6]

20

3

Wir fuhren jetzt die folgenden Operationen durch:

• Relabel(2). Dann ist dist(2) = 1.

• Push(2,3) mit ∆ = 2 und Push(2,4) mit ∆ = 1 und Push(2,5) mit ∆ = 10. Dann ist e(2) = 7,e(3) = 5, e(4) = 1,e(5) = 10

Der neue Zwischenstand:

10

1

2

3

4

5

6(2)

(3)

(5)

[6]3(3)

2(2)

1(1)

10(10)

(4)

5

1

10

[1] 7

20(20)

• Relabel(2). Da rf (2, 1) > 0 und dist(2) < dist(1) ist, folgt dist(2) := dist(1) + 1 := 7

• Push(2,1) mit ∆ = 7 Dann f(1, 2) = 13 und e(2) = 0

Jetzt haben wir den folgenden Zwischenstand im Netzwerk:

1

2

3

4

5

6(2)

(3)

(5)

[6]3(3)

2(2)

1(1)

10(10)

(4)

5

1

10

[7]

13(20)

Nun folgen diese Operationen

• Relabel(3). Da rf (3, 1) > 0 und dist(3) < dist(1) ist, folgt dist(3) := dist(1) + 1 := 7

• Push(3,1) mit ∆ = 3. Dann ist e(3) = 2

Der neue Zwischenstand:

1

2

3

4

5

6(2)

(3)

(5)

[6]

13(20)

2(2)

1(1)

10(10)

(4)

[7] 1

102 [7]

0(3)

• Relabel(3). Da rf (3, 2) > 0 und dist(3) < dist(2) ist, folgt dist(3) := dist(2) + 1 := 8

• Push(3,2) mit ∆ = 2. Dann e(2) = 2 und e(3) = 0

• Push(2,1) mit ∆ = 2. Dann e(2) = 0

Der neue Zwischenstand sieht so aus:

11

1

2

3

4

5

6(2)

(3)

(5)

[6]

1(1)

10(10)

(4)

[7]

11(20)

0(2)

0(3)

[8]

1

10

Weiter:

• Relabel(4), folgt dist(4) := 1. Push(4,6) mit ∆ = 1.Dann ist e(4) = 0 und e(6) = 1

Der neue Zwischenstand:

1

2

3

4

5

6(2)

(5)

[6]

1(1)

10(10)

(4)

[7]

11(20)

0(2)

0(3)

[8] 10

[1]

1

1(3)

• Relabel(5) folgt dist(5) := 1. Push(5,6) mit ∆ = 5.Dann e(5) = 5 und e(6) = 6

Der neue Zwischenstand:

1

2

3

4

5

6(2)[6]

1(1)

10(10)

(4)

[7]

11(20)

0(2)

0(3)

[8]

[1]

[1]

5(5)

6

5

1(3)

• Relabel(5),folgt dist(5) := dist(4) + 1 = 2. Push(5,4) mit ∆ = 2.Dann ist e(5) = 3 unde(4) = 2

• Push(4,6) mit ∆ = 2. Dann ist e(4) = 0 und e(6) = 8

Das Netwerk sieht dann so aus:

1

2

3

4

5

6[6]

1(1)

10(10)

(4)

[7]

11(20)

0(2)

0(3)

[8]

3(3)

2(2)

5(5)

[1]

[2]

8

3

12

Zum Schluss noch:

• Relabel(5). Da rf (5, 2) > 0 und dist(5) < dist(2) ist, folgt dist(5) := dist(2) + 1 := 8.

Push(5,2) mit ∆ = 3. Dann ist e(5) = 0 und e(2) = 3

• Push(2,1) mit ∆ = 3. Dann ist e(2) = 0

1

2

3

4

5

6[6]

1(1)

(4)

[7]

0(2)

0(3)

[8]

3(3)

2(2)

5(5)

[1]

87(10)

8(20)

[8]

Nun ist kein Knoten mehr aktiv, der Algorithmus terminiert. Und maximal Fluss ist 8.

Aufgabe 9 (Algorithmus fur Eulertouren)

Eine Euler-Tour ist ein Kreis, der jede Kante genau einmal beruhrt.

a) Zeigen Sie, dass ein ungerichteter Graph ohne isolierte Knoten keine Euler-Tour besitzt, wenner nicht zusammenhangend ist.

b) Zeigen Sie, dass ein ungerichteter Graph keine Euler-Tour besitzt, wenn einen Knoten mit un-geradem Grad gibt.

c) Zeigen Sie, dass jeder zusammenhangende Graph bei dem jeder Konten geraden Grad hat eineEuler-Tour besitzt. Hinweis: Entwerfen Sie einen Algorithmus, der eine Euler-Tour konstruiertund zeigen Sie, dass er unter den gegebenen Umstanden immer funktioniert. Eine Moglichkeitbesteht darin, sukkzessive Kreise zu bestimmen und aneinanderzuhangen.

d) Erklaren Sie, wie Ihr Algorithmus aus c) in Zeit O (m+ n) implementiert werden kann.

Musterlosung:

a) Seien A und B zwei Zusammenhangskomponeneten von G. Da G keine isolierten Knoten besitzt,befinden sich in beiden Komponenten Kanten. Angenommen es gabe eine Euler-Tour K. AlsEuler-Tour besucht besucht alle Kanten in A. Da es aber keine Kante zwischen A und B gibtkann K keine Kante von B besuchen. Das ist ein Widerspruch zur Annahme.

b) Angenommen es gabe eine Euler-Tour K = (v0, v1, . . . , vm−1, v0). Sei v ein Knoten mit un-geradem Grad. OBdA sei v 6= v0 (sonst konnen wir die Knoten auf dem Kreis entsprechendumnumerieren). Jedes Auftreten von v in K deckt genau zwei Kanten ab.1 Da keine Kante dop-pelt verwendet wird, deckt K also nur eine gerade Zahl von Kanten ab. Folglich konnen nichtalle Kanten von v in K verwendet werden. Widerspruch.

c) Sei G = (V,E) ein zusammenhangender Graph, dessen Knoten all geraden Grad haben. Imfolgenden wird gezeigt, wie eine Euler Tour konstruiert werden kann, die alle Kanten aus Genthalt. Die Konstruktion folgt dem Motto “konstruiere und erweitere einen Zyklus”.

1Hier schließen wir self-loops aus oder zahlen sie im Grad doppelt.

13

Das Vorgehen ist einfach erklart. Um nun einen Kreis C zu konstruieren, erzeugen wir einen PfadP mit einem beliebigen Startknoten v ∈ V , dessen inzidente Kanten noch nicht alle besucht sind.Der Pfad P wird so lange durch das hinzunehmen unbenutzter Kanten erweitert, bis wir wiederin v anklommen. Unbenutzt heißt hier, dass die Kante noch nicht in C oder P benutzt wird.Nun kann P dem Kreis C hinzugefugt werden.

Angenommen, dass bereits ein Zyklus C konstruiert wurde. Enthalt C alle Kanten aus G, dannsind wir fertig. Andernfalls gibt es einen Knoten v ∈ C derart, dass noch nicht alle zu v inzidentenKanten in C enthalten sind. Die Prozedur kann hier fortgesetzt werden. Ware dies nicht der Fall,ware G nicht zusammenhangend.

d) Die Laufzeit folgt aus der Uberlegung, dass jede Kante konstant oft “angeschaut” wird.

14