--- tags: Assignments --- # Blatt 10 |Kurs |Semester |Team | |--- |--- |--- | |Algorithmen und Datenstrukturen |SS 2020 |Carlo Mohl & Noah Nuebling | --- ## Aufgabe 1 ### a) #### 1. ``` L = Menge aller simplen Pfade p auf G (also ein Tupel aus Kanten) f : L -> R = Länge(p) (also die Anzahl der Kanten in L) |L| in O((|V|)!) (Wobei (|V|)! die Anzahl der Permutationen aller Knoten in G sind) ``` #### 2. ``` L = Menge L aller Knotenteilmengen M f : L -> R = |M| (also die Anzahl der Knoten in M) |L| in O(2^|V|) (Wobei 2^|V| die Kardinalität der Potenzmenge auf V ist) ``` #### 3. ``` L = Menge L aller Knotenteilmengen M f : L -> R = |M| (also die Anzahl der Knoten in M) |L| in O(2^|V|) (Wobei 2^|V| die Kardinalität der Potenzmenge auf V ist) ``` ### b) Der Algorithmus ist rekursiv und besitzt 2Parameter: Eine Menge an "relevanten" Kanten aus dem Graphen und ein Kostenakkumulator. In der obersten Rekursion sind alle Kanten aus dem Graphen relevant und der Kostenakkumulationsparameter hat den Wert 0. In jeder Rekursion wird über alle noch relevanten Kanten iteriert. Für jede dieser Kanten e rufen wir die Funktion nun erneut auf. Beim neuen Funktionsaufruf ist die Menge der "relevanten" Kanten um die Reduziert die adjazent zu e sind. Die Kante e selber nehmen wir auch raus. Zum bisherigen Wert des Kostenakkumulators addieren wir beim neuen Aufruf das Gewicht der Kante e. Nachdem wir über die relevanten Kanten iteriert haben returnen wir das Minimum der returns der Unteraufrufe. Wenn es keine relevanten Kanten für einen Aufruf gibt, dann returnen wir direkt der Wert des Kostenakkumulators. Da wir mit jeder tieferen Rekursionsstufe mindestens eine Kante rausnehmen, ist der Algorithmus in `O von (|E|)!` ## Aufgabe 2 ## Aufgabe 3 ### a) ### b) ## Aufgabe 4 ### a) ### b)