b f c e d a g

1. Übungsblatt
Kombinatorische Optimierung
WS 2016/17
Jens M. Schmidt
Aufgabe 1: Optimalitätsbedingungen
Beweisen Sie die Äquivalenz folgender Aussagen für einen Spannbaum T eines zusammenhängenden Graphens G = (V, E).
i) T ist ein minimaler Spannbaum.
ii) (Kreisbedingung) Für jede Kante vw ∈ E − E(T ) gilt, dass alle Kanten des
v-w-Pfades in T höchstens das Gewicht c(vw) haben.
iii) (Schnittbedingung) Für jede Kante e ∈ T und Knotenmenge S einer Zusammenhangskomponente von T − e ist e minimal in δ(S).
Aufgabe 2: Kruskal und Prim
a
4
7
d
b
9
15
10
f
12
e
c
5
6
11
13
8
g
i) Führen Sie den Algorithmus von Kruskal an obigem Graphen aus.
ii) Führen Sie den Algorithmus von Prim an obigem Graphen aus, beginnend mit
dem Knoten a.
iii) Eine Kontraktion einer Kante e = vw löscht e und identifiziert die Knoten
v und w; hierbei können neue Mehrfachkanten auftreten. Rekapitulieren Sie
die aus Graphen und Algorithmen bekannte Inzidenzlisten-Repräsentation von
Graphen und überlegen Sie sich, in jeweils welcher Laufzeit1 Kanten gelöscht,
eingefügt und kontrahiert werden können.
1
Genauer benutzen wir hierbei die Anzahl Rechenschritte auf der sogenannten unit-cost RAM. Diese
erlaubt folgende grundlegende Funktionen auf Registern und Hauptspeicher in jeweils einem Rechenschritt
(daher der Name unit-cost): Eingabe-Ausgabe-Operationen, Speicher-Register Transfers, indirektes Addressieren, Verzweigungen, fundamentale arithmetische Operationen und Vergleiche. Ebenso wird als Eingabelänge nicht die Bitlänge der Eingabe, sondern die Anzahl der Zahlen in der Eingabe gemessen (also
Eingabelänge n + m für Graphen). Wir machen zudem die Annahme, dass die Bitlänge aller Operanden
der Anweisungen polynomiell in der Eingabebitlänge sind, da die unit-cost RAM andernfalls nicht mehr
polynomiell äquivalent zu anderen grundlegenden Maschinenmodellen ist.
iv) Erklären Sie in so viel Detail wie nötig, welche Schritte des Algorithmus von
Prim wieviel Laufzeit benötigen (bei Inzidenzlisten-Repräsentation der Eingabe). Für welche Schritte ist es sinnvoll, eine weiterführende Datenstruktur (wie
z.B. Fibonacci-Heaps) zu benutzen?
Aufgabe 3: Starke Austauscheigenschaft
Seien E und F die Kantenmengen zweier Spannbäume eines Graphen G. Beweisen
Sie, dass für jede Kante e ∈ E − F eine Kante f ∈ F − E existiert, so dass sowohl
E + f − e als auch F + e − f Spannbäume von G sind.
Aufgabe 4: Vizemeister
Ein zweitbester MST ist ein Spannbaum mit minimalem Gewicht, das größer als das
Gewicht eines MST ist.
i) Geben Sie möglichst große Graphklassen an, für deren Graphen kein zweitbester
MST existiert. Bonusaufgabe: Sind das die einzigen?
ii) Durch minimal wie viele Kantenvertauschungen unterscheidet sich ein gegebener MST T von einem (beliebigen) zweitbesten MST?
iii) Finden Sie einen Algorithmus mit Laufzeit O(mn) oder besser, der einen zweitbesten MST effizient berechnet.

Download Report