---
tags: Assignments
---

# Blatt 09

|Kurs |Semester |Team |
|--- |--- |--- |
|Algorithmen und Datenstrukturen |SS 2020 |Carlo Mohl & Noah Nuebling |

---

## Aufgabe 1

### 1)
Wahr.

Argument ist das Kreise bei nur positiven Kantenkosten, nur mehr Kosten bringen, da sie zwei schon erreichte Knoten verbinden. Das bedeutet das in den Teilgraphen nie Kreise seien werden, damit sind die Teilgraphen Kreisfrei und zusammenhängend und somit Bäume.

### 2)
Falsch.

Gegenbeispiel:

### 3)
Wahrscheinlich wahr.
Argument: ich kann von jedem Knoten eine BFS starten u. somit könnte ich immer jede Kante in einem MST haben.

Bei der BFS entsteht immer ein Spannbaum. Wenn wir die BFS an einem Indizenten Knoten von e beginnen können wir immer einen Spanning Tree konstruieren, der e enthält.

### 4)
Falsch, Gegenbeispiel:
Graph G (V,E)
V:={(a,b,c)} E:={(a,b,10),(a,c,1),(b,c,1)}
MST wäre die Kantenmenge :={(a,c,1),(b,c,1)}
wähle als Kante e die Kante:={(a,b,10)}, für diese Kante existiert in G kein MST.


### 5)
Wahr, Beweis, siehe minimal Spanning Tree wikipedia unter dem Punkt "Uniqueness"

https://en.wikipedia.org/wiki/Minimum_spanning_tree

1. Wir nehmen an, es gibt zwei MSTs X und Y auf dem Graphen G.l

## Aufgabe 2

### a)
Graph G (V,E)
V:={(a,b,c,d)} E:={(a,b,2),(b,c,3),(a,d,1)}
Schnitt V\S:={a} und S:={b,c,d}
Menge M:={(b,c,3)}
Schnittkante die nicht leicht ist aber zu dem MST gehört:={(a,b,2)}

Genügt den Anforderungen, da die gestellten Bedingungen erfüllt wurden ?

### b)
Graph G (V,E)
V:={(a,b,c,d,z)} E:={(a,b,1),(b,c,1),(c,d,1),(b,z,20),(c,z,10), (d,z,1)}
wobei a der Startknoten und z der Zielknoten des Dijstraalgorithmes sind.
der Dijkstra-Suchbaum der auch minmaler Spanngraph ist hat die Kanten: {(a,b,1),(b,c,1),(c,d,1),(d,z,1)}. verändert man die Kosten der Kante (b,z,20) zu (b,z,1) so ist der Dijkstra-Suchbaum nicht mehr minmaler Spanngraph von G, da eine Kante nicht besucht werden würde.

Genügt den Anforderungen, da die gestellten Bedingungen erfüllt wurden ?

### c)
Graph G (V,E)
V:={(a,b,c,d,e,f)} E:={(a,b,1),(a,c,1),(b,c,1),(c,d,10),(d,e,1), (d,f,1),(e,f,1)}
kein Baum, da Kreise enthalten, die Kante (c,d,10) muss im MST sein, da sie die einzige Verbindung der Knotenmengen {(a,b,c)} und {(d,e,f)} ist.

Genügt den Anforderungen, da die gestellten Bedingungen erfüllt wurden ?

### d)
Graph G (V,E)
V:={(a,b,c,d)} E:={(a,b),(a,c),(a,d)}
Alle Kanten sind Schnittkanten wenn der Schnitt so verläuft:
Schnitt V\S:={a} und S:={b,c,d}

Genügt den Anforderungen, da die gestellten Bedingungen erfüllt wurden ?

### e)
Graph G (V,E)
V:={(a,b,c,d,e,f,g)} E:={(a,d),(b,d),(c,d),(d,e),(e,f),(e,g),(f,g)}
Schnitt V\S:={d,e,f,g} und S:={a,c,d}
Schnitt mit 3 Schnittkanten und Graph welcher zusammenhängend und kein Baum ist da nicht Kreisfrei. Schnittkanten sind alle Teil des MST, da sie die einzigen Verbindungen zu den jeweiligen Knoten sind.

Genügt den Anforderungen, da die gestellten Bedingungen erfüllt wurden ?

## Aufgabe 3

### a)
Vorraussetzung: die Kantenmenge M darf keine Kreise enthalten.

Abänderung von Kruskal: da Kruskal am Anfang des Durchlaufs alle Kanten nach Gewicht aufsteigend sortiert und somit bestimmt welche Kanten er zuerst in den MST nimmt, einfach die Kanten aus M an den Anfang der sortierten Kantenliste kopieren und aus der original Sortierung löschen und den Algorithmus laufen lassen.

Bei Prim ändern wir:

if w in PQ and d[w] > c(e) then 
d[w] <- c(e)

zu

if (w in PQ and d[w] > c(e)) or (e in M) then 
d[w] <- 0

### b)

Kosten:

makeArray: O(n)
union: O(n)
findSet: O(1)

Gesamtlaufzeit:
O(n log n)

## Aufgabe 4

### a)
Inital Conditions:
Matchings:
(A,V)
(D,C)
(F,E)
Runde 1:
Augmented Path:
(Z,C)

Matchings:
(A,V)
(C,Z)
(D,C)
(F,E)

Runde 2:
Augmented Path:
(S,D,C,F,E,B)

Matchings:
(A,V)
(B,E)
(C,Z)
(D,S)
(F,K)

Runde 3:
Augmented Path:
(C,A,V,D,S

Matchings:
(A,V)
(C,Z)
(D,C)
(E,Z)