---
# System prepended metadata

title: 'Algorithmen und Datenstrukturen: Blatt 12'
tags: [Algorithmen und Datenstrukturen, Informatik, Uni]

---

# Algorithmen und Datenstrukturen: Blatt 12

## Aufgabe 1

![A1](https://i.imgur.com/ipUsjTe.jpg)
Die lila markierten Kanten beschreiben den Kürzesten-Wege-Baum.

## Aufgabe 2

![2](https://i.imgur.com/Rmoh0FL.png)

### 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

![2a](https://i.imgur.com/Kd6NJzc.png)

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}                 |

![2b](https://i.imgur.com/Kd6NJzc.png)

## Aufgabe 3

![A3](https://i.imgur.com/IrIaVxR.png)

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:

![4.1](https://i.imgur.com/nYyFLRz.png)

- 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`
