# TI 02
## Aufgabe 1
### (a)
Aus einem Graphen $G = (V,E)$ seien $u$, $v$ zwei beliebige Knoten.

#### Fall 1:
Knoten $u$ und $v$ sind zusammenhängend.

Somit muss es einen Weg $u↝v$ und $v↝u$ geben. Im transponierten Graphen gibt es somit auch einen Weg v↝u und $u↝v$. Knoten $u$ und $v$ sind also wieder zusammenhängend.

#### Fall 2:
Knoten $u$ und $v$ sind nicht zusammenhängend.

Somit gibt es mindestens einen der Weg $u↝v$ oder $v↝u$ nicht. O.B.d.A nehmen wir an, dass es den Weg $u↝v$ nicht gibt. Dann gibt es im transponierten Graphen den Weg $v↝u$ nicht. Die Knoten $u$ und $v$ sind also nicht zusammenhängend.

Für alle $u,v$ aus $G$ gilt also, wenn sie in $G$ zusammenhängend sind, sind sie auch in $G^T$ zusammenhängend und wenn sie in $G$ nicht zusammenhängend sind, sind sie es auch nicht in $G^T$.
Somit bleiben die starken Zusammenhangskomponenten aus $G$ in $G^T$ erhalten.

### (b)
Sei scc($G$) der Graph, der als Knoten die starken Zusammen- hangskomponenten von $G$ besitzt und der eine Kante $(u,v)$ (mit $u ≠ v$) genau dann besitzt, falls es in $G$ einen Knoten in der starken Zusammen- hangskomponente $u$ gibt, der eine Kante zu einem Knoten in der starken Zusammenhangskomponente $v$ hat.

Wir zeigen durch Widerspruch, dass scc($G$) ein DAG sein muss.

Angenommen in scc($G$) gibt es einen Zyklus, dann gibt es mindestens zwei Knoten $u,v$ in diesem Zyklus, für die gilt: $u↝v$ und $v↝u$. Somit sind die Zusammenhangskomponenten, die die Knoten $u$ und $v$ darstellen, zusammenhängend. Knoten $u$ und $v$ müssen also die selbe Zusammenhangskomponente sein. Dies ist jedoch laut Definition ausgeschlossen. In scc($G$) kann es also keinen Zyklus geben.

Da scc($G$) laut Definition gerichtet ist und keinen Kreis enthält, ist scc($G$) ein DAG.

### (c\)
Sei $G = (V,E)$ ein DAG mit $n=a+2$ Knoten und $V = \{s,v_1,v_2,v_3,...,v_{a-1},v_a,t\}$.
Sei außerdem o.B.d.A die topologische Sortierung von $G$ $s \prec v_1 \prec v_2 \prec v_3 \prec ... \prec v_{a-1} \prec v_a \prec t$
Es kann also kein Pfad von einem in der topologischen Sortierung weiter hinten stehenden Knoten zu einem weiter vorne stehenden Knoten führen. Weil von jedem Knoten alle Kanten zu den in der topologischen Sortierung weiter hinten stehenden Knoten haben können, gehen wir davon aus, dass alle diese Kanten existieren.
Ein Pfad von $s$ nach $t$ kann also durch eine Teilmenge von Knoten aus $V' = V \setminus \{s,t\}$ dargestellt werden. Da in $V'$ genau a Knoten sind, gibt es $2^a$ Teilmengen von $V'$ und somit auch $2^a = 2^{n-2}$ Pfade von $s$ nach $t$.

## Aufgabe 2

### (a)
### Algorithmenbeschreibung
Wir legen ein 0-indiziertes Integer-Array A der Länge n an. Wir sortieren alle Knoten $v \in V$ topologisch, sodass gilt: $v_0 \prec v_1 \prec v_2 \prec v_3 \prec ... \prec v_{n-2} \prec v_{n-1}$, wobei $v_0$ = $s$ und $v_{n-1}$ = $t$. Der Wert A[i] gibt an, wie viele Pfade von $s$ nach $v_i$ führen. A[0] wird auf 1 gesetzt. Wir gehen nun alle Knoten $v_i$ mit $1\leq i \leq n-1$ aufsteigend durch. Für jeden Knoten betrachen wir all seine direkten Vorgänger mit der Anzahl der zu ihnen führenden Pfade. Die Summe dieser Pfade speichern wir in A[i]. Am Ende geben wir A[n-1] aus.

#### Eingabe
DAG $G = (V,E)$ mit n Knoten, genau einer Quelle $s$ und genau einer Senke $t$. E sei als Adjazensmatrix gegeben.

#### Ausgabe
Anzahl $x$ der Pfade $s↝t$.

#### Korrektheitsbedingung
Die Summe aller Pfade $s↝t = x$

### Korrektheisbeweis
Da $G$ ein DAG ist, existiert eine topologische Sortierung. Wenn wir diese Sortierung durchgehen, sind alle Vorfahren des aktuell betrachteten Knotens schon bearbeitet. Wenn es zu einem Vorfahren unseres betrachteten Knotens n Pfade gibt, gibt es diese auch zum aktuellen Knoten. Wenn es mehr als einen direkten Vorfahren gibt, summieren sich diese Pfade auf. Da alle Knoten durchgegangen werden, ist A[n-1] am Ende belegt und enthält die korrekte Anzahl an Pfaden $s↝t$. Der Algorithmus terminiert immer, da er nur endlich viele Knoten durchgeht und alle Knoten nur einmal bearbeitet.

