# Algorithmen und Datenstrukturen: Blatt 10

## Aufgabe 1

### 1a)


### 1c)

| | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| ----- | -------- | --- | ----- | --- | --- | --- | --- |
| d | $\infty$ | 4 | 0 | 2 | 1 | 2 | 3 |
| $\pi$ | $nil$ | 6 | $nil$ | 5 | 3 | 5 | 4 |

Reihenfolge: 3, 5, 4, 6, 7, 2

### 1d)


## Aufgabe 2

### 2a)

Der kleinste ungerichtete Graph, der nicht bipartit ist,
ist ein Graph mit 3 Knoten, wobei alle drei Knoten miteinander verbunden sind.


## Aufgabe 3

### 3a)

Die Strategie ist für das Beobachten selbst gut,
aber finanziell eher nicht.
Da dadurch sämtliche Kreuzungen besetzt werden müssen,
denn sobald eine Straße unbeobachtet ist,
diese dann doppelt besetzt werden wird und
somit zwei Fotographen für theoretisch eine Straße benötigt werden.
Aber eigentlich würde ein Forograph für die Straße reichen
und man für diese Straße statt 1000€ nur noch 500€ ausgeben muss.
Besser wäre mit der Breitensuche zu arbeiten zum Beispiel,
dass man alle Kreuzungen besetzt,
bei denen die Distanzen d zur Startkreuzung s gerade ist,
also d%2==0, so würden die Straßen nicht immer doppelt beobachtet werden.

### 3b)

Greedy-Algorithmus:
"Gehe alle Straßen ab (z.B. mit einer Breitensuche).
Wenn du auf eine unbeobachtete Kante triffst,
stelle Fotografen am Knoten am Ende der Kante auf."

Dies könnte zum Beispiel so aussehen:


Die mit X markierten Kreuzungen sind diejenigen,
an denen Fotografen stehen, s markiert den Startpunkt.
Der Algorithmus ist deshalb greedy,
weil lokal die naheliegenste Entscheidung zu treffen,
wenn man auf eine unbeobachtete Kante trifft, bedeutet,
mindestens an einem der beiden angrenzenden Knoten Fotografen aufzustellen
und so die Kreuzung zu beobachten.

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