Wiederholungsfragen a) Erläutere die Vorgehensweise des

Wiederholungsfragen
a) Erläutere die Vorgehensweise des Algorithmus von Prim und des Algorithmus von
Kruskal.
b) Welche Laufzeit hat der Algorithmus von Kruskal?
c) Erläutere wie man die Laufzeit von O(m log n) beim Algorithmus von Kruskal erreicht.
d) Wie funktioniert der Algorithmus von Dijkstra? Laufzeit?
e) Wie funktioniert der Algorithmus von Moore, Bellman und Ford? Laufzeit?
f) Erkläre mit eigenen Worten die Nebenbedingungen des Max-Flow-Problems.
g) Wodurch erhält man eine obere Schranke für den Wert eines maximalen Flusses von
s nach t?
h) Erläutere mit eigenen Worten die wichtigsten Schritte im Beweis zur Korrektheit
des Ford-Fulkerson-Algorithmus. Gehe insbesondere darauf ein, wie der minimale
s-t-Schnitt gefunden werden kann.
i) Was ist ein entscheidener Nachteil des Ford-Fulkerson-Algorithmus?
j) Wodurch wird die Größe eines maximalen Matchings in bipartiten Graphen beschränkt?
k) Wodurch wird die Größe eines maximalen Matchings in allgemeinen Graphen beschränkt?
l) Erläutere mit eigenen Worten die Tutte-Berge-Formel.
m) Beschreibe die grundlegende Idee des Algorithmus zur Bestimmug eines perfekten
Matchings in allgemeinen Graphen. Gehe insbesondere auf die drei verschiedenen
Fälle ein, die im Algorithmus unterschieden werden.
n) Warum kann der Algorithmus für maximales Matching in bipartiten Graphen nicht
auf allgemeine Graphen übertragen werden?

Download Report