### Laufzeitanalyse
Das initiieren des Array benötigt $O(n)$ Schritte. Das erstellen einer topologischen Sortierung erfolgt in $O(n+m)$. Das durchgehen der topologischen Sortierung erfolgt in O(n), außerdem müssen alle Kanten einmal betrachtet werden, weshalb wir bei dem durchgehen der Sortierung in $O(n+m)$ liegen. Die Ausgabe von A[n-1] erfolgt in O(1). Insgesamt ergibt sich also eine Laufzeit von O(n+m).

### (b)
### Algorithmenbeschreibung
Wir legen ein 0-indiziertes Integer-Array A der Länge n an. Wir sortieren alle Knoten $v \in V$ topologisch, sodass gilt: $v_0 \prec v_1 \prec v_2 \prec v_3 \prec ... \prec v_{n-2} \prec v_{n-1}$, wobei $v_0$ = $s$ und $v_{n-1}$ = $t$. Der Wert A[i] gibt an, wie schwer der schwerste Pfad $s↝v_i$ ist. A[0] wird auf 0 gesetzt. Wir gehen nun alle Knoten $v_i$ mit $1\leq i \leq n-1$ aufsteigend durch. Für jeden Knoten betrachen wir all seine direkten Vorgänger mit dem Gewicht des schwersten zu diesem führenden Pfades addiert mit dem Gewicht der Kante von genau diesem Vorgänger zum aktuellen Knoten $v_i$. Das Maximum dieser Werte speichern wir in A[i]. Am Ende geben wir A[n-1] aus.

#### Eingabe draft
DAG $G = (V,E)$ mit n Knoten, genau einer Quelle $s$ und genau einer Senke $t$. E sei als Adjazensmatrix gegeben.
Eine Funktion $w: E \rightarrow {\rm I\!R}$ die das Gewicht einer Kante zurückgibt.

#### Ausgabe draft
Maximales Gewicht $x$ eines Pfades $s↝t$.

#### Korrektheitsbedingung draft
Das Gewicht $x$ ist das maximale Gewicht aller Pfade $s↝t$.

### Korrektheisbeweis draft
Da $G$ ein DAG ist, existiert eine topologische Sortierung. Wenn wir diese Sortierung durchgehen, sind alle Vorfahren des aktuell betrachteten Knotens schon bearbeitet. Wenn es zu einem direkten Vorfahren $v_v$ unseres betrachteten Knotens einen Pfad mit einem Gewicht g gibt, gibt es zum aktuellen Knoten $v_a$ einen Pfad mit dem Gewicht g + $w((v_v,v_a))$. Wenn es mehr als einen direkten Vorfahren gibt, nehmen wir das maximale Gewicht der möglichen Pfade. Da alle Knoten durchgegangen werden, ist A[n-1] am Ende belegt und enthält das korrekte maximale Geiwcht aller Pfade $s↝t$. Der Algorithmus terminiert immer, da er nur endlich viele Knoten durchgeht und alle Knoten nur einmal bearbeitet.

### Laufzeitanalyse draft
Das initiieren des Array benötigt $O(n)$ Schritte. Das erstellen einer topologischen Sortierung erfolgt in $O(n+m)$. Das durchgehen der topologischen Sortierung erfolgt in O(n), außerdem müssen alle Kanten einmal betrachtet werden, weshalb wir bei dem durchgehen der Sortierung in $O(n+m)$ liegen. Die Ausgabe von A[n-1] erfolgt in O(1). Insgesamt ergibt sich also eine Laufzeit von O(n+m).

## Aufgabe 3
### Algorithmenbeschreibung
Wir wählen einen beliebigen Knoten $v_0$ aus $V$. Von diesem Knoten starten wir eine Breitensuche und speichern zu jedem Knoten $v_x$ die Entfernung $d$ zu $v_0$ indem wir die Entfernung $d$ vom direkten Vorgänger $v_v$ mit dem Gewicht der Kante $(v_v,v_x)$ $w((v_v,v_x))$ addieren. Am Ende dieses Vorgangs nehmen wir den entferntesten Knoten $v_e$ und starten die gerade beschrieben Breitensuche noch einmal von $v_e$. Der Pfad von $v_e$ zum entferntesten Knoten $v_{e'}$ von $v_e$ ist der längste Pfad in diesem Baum.

#### Eingabe
Baum $G = (V,E)$ mit n Knoten
Funktion $w : E \rightarrow {\rm I\!R}_0^+$

#### Ausgabe
Länge $x \in {\rm I\!R}$ eines längsten Pfads.

#### Korrektheitsbedingung
Für alle Teilmengen $V'$ von $V$ gilt:
($|V'|\geq 2 \land V'$ ist Pfad) $\rightarrow$ länge des Pfades $\leq x$

### Korrektheisbeweis
Angenommen der Pfad zwischen $v_e$ und $v_{e'}$ ist nicht der längste, dann muss es einen Knoten geben, der eine größere Entfernung zu einem der beiden Endpunkte hat. Wenn es so einen Knoten geben würde, hätten wir ihn mit der Breitensuche gefunden und er wäre der am weitesten Entfernte Punkte gewesen. Somit finden wir immer den längsten Pfad im Baum.

### Laufzeitanalyse
Da die Breitensuche in O(n+m) läuft und die Speicherung der Kosten pro Knoten in O(1) liegt, sowie m = n-1 läuft der gesamte Algorythmus in O(n+n-1) = O(n).