---
tags: Assignments
---

# Blatt 07

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

---

## Aufgabe 1

:::info
__Erklärung__

=> Satz x:
- Beweis, dass aus den anderen Sätzen Satz x folgt.

<= Satz x:
- Beweis, dass aus Satz x die anderen Sätze folgen.
:::

(Definition Baum aus der Vorlesung: Ein zusammenhängender Graph ohne Kreise.)

### a)
__Beweis zu Satz 3__

=> Satz 3:
1. Beweis dass G zusammenhängend ist:
Die Definition eines Baumes besagt, dass er zusammenhängend ist.
2. Beweis für G hat n - 1 Kanten für n = |V|
Beweis per Induktion über die Anzahl der Knoten:

IA: Ein einfacher Baum mit 2 Knoten hat genau 1 Kante. Es gilt `m = n - 1`
IS: Wenn wir einen Knoten in einen Baum einfügen, dann müssen wir immer auch genau eine Kante einfügen, damit der entstehende Baum zusammenhängend und Kreisfrei ist, also die Baumeigenschaft erfüllt. Es gilt weiterhin `m = n - 1`

<= Satz 3:

Beweis über Induktion:

IA: Ein einfacher Graph mit 2 Knoten und einer Kante muss zusammenhängend und Kreisfrei sein. Der Graph ist also ein Baum

IS: Wenn wir Einen weiteren Knoten einfügen und eine weitere Kante (sodass m = n - 1 erhalten bleibt), dann muss diese Kante den neuen Knoten mit dem Restgraphen verbinden (da der Graph simpel und zusammenhängend ist). Es kann hierdurch kein Kreis entstehen. Das Anfügen des Knotens und der Kante führt also zu einem Baum.

__Beweis zu Satz 4__

=> Satz 4:

Wir betrachten 2 adjazente Knoten v und w die von der Kante e verbunden werden (OBdA). Nach Satz 2 ist der Pfad der nur aus e besteht der einzige, der v und w verbindet. Wenn wir e entfernen, gibt es also keinen Pfad zw. v und w mehr, und der Graph ist nicht mehr zusammenhängend.

<= Satz 4:

Satz 4 besagt, dass der Graph zusammenhängend ist, d.h. es gibt mind. einen simplen Pfad zwischen zwei beliebigen v und w. Satz 4 besagt auch, dass der Graph __minimal__ zusammenhängend ist, d.h. es gibt höchstens einen simplen Pfad zwischen zwei beliebigen Knoten v und w. Insgesamt folgt also dass es genau einen Pfad zw. v und w gibt (Satz 2).

__Beweis zu Satz 5__

Wir halten fest: Ein simpler Graph G ist genau dann nicht kreisfrei, wenn es für mind. ein beliebiges Knotenpaar v und w aus G mehr als 1 (?simplen) Pfad zwischen v und w gibt.

=> Satz 5:

Wenn es zwischen allen beliebigen Knotenpaaren v und w aus dem Graphen genau einen simplen Pfad gibt (Satz 2) dann gilt:
1. Der Graph ist Kreisfrei.
2. Einfügen einer Kante e zw. v und w (OBdA) führt dazu, dass es nun 2 Pfade zw. v und w gibt. Der Graph ist nicht mehr kreisfrei.

<= Satz 5:

Wenn G maximal Kreisfrei ist, dann muss durch jedes Einfügen von einer Kante e zwischen zwei Knoten v und w ein Kreis entstehen.
Da der Graph vor dem Einfügen von e kreisfrei ist, kann es 0 oder 1 Pfade zwischen v und w gegeben haben. Nach dem Einfügen ist die Anzahl also 1 oder 2.
Da nach dem Einfügen von e der Graph nicht mehr kreisfrei ist, muss es nach dem Einfügen der Kante mind. 2 Pfade zw. v und w geben. Vor dem Einfügen muss es also mind. 1 Pfad gegeben haben.
Daraus folgt, dass es vor dem Einfügen genau 1 Pfad gab. (Satz 2)

### b)

Es gibt für jedes w eine Kante die von w zu v führt und eine Kante die von v zu w führt. Damit gibt es auch für alle w und w' einen Pfad der von w zu w' führt. (Z.b. P(w, w') = (w, v, w'))

## Aufgabe 2

### a)
Für Wörter werden Knoten angelegt. Kanten werden für Verbindungen zwischen Wörtern mit Editierdsitanz von 1 angelegt. Die Kanten sind ungewichtet. Für die Lösung des Problems würde man den BFS Algorithmus verwenden.

### b)
Wir ersetzen jede "alte" Kante mit zwei gerichteten Kanten die jeweils ein Gewicht haben in der Höhe der Kosten ihrer Operation.

### c)
Knoten: Tiernamen
Kanten: Gerichtete Kante e von v zu w existiert genau dann wenn w mit dem Endbuchstaben von v anfängt.
Gewichtung: Keine

Algorithmus: Wir bestimmen ob der Graph zusamenhängend ist und ob jeder Knoten einen geraden Grad hat. Wenn ja, dann ist eine solche Wortkette möglich.

## Aufgabe 3

### a)
1.
__Adjazenzmatrix__
Laufzeit: `O(n^2)`
Begründung:
Wir iterieren über jeden Knoten (es gibt n Knoten). Für jeden Knoten müssen wir, um über die Kanten des Knotens zu iterieren, in jede Spalte der Adjazenzmatrix schauen (es gibt n Spalten). Die Laufzeit ist also in `O(n * n)`

2.
__Offset-Array__
Laufzeit: `O(n + m)`
Begründung:
Wir iterieren über jeden Knoten (es gibt n Knoten).
Die Laufzeit um über alle Kanten eines Knotens zu iterieren ist proportional zum Grad dieses Knotens. Die Laufzeit um über alle Kanten im Graph zu iterieren ist also proportional zur Summe aller Knotengrade. Die Summe aller Knotengrade ist, wie in der Vorlesung bewiesen gleich 2m.

<!-- Wir iterieren über jeden Knoten, Für jeden Knoten müssen wir, um über die Kanten des Knotens zu iterieren, an die jeweilige Stelle des Offset Arrays schauen und bis zum "degree" des jeweiligen Knoten die Kanten lesen. -->

Somit ist die Laufzeit also in `O(n + m)`.

### b)
Wir übernehmen den standard BFD Algorithmus mit den folgenden Abänderungen:
- Statt dem Markierungsarray benutzen wir ein Hopdistanz-array
- Wenn wir einen Knoten v betrachten, tun wir auch schon besuchte Knoten w in Schlange, unter der folgenden Bedingung: Hopdistanz(w) = Hopdistanz(v) + 1
- Wir legen ein weiteres Array P an welches die Anzahl der minimalen Pfade zu einem Knoten zählt. Es wird mit 0en initialisiert. Wenn wir das erste mal auf einen Knoten treffen (Hopdistanz = unendlich) dann setzten wir den Eintrag in P für den entsprechenden Knoten auf 1. Wenn wir ein weiters mal auf den Knoten treffen, dann prüfen wir ob die momentane Hopsdistanz gleich der Minimalen Hopdistanz für den Knoten ist. Wenn ja, dann erhöhen wir den Eintrag in P für den entsprechenden Knoten um 1.

### c)

Wenn sich der Algorithmus einen Knoten v anschaut, der von einem Knoten u aus entdeckt wurde, und dann einen adjazenten Knoten w != u findet, der schon markiert ist, dann heißt das, dass es einen Kreis im Graphen gibt.

## Aufgabe 4

### a)
Ja, dies ist für den Pfadgraphen P2 wahr. (Der mit nur 2 Knoten)

### b)
Nein, jeder Knoten wird immer über einen minimalen Weg besucht. Somit sind höchstens Querkanten, aber keine Vorwärtskanten möglich.

### c)
Nein, denn bei der In-Order Traversierung muss immer der kleinste / linkeste Kindknoten zuerst besucht werden. Bei der DFS ist dies nicht sichergstellt.

### d)
Wahr

### e)
Wahr.
Wenn wir eine Kante aus der Eulertour entfernen entsteht ein simpler Pfad der alle Knoten der Graphes durchläuft.
Wir nennen die beiden Endknoten des Pfades v und w.
Wenn wir nun bei v eine DFS beginnen, könnte diese (durch Zufall oder so) den Eulerpfad genau ablaufen, bis die Suche bei w landet. An diesem Punkt wären nun alle Knoten besucht worden, es gäbe also keine zu w adjazenten Knoten, die noch nicht besucht worden sind, und damit würde die DFS abbrechen. Somit beschreibt der Eulerpfad also einen möglichen DFS Baum.