# Algorithmen und Datenstrukturen: Blatt 12

## Aufgabe 1

Die lila markierten Kanten beschreiben den Kürzesten-Wege-Baum.

## Aufgabe 2


### 2a)

| Schritt | Menge der grauen Knoten | schwarz |
| ------- | ------------------------------------------------- | ------- |
| 1 | {(g,-,0)} | |
| 2 | {(g,-,0),(f,g,1)} | |
| 3 | {(g,-,0),(f,g,1),(d,f,2)} | |
| 4 | {(g,-,0),(f,g,1),(d,f,2),(c,d,2)} | |
| 5 | {(g,-,0),(f,g,1),(c,d,2),(a,c,1)} | d |
| 6 | {(g,-,0),(f,g,1),(c,d,2),(a,c,1),(j,g,2)} | |
| 7 | {(g,-,0),(f,g,1),(c,d,2),(a,c,1),(j,g,2),(b,c,3)} | |
| 8 | {(g,-,0),(f,g,1),(a,c,1),(b,c,3),(i,j,2)} | c,j |
| 9 | {(g,-,0),(f,g,1),(a,c,1),(h,i,2)*} | b,h,i |
| 10 | {(e,g,5)*} | a,f,e,g |

*wird am Ende des selben Schritts schwarz


Gewicht: 0+1+2+2+1+2+5+2+2+5=22

### 2b)

| Schritt | Kante | Zusammenhangskomponenten |
| ------- | ----- | ------------------------------------- |
| 1 | (a,c) | {a,c},{b},{d},{e},{f},{g},{h},{i},{j} |
| 2 | (f,g) | {a,c},{f,g},{b},{d},{e},{h},{i},{j} |
| 3 | (c,d) | {a,c,d},{f,g},{b},{e},{h},{i},{j} |
| 4 | (d,f) | {a,c,d,f,g},{b},{e},{h},{i},{j} |
| 5 | (h,i) | {a,c,d,f,g},{h,i},{b},{e},{j} |
| 6 | (g,j) | {a,c,d,f,g,j},{h,i},{b},{e} |
| 7 | (b,c) | {a,b,c,d,f,g,j},{h,i},{e} |
| 8 | (i,j) | {a,b,c,d,f,g,h,i,j},{e} |
| 9 | (e,g) | {a,b,c,d,e,f,g,h,i,j} |


## Aufgabe 3


Der Graph liefert deswegen den selben minimalen Spannbaum für beide Algorithmen,
weil der minimale Spannbaum eindeutig ist.

## Aufgabe 4

Beweis per Widerspruch:
Annahme: Der Pfad P liegt auf einem MST und ist kein Minimax-Pfad.

Es soll außerdem ein Pfad Q von u nach v führen,
der dieselben Knoten aufspannt wie P.

s. Beispiel:


- Wenn nun für das Gesamtgewicht von Q gilt, dass es kleiner ist, als das von P,
dann liegt P nicht auf einem MST.
- Wenn die Gesamtgewichte gleich sind, so liegt P auf einem MST und ist ein Minimax-Pfad.
- Wenn Gesamtgewicht von Q > Gesamtgewicht von P,
so ist P ein Minimax-Pfad und liegt auf einem MST.

In allen drei Fällen tritt ein Widerspruch zur Annahme auf.
Deshalb muss P ein Minimax-Pfad sein, wenn P auf einem MST liegt.

###### tags: `Algorithmen und Datenstrukturen` `Informatik` `Uni